ComDoc ComDoc

최댓값과 최솟값 찾기 이진 탐색 트리에서 최솟값은 항상 왼쪽에 있기 때문에 왼쪽의 None을 찾아 직전의 값을 리턴하면 됩니다. 최댓값은 반대입니다. 특정값 찾기 현재 노드의 값과 특정값을 비교해서 높으면 오른쪽 낮으면 왼쪽으로 내려가면 됩니다. class Node: def __init__(self, item): self.item = item self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, item): new_node = Node(item) if self.root is None: self.root = new_node return current = self.root while ..

트리란? Tree는 edge와 node의 집합입니다. 최상위 node를 root라 하고, 한 노드가 아래 노드와 연결되어 있을 때 위 노드를 parent, 아래 노드를 child라 합니다. 자식노드가 없는 노드를 leaf 노드라고 합니다. 직접 연결되지 않은 노드라도 연결된 에지를 통해 방문할 수 있습니다. 한 노드에서 다른 노드로 도달하는 데 사용한 에지의 모음을 경로(path)라고 합니다. 모든 노드를 일정한 순서로 방문하는 것을 트리 순회(tree traverasal) 또는 트리 탐색이라 합니다. 트리를 레벨로 구분하기도 합니다. 루트는 레벨0 그 자식들은 레벨 1이 되는 식입니다. 총 레벨을 수를 트리의 깊이라고 합니다. 이진트리란? 이진 트리(binary tree)는 모든 노드의 자식 노드가 2..

집합(set)은 파이썬 2.3부터 포함된 자료형입니다. 이걸 또 한 번 만들어 보겠습니다. 삽질 맞습니다. ㅠ,.ㅠ 집합의 특징은 다음과 같습니다. 집합의 멤버는 순서가 없으며 유일합니다. 멤버가 하나도 없는 집합을 공집합(empty set)이라 합니다. 집합에 포함될 수 있는 모든 멤버를 포함하는 집합을 전체집합(universe)이라 합니다. 두 집합의 멤버가 정확하게 같아야 같은 집합입니다. 한 집합의 모든 멤버가 다른 집합에 포함되어 있을 때 이 집합을 다른 집합의 부분 집합(subset)이라 합니다. 집합의 동작은 다음과 같습니다. 합집합 두 집합을 합쳐 새로운 집합을 만듭니다. 교집합 두 집합에 모두 존재하는 멤버로 새로운 집합을 만듭니다. 차집합 한집합의 멤버 중 다른 집합에 존재하지 않는 멤..

해싱은 데이터를 아주 빠르게 '삽입'하거나 '가져올 때' 사용하는 기법입니다. 하지만, 최솟값이나 최댓값을 찾을 때(전체 자료를 검색해야 할 때)는 효율이 떨어집니다. 김 빠지는 이야기를 하나 하자면.. 파이썬의 딕셔너리는 해시 테이블로 구현되어 있습니다.. ㅇㅇ 있는 걸 만드는 삽질을 또 해보겠습니다. 주의: 직접 만든 해시 함수를 보안에 관련된 부분에 사용하는 것은 위험합니다. 해시(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의 반대(요소 제거) 그리고 보통 디큐로 발음합니다. 특히 인큐의 반대말로 쓰였을 때는 디..