1장 자료 구조

컴퓨터 안에서 데이터는 메모리에 저장되는데, 데이터의 순서나 위치 관계 등을 정하는 것이 ‘자료 구조’ 이다. 데이터를 메모리에 저장할 때 목적에 맞게 구조화해서 메모리의 이용 효율을 높이기 위한 것으로, 7개의 자료 구조를 정리했다.

---

List

리스트(list)는 데이터를 일직선으로 나열한 형태를 가지고 있다. 데이터의 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸린다.

리스트의 개념도이다. 네 개의 문자열 ‘Blue’, ‘Green’, ‘Yellow’, ‘Red’ 가 데이터로 저장되어 있으며, 각 데이터에는 포인터(pointer)가 있어 다음 데이터의 메모리 위치를 가리킨다. 리스트에서는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 영역에 흩어져서 저장된다.

• 데이터를 조회하려면 포인터를 처음부터 순서대로 따라가야만 한다.
• 데이터 추가는 추가할 위치의 앞뒤 포인터를 변경만 하면 되므로 간단하다. (삭제도 같은 방식으로 포인터의 방향을 바꾸면 된다)

조회	추가	삭제
O(n)	O(1)	O(1)

Array

배열(array) 은 데이터를 1열로 나열한 것이다. 리스트와는 대조적으로 데이터에 접근하기는 쉽지만 추가나 삭제에 시간이 걸린다.

조회	추가	삭제
O(1)	O(n)	O(n)

Stack

스택(Stack)은 데이터를 1열로 나열하지만, 서류를 쌓아 놓은 경우처럼 새롭게 추가한 데이터에만 접근할 수 있다. 새로운 서류가 도착하면 현재 서류 더미의 가장 위에 올려두고 서류를 꺼낼 때는 가장 위에서부터 꺼내는 것과 같다.

• 데이터 추가 : push
• 데이터 추출 : pop

스택처럼 나중에 넣은 것을 먼저 꺼내는 후입선출 구조를 LIFO 라고 한다. 리스트나 배열과 마찬가지로 스택도 데이터를 1열로 나열한 것이지만 데이터 추가나 삭제가 단방향으로만 가능하다는 제약이 있다. 만약 중간에 있는 데이터가 필요하다면 해당 데이터가 제일 위에 올 때까지 데이터를 pop 해야 한다.

단방향으로만 조작할 수 있다는 제약이 있어 불편하다고 생각할 수도 있지만, 항상 최신 데이터만 접근할 수 있도록 하는 구조에서는 편리하게 사용할 수 있다.

Queue

큐(Queue)는 데이터를 1열로 나열한 구조로, 스택과 비슷하지만 큐는 추가하는 측과 삭제하는 측이 반대다. ‘대기 행렬’ 이라고도 불리는데, 그 명칭처럼 줄을 서 있는 행렬을 생각하면 이해하기 쉽다. 행렬에서는 새롭게 온 사람이 가장 뒤에 서며, 가장 앞에 있는 사람이 순서대로 처리된다.

• 데이터 추가 : enqueue
• 데이터 추출 : dequeue

큐는 선입선출 구조 (FIFO) 이다. 스택과 마찬가지로 데이터를 조작할 수 있는 위치가 정해져 있다. 다만 큐에서는 추가하는 쪽과 추출하는 쪽이 반대이다. 오래된 데이터부터 순서대로 처리해야 하는 것은 매우 자연스러운 방식이어서 큐는 폭넓게 활용되고 있다. 예를 들어, 너비 우선 탐색에서는 탐색 후보 중에서 항상 가장 오래된 것을 선택하므로 후보 관리에 큐를 활용한다.

Hash Table

해시 테이블(Hash Table)은 ‘해시 함수’와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조이다.

해시 테이블은 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장한다. 만약 해당 데이터를 배열에 저장한다면 선형 탐색이 이루어지므로 데이터양에 비례해서 시간이 늘어난다. 이 문제를 해결해 주는 것이 해시 테이블이다.

1. ‘해시 함수’ 를 이용해서 Joe의 키(즉 문자열 ‘Joe’)에 해당하는 해시값을 계산한다. 여기서는 4928 이라는 결과가 나온다.
2. 구한 해시값을 배열의 상자 갯수인 5로 나누어 mod 연산한다. (5로 나눈 나머지는 3이다)
3. 구한 수와 같은 배열의 3번 상자에 Joe 의 데이터를 저장한다.
4. 만약 Joe 를 키로 갖는 데이터를 조회하고자 한다면 key 의 해시값을 계산하면 바로 그 위치를 찾을 수 있게 되는 것이다.
5. 그런데 추가로 같은 해시값을 갖는 key 가 추가된다면(이를 ‘충돌’이라고 한다.), 배열의 3번 상자에서 리스트 구조로 연결해서 저장한다.
6. 만약 3번 상자에 저장된 Ally 라는 key 를 찾는다면, 제일 처음 저장된 Joe 를 선두로 하는 리스트를 대상으로 선형 탐색을 실시한다.

이처럼 해시 테이블에 사용하는 배열의 크기는 너무 작으면 충돌이 많아지고 선형 탐색의 빈도가 높아진다. 반대로 크기가 너무 크면 데이터가 없는 상자가 많아져서 메모리를 낭비하게 된다. 따라서 배열의 크기를 적절히 설정하는 것이 중요하다.

Heap

힙(Heap) 은 그래프의 트리 구조 중 하나로, ‘우선순위 큐’를 구현할 때 사용된다. 우선순위 큐는 자료 구조의 하나로서 데이터를 자유롭게 추가할 수 있다. 반면 데이터를 추출할 때는 최솟값부터 순서대로 선택한다. 추가는 자유롭게 하고 추출할 때는 작은 값부터 꺼내는 것이 우선순위 큐이다.

힙을 표현하는 트리 구조에서는 각 정점을 ‘노드(node)’라고 부른다. 각 노드에 데이터가 저장된다. 노드들은 최대 두 개의 자식 노드를 가진다. 노드는 위에서부터 채워지며, 같은 층에서는 왼쪽부터 채워진다. 또한 힙에서는 데이터 저장 위치를 정하기 위해 자식 노드의 숫자는 반드시 부모 노드의 숫자보다 커야 한다는 규칙이 있다. 따라서 가장 위(root)에 가장 작은 숫자가 들어있다. 이 규칙을 지키기 위해 가장 아래층에 있는 왼쪽 노드부터 값을 채우고, 가장 아래 층이 모두 채워지면 새로운 층을 만들어서 또 가장 왼쪽부터 채워나간다.

1. 힙에 숫자 5를 추가하는 경우를 보자.
2. 추가되는 수는 가장 아래 층의 왼쪽부터 저장된다. 그림의 경우 아래층에 한 자리가 남아있으므로 거기에 저장된다.
3. 부모의 숫자가 클 때는 조건을 만족하지 않으므로 부모와 자식을 교환한다. (6과 5를 교환)
4. 그 다음으로는 부모 1 < 자식 5 이므로 부모의 숫자가 작아서 교환이 발생하지 않는다. 이것으로 힙에 숫자 추가가 완료된다.
5. 힙에서 숫자를 꺼낼 때는 가장 위에 있는 숫자가 추출된다. root의 숫자가 최솟값을 지니고 있기 때문이다.
6. 가장 위의 숫자가 없어졌으므로 힙의 구조를 다시 정리해야 한다.
7. 이럴 때는 가장 후미에 있는 6이 가장 위로 이동한다.
8. 부모 6 > 자식(우) 5 > 자식(좌) 3 이므로 가장 낮은 왼쪽 자식과 부모를 교환한다.
9. 이것을 교환이 발생하지 않을 때까지 반복한다.

힙은 항상 root에 최솟값이 있으므로 데이터 수에 상관없이 O(1) 시간에 최솟값을 추출할 수 있다. 또한 추출 후 힙을 재구축할 때에는 가장 후미에 있는 데이터를 root로 가져온 후 자식과 비교해 가며 아래 방향으로 진행한다. 때문에 계산 시간은 트리의 높이와 비례한다. 데이터 수를 n이라고 하면 힙 형성 조건에 따라 트리의 높이는 log2n 이므로 재구축의 계산시간은 O(log n)이 된다. 데이터 추가도 마찬가지이다.

추출	추가
O(1)	O(log n)

Binary search tree

이진 탐색 트리(Binary search tree)는 그래프의 트리 구조를 사용한다.

이진 탐색 트리는 두 가지 성질을 지닌다. 첫 번째 성질은, 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다. 예를 들어, 노드 9는 그 왼쪽에 있는 가지의 모든 숫자(3, 8)보다 크다. 두 번째 성질은, 모든 노드는 그 노드의 오른쪽 가지에 포함되는 어떤 숫자보다 작은 숫자가 된다는 것이다. 예를 들어, 노드 15는 그 오른쪽 가지에 있는 어떤 수(23, 17, 28)보다 작다.

이 두 개의 성질로부터 다음 조건이 성립된다. 먼저, 이진 탐색 트리의 최소 노드는 최상단에 있는 노드로부터 왼쪽 가지만 계속 따라가면 나오는 가장 끝에 위치한 노드가 된다. 반대로 최대 노드는 최상단의 노드로부터 오른쪽 가지만 계속 따라가면 나오는 가장 끝에 위치한 노드가 된다.

1. 이진 탐색 트리에 1을 추가해보자.
2. 최상단 노드부터 탐색하자. 추가하려고 하는 1을 현재 노드 값과 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 진행한다. (1 < 15 이므로 왼쪽으로 진행)
3. 1 < 9 이므로 왼쪽으로 진행한다.
4. 1 < 3 이므로 왼쪽으로 진행해야 하지만 노드가 없으므로 새로운 노드를 추가한다.
5. 다음으로는 노드를 삭제해보자. 예를 들어 28을 삭제해 보자.
6. 자식 노드가 없는 노드는 대상 노드를 삭제만 하면 작업이 끝난다.
7. 다음으로는 9를 삭제해보자. 자식 노드가 두 개인 경우는 먼저 대상 노드를 삭제한다.
8. 삭제한 노드의 왼쪽 가지에서 최대 노드를 찾아 삭제한 노드의 위치로 이동시킨다. (9는 사라지고 8이 올라간다)

이진 트리의 탐색은 트리의 높이만큼만 비교하면 되므로 노드가 n개 있고 트리가 균형 잡힌 경우라면 최대 log2n 회의 비교로 이동할 수 있다. 단 트리가 한쪽으로 치우쳐서 직선에 가까운 모양인 경우에는 트리가 높아져서 O(n)이 될 수도 있다.

📎 참고자료

알고리즘 도감(도서)