맵 & 딕셔너리(Map & Dictionary) 맵과 딕셔너리는 매우 유사한 자료구조다. 이에 맵에 대해서 먼저 설명하고, 맵과 딕셔너리의 차이점을 알아보겠다. 우선 맵은 키-값(key-value) 쌍으로 이루어진 집합이다. 키를 통해서 값을 추가, 탐색하고 이를 수정, 삭제할 수 있다. 이때 맵의 특징은 같은 키를 가지는 여러 값이 존재할 수 없다는 것이다. 그렇다면 딕셔너리는 무엇일까? 딕셔너리는 기본적으로 맵과 동일하지만, 중복된 키값이 존재할 수 있다는 특징이 있다. 다만 실제로 맵과 딕셔너리의 차이를 엄밀하게 다들 지키는 것은 아니고, 반대의 의미로 쓰이거나 하여 사실상 같은 의미를 가진다고 볼 수 있다. 예를 들어 파이썬의 딕셔너리는 기본적으로 키 중복을 허용하지 않지만 딕셔너리(dict)라는..
힙(Heap) 힙은 완전 이진 트리(Complete binary tree)의 형태를 가집니다. 즉, 완전 이진 트리의 성질에 따라 트리의 높이 h arr[idx]) { swap(parent, idx); upHeap(parent); } } void downHeap(int idx) { int left = 2 * idx; int right = 2 * idx + 1; int child; if (left > getSize()) return; else if (left == getSize()) child = left; else { if (arr[left]
우선순위 큐에 대해 소개하기 전에 ADT(Abstract Data Type)와 implementation(구현 방법)의 차이에 대해서 잠시 다시 짚어보겠습니다. ADT(자료구조) Implementation(구현 방법) List Array, Linked list Stack Array, Linked list Queue Array, Linked list Tree Linked structure Binary tree Array, Linked structure Priority queue Heap, Binary search tree, List 위와 같이 각 자료구조는 여러가지의 구현 방법이 있을 수 있습니다. 또한 다른 자료구조 자체도 다른 자료구조의 구현 방법이 될 수 있습니다. 이를 여기서 다시 짚어보는 이유는 ..
이진 트리(Binary tree) [이미지] 이진 트리는 특별한 트리로, 자식을 최대 2개 가질 수 있는 트리입니다. 이떄 두 자식을 left child, right child라고 합니다. 용어 n: 노드의 개수 m: internal node(자식이 있는 노드)의 개수 l: leaf node(자식이 없는 최하위 노드)의 개수 h: 트리의 높이 이진 트리의 특성 이진 트리의 성질은 수학적으로 몇가지 특정지을 수 있습니다. [이미지] 이진트리의 특성상 높이는 log2(n+1) - 1 오른쪽 자식 순으로 탐색을 하는 방식으로, 그 특성상 자식이 2개로 제한되는 이진 트리에서만 가능합니다. 오일러 투어(Euler tour traversal) dfs방식으로 탐색을 하며 마주치는 모든 노드(이미 방문하여 되돌아간 ..
트리 트리는 계층 구조를 가진 모델입니다. 트리는 노드로 이루어져 있으며 이들 노드 간에는 부모-자식 관계가 존재합니다. 트리가 트리라고 불리는 이유는 마치 나무의 가지가 뻗어나가는것과 같은 형태를 보이기 때문입니다. 다만 나무가 위로 뻗어나는것과 달리 트리는 위의 부모노드에서 아래의 자식노드로 뻗어나가는 특징을 가지고 있습니다. 그렇기에 각 트리의 노드는 하나의 부모만을 가지지만, 자식으로는 여러 노드를 가질 수 있습니다. 용어 루트 노드(Root): 부모가 없는 노드로 트리에 하나만 존재한다. 예시에서는 1. Internal node: 적어도 하나의 자식을 가지는 노드. 예시에서는 1, 2, 3, 5. External node: 자식을 가지지 않는 노드. 예시에서는 4, 6, 7. Ancestors ..
재귀(Recursion) 재귀는 어떠한 자료구조나 ADT는 아니나 자료구조를 다룰 때 자주 나오는 개념이기에 소개한다. 재귀란 자기 스스로를 호출하여 반복하는 것이다. 재귀의 반대되는 개념으로는 iterative가 있다. 재귀함수와 for문의 관계라고 생각하면 된다. # 재귀 함수의 예시 def say_hello(): print("Hello!") say_hello() 이런 재귀 알고리즘을 사용하는 이유는 우선 '사람'이 보고 이해하기 좋기 때문이다. iterative 하게 구현하는 것이 계속해서 재귀함수가 스택 메모리에 쌓이는 것을 방지하기에 성능면에서는 더 뛰어날 것이다. 특히 이진 탐색이나 위상 정렬등에서 재귀적으로 사고하는 것이 이해하기에 편하다. 구현 따로 재귀 함수에 구현이라 할 것은 없지만, ..
덱(Deque) Deque(덱)은 Double-ended queue의 줄임말입니다. 이는 큐와 매우 비슷한 자료구조입니다. 큐가 front에서 dequeue를 하고 rear에서만 enqueue를 했다면, 덱에서는 양쪽으로 enqueue와 dequeue가 가능합니다. 파이썬 Collections 기준으로는 enqueue 시에 append()와 appendleft() 함수를 사용하고, dequeue 시에는 pop()와 popleft()를 사용합니다. 이러한 특성으로 덱은 스택과 큐 모두를 대체 가능한 자료구조입니다. 그렇다면 왜 큐와 스택 대신 항상 덱을 사용하지 않을까요? 이에 대한 답은 굳이 두 가지의 특성을 합친 것이 필요하지 않은 경우가 많기 때문입니다. 또한 덱을 사용하면 오버헤드가 발생할 수 있는..
큐 스택이 LIFO(Last In First Out)의 구조라면 큐는 FIFO(First In First Out), 즉 선입선출의 구조라고 할 수 있습니다. 큐에는 앞(front)과 뒤(rear)가 존재하는데, 이때 데이터 삽입시에 뒤에 enqueue 되고, 데이터를 꺼낼 시에는 앞에서 dequeue 됩니다. 활용 이러한 큐의 개념은 여러곳에서 사용됩니다. 대용량의 트래픽을 처리할 때 큐를 응용한 Kafka나 RabbitMQ 등을 사용하는데, 작업들을 큐에 쌓아놓고 Consumer가 큐에서 작업을 꺼내서 차례대로 처리하는 방식입니다. 큐는 프로세스의 round robin scheduler에도 사용되는데, dequeue한것을 다시 enqueue를 반복하는 방식으로 계속 순환이 가능합니다. 또한 트리에서 노..
스택 스택은 LIFO(Last in, first out)의 후입선출 구조를 가지고 있는 자료구조입니다. 다시 말해서, 마치 책을 쌓아놓는 것처럼 가장 마지막에 넣은 데이터를 가장 먼저 빼낼 수 있는 구조입니다. 활용 스택은 정말 다양한 곳에서 사용되는데, 예를 들어 컴퓨터의 메모리 영역에서도 스택이 활용됩니다. 재귀 함수를 사용하여 함수 내에서 다른 함수를 계속 호출할 때도 호출한 함수들이 스택에 차례로 쌓이며 작동하며, 운영 체제에서 되돌리기(Ctrl + Z)를 사용하는 것도 이전 작업을 스택에 쌓아놓고 되돌리는 원리입니다. 이뿐만 아니라 스택은 다른 자료구조의 구현을 위해서도 사용됩니다. ADT int getSize() bool isEmpty() 스택의 핵심은 삽입의 push, 추출하는 pop 그리고..
연결 리스트 연결 리스트(Linked List)는 배열과 유사하게 리스트를 표현하는 자료구조입니다. 연결 리스트는 여러 개의 노드로 이루어져 있으며, 각 노드에 데이터가 저장됩니다. 각 노드는 값(value)을 저장하는 공간과 다음 노드를 가리키는 포인터로 구성되어 있습니다. 이때 노드가 다음 노드를 가리키는 포인터 1개 만을 가진다면 singly linked list(단일 연결 리스트), 다음 노드뿐만 아니라 자신의 이전 노드를 가리키는 포인터도 가지면. doubly linked list(이중 연결 리스트)라고 합니다. Head와 Tail 다음은 단일 연결 리스트의 모습입니다. 연결 리스트는 첫 번째 노드를 가리키는 head 포인터와 마지막 노드를 가리키는 tail 포인터를 가지고 있습니다. 이때 노드..
