ComDoc ComDoc

해싱은 데이터를 아주 빠르게 '삽입'하거나 '가져올 때' 사용하는 기법입니다. 하지만, 최솟값이나 최댓값을 찾을 때(전체 자료를 검색해야 할 때)는 효율이 떨어집니다. 김 빠지는 이야기를 하나 하자면.. 파이썬의 딕셔너리는 해시 테이블로 구현되어 있습니다.. ㅇㅇ 있는 걸 만드는 삽질을 또 해보겠습니다. 주의: 직접 만든 해시 함수를 보안에 관련된 부분에 사용하는 것은 위험합니다. 해시(hash)의 개념은 각기 다른 곳에서 독립적으로 발생하였다. 1953년 1월 H. P. Luhn은 체이닝(chaining)으로 해시를 사용한 내부 IBM 비망록을 작성했다. G. N. Amdahl, E. M. Boehme, N. Rochester, Arthur Samuel은 거의 같은 시기에 해시를 사용하는 프로그램을 제..

먼저 파이썬 내장 딕셔너리 자료형을 이용해 다음 텍스트에서 각 단어가 몇 번 나오는 지를 확인하는 프로그램을 구현해 봅시다. the brown fox jumped over the blue fox 예상 결과 the 2 brown 1 fox 2 jumped 1 over 1 blue 1 코딩 def count_words(text): words = text.split(' ') counter = {} for word in words: if word in counter: counter[word] += 1 else: counter[word] = 1 for word in counter: print(word, counter[word]) count_words('the brown fox jumped over the blue..

파이썬에는 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 리..