ComDoc ComDoc

파이썬에는 queue.PriorityQueue가 기본 모듈로 있습니다. @,.@ PriorityQueue의 베이스인 heapq 모듈도 있습니다. ~! 그렇기 때문에 만들 필요가 없는 것이고, (파이썬의 배터리 인클루드~!) 또 제대로 만들려면 힙을 이용하는 게 맞습니다만, 간단하게 흉내만 내 보겠습니다. 혹시 힙이 궁금하시면 다음 링크를 참고하십시오. https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88 --------------------------------- 보통 큐에서는 먼저 삽입한 요소부터 삭제됩니다. 하지만 우선순위를 기준으로 요소를 삭제해야 하는 경우도 있습니다. 대표적인 예가..

큐(queue)로 기수 정렬(radix sort) 하기 데이터를 정렬할 때도 큐를 이용할 수 있습니다. 아주 예전 컴퓨터에 프로그램을 입력할 때 천공(펀치) 카드를 사용했죠. (디스켓 세대인 저도 이건 교과서에서나 볼 수 있었습니다.) 펀치 카드 정렬할 때 카드를 보관하는 통을 이용했다고 합니다. 예를 들어서 설명하겠습니다. 다음 번호가 찍혀 있는 천공 카드가 있다고 가정하겠습니다. 34, 56, 86, 46, 13, 51, 38, 54 1. 첫 번째 (1의) 자리부터 분류합니다. 첫 번째 자리의 숫자와 같은 번호가 붙어 있는 바구니에 담으면 됩니다. 10진수니까 10개의 바구니가 필요합니다. 0번 바구니: 1번 바구니: 51 2번 바구니: 3번 바구니: 13 4번 바구니: 34, 54 5번 바구니: 6..

큐는 리스트의 일종으로 뒷부분에 데이터가 삽입되고 앞부분에서는 데이터가 삭제되는 자료구조입니다. 간단히 선입 선출 (FIFO = First-in first-out)이라고 하죠. 컨베이어 벨트를 떠올리시면 이해가 쉬울 겁니다. 프린터 스풀러나, 운영 체제의 프로세스 처리 순서 등에서 많이 쓰이죠. 큐의 뒤(rear, tail, back)에 요소를 삽입하는 것을 enqueue(put, insert) 큐의 앞(front, head)에서 요소를 제거하는 것을 dequeue(get, delete)라고 합니다. * dequeue에는 두 가지 의미가 있습니다. double ended queue 양 끝을 가지는 큐, enqueue의 반대(요소 제거) 그리고 보통 디큐로 발음합니다. 특히 인큐의 반대말로 쓰였을 때는 디..

우리가 흔히 사용하는 방식은 중위 표기법(infix notation)인데, 연산 기호를 중간에 넣습니다. ex) 1 + 2 연산기호가 앞에 오는 전위 표기법(prefix notation)도 있고.. ex) + 1 2 연산기호가 뒤에 오는 후위 표기법(postfix notation)도 있습니다.. ex) 1 2 + 전위 표기법은 폴란드식 표기법(PN, Polish Notation), 후위 표기법은 역 폴란드식 표기법(RPN, Reverse-Polish Notation)이라고도 하는데요. 이런 표기법들은 괄호를 쓸 필요가 없고, 또 스택으로 구현할 수 있습니다. 자세한 건 글 마지막 링크들을 참고하시고요. 간단하게 느낌만 살펴보도록 하겠습니다. 후위표기법 : 5 6 + 7 * 2 / 중위표기법 : ((5 +..

수식에 열고 닫는 괄호 쌍을 체크할 때도 스택을 이용할 수 있습니다. 수식을 인자로 받아 수식에 괄호가 빠졌을 때 나 홀로 있는 괄호의 위치를 반환하는 함수를 구현해 봅시다. 예를 들자면 '2.4 + 23/12 + (3.141592 * .21' 코딩해 보죠.. def check_bracket(text): stack = [] for i in range(len(text)): if text[i] == '(': stack.append(i) elif text[i] == ')': stack.pop() return stack print(check_bracket('2.4 + 23/12 + (3.141592 * .21')) 간단히 개념만 잡는 정도로 작성해 보았습니다. 위 코드의 경우 문제가 있습니다. 주어진 문자열에서..

프로그래밍 언어를 구현할 때도 스택을 사용합니다. 좀 더 자세히 말씀드리면 함수의 호출은 스택으로 구현됩니다만, 이 부분을 자세히 설명드리는 것은 이 글의 범위를 벗어난 것 같습니다. 혹시 이 부분에 대해 궁금하신 분은 다음 사이트를 참고하시기 바랍니다. https://dojang.io/mod/page/view.php?id=1376 스택으로 재귀 구현 흉내 내기를 해보겠습니다. 먼저 재귀의 가장 흔한 예인 팩토리얼을 만들어 봅시다. 5 팩토리얼은 다음과 같죠.. 5! = 5*4*3*2*1 = 120 코딩을 합니다. # 팩토리얼 2019-06-01 def factorial(n): if n == 1: return n return n*factorial(n-1) print(factorial(5)) # 120 리..

앞으로 읽으나 뒤로 읽으나 같은 단어, 구절, 숫자 등을 회문(palindrome)이라고 합니다. 스택은 '(깔끔하게 정돈하여) 쌓은 무더기'라는 뜻입니다. (아래) 먼저 쌓은 것부터 꺼낼 수 없고 (가장 위) 마지막 쌓은 것부터 꺼낼 수 있습니다. 파이썬에서는 list의 append 메소드가 push와 같고 list에는 pop 메소드도 있으니 list를 바로 쓰시면 됩니다. 스택을 이용해서 넣었다 빼면서 원문과 같은 지 확인하면 됩니다. def is_palindrome(word): s = [] for i in range(len(word)): s.append(word[i]) for i in range(len(word)): if s.pop() != word[i]: return False return Tru..

십진수의 진법 변환 (기수 범위: 2~9) def change_base(num, base): stack = [] while num > 0: stack.append(num % base) num = num // base result = '' for _ in range(len(stack)): result += str(stack.pop()) return result print(change_base(7, 2)) # 111 * (언패킹 등에서) 사용하지 않는 변수는 _ 을 사용하는 관례가 있습니다. 스택에 연연하지 않고 파이썬스럽게 코딩한다면... 이런 느낌? def change_base(num, base): stack = [] while num > 0: stack.append(num % base) num = nu..