이진 트리(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 포인터를 가지고 있습니다. 이때 노드..
리스트는 여러 개의 요소들을 나타내는 방식입니다. 자료구조론에서 이러한 리스트를 표현하는 밥법은 크게 두 가지로, 배열(Array)과 연결 리스트(Linked List)가 있습니다. 이번 글에서는 배열과 그 특성에 대해서 다루어보겠습니다. 배열 int arr[3] = {1, 2, 3}; 배열은 같은 데이터 타입을 가지는 요소들의 sequence(시퀀스)입니다. 배열 속에서 각 요소들은 index(인덱스)로 접근가능합니다. N의 크기를 가지는 배열에서 첫 번째 요소의 인덱스는 0, 두 번째 요소의 인덱스는 1, 이런 식으로 증가하여 N번째(마지막) 요소의 인덱스는 N-1이 됩니다. 특징과 장점 같은 데이터 타입을 가지기 때문에 배열의 각 요소는 같은 크기를 가지게 됩니다. 같은 크기를 가진다는 점 덕분에 ..
지난 학기에는 학교에서 자료구조를 수강했었다. 흔히 컴퓨터공학 6대 과목을 자료구조, 알고리즘, 컴퓨터 구조론, OS, 컴퓨터 네트워크, 데이터베이스 이렇게 6가지를 말하곤 한다. 그중 처음 듣는 과목인 자료구조였던 만큼 제대로 된 전공공부를 해보게 된다 라는 느낌으로 수강하였다. 사실 자료구조의 대부분은 따로 커리큘럼을 따라 배운것은 아니지만, 그때그때 배웠던 지식으로 알고 있었기에 대부분 수업을 복습하는 느낌으로 듣게 되었다. 그러나 원래 잘 확실히 이해하지 못했던 Priority Queue와 Heap의 관계를 ADT와 Implemantation의 관계라는 것을 이해할 수 있었고, AVL Tree를 직접 구현해보기도 하고, 여러 자료구조들을 수학적으로 따져보기도 하는 과정도 새로웠다. 또한 그래프 구..
