Data Structures

상위 문서: 알고리즘 설계와 분석

개요

해당 문서에서는 알고리즘을 구현하기 위해서 사용되는 기초적인 자료구조들에 대해 살펴본다.

Contiguous vs. Linked Data Structures

자료구조는 그것들이 배열에 기반하는지 포인터에 기반하는지에 따라, 연속(contiguous) 또는 연결(linked) 자료구조로 분류될 수 있다. 연속적으로 할당된 자료 구조는 어떤 단일 메모리 덩어리로 구성되며, 배열(arrays), 행렬(matrices), 힙(heaps), 해시 테이블(hash tables)을 포함한다. 연결 자료구조는 포인터로 서로 묶인 여러 메모리 조각들로 구성되며, 리스트(lists), 트리(trees), 그래프 인접 리스트(graph adjacency lists)를 포함한다.

Arrays

배열은 연속 자료구조의 대표 주자이다. 배열은 고정된 크기의 데이터 레코드들로 이루어진 자료 구조이며, 각 원소는 해당 인덱스나 주소를 통해서 효율적으로 탐색될 수 있다. 배열의 장점은 아래와 같다:

• 인덱스가 주어졌을 때 해당 원소에 상수 시간에 접근할 수 있다.
• 공간 효율성: 배열은 순수하게 저장하는 데이터로만 이루어져 있으므로 포인터나 기타 서식 정보로 메모리가 낭비되지 않는다.
• 메모리 지역성(locality): 많은 프로그래밍 작업은 자료구조의 모든 원소를 순회(iterate)하는데, 이때 메모리 지역성이 높다면 캐시(Cache)가 더욱 활용되어 프로그램의 속도가 빨라진다.

하지만 배열의 단점은 프로그램의 실행 도중 그 크기를 조절할 수 없다는 것이다. 만약 우리가 n개의 레코드만을 위한 공간을 할당했는데 (n+1)번째 고객을 추가하려 하면 프로그램은 곧바로 실패한다. 매우 큰 배열을 잡아두는 것으로 보완할 수 있으나, 이는 공간을 낭비하여 다시금 프로그램이 할 수 있는 일을 제한한다.

Dynamic Arrays

사실 이러한 단점은 동적 배열(dynamic array)를 통해서 일정 부분 해결할 수 있다. 크기를 1의 배열로 시작하여 공간이 모자랄 때마다 크기를 m에서 2m으로 두 배로 만드는 방식으로 동적 배열을 구현한다고 가정하자. 이는 크기 2m의 새로운 연속 배열을 할당하고, 기존 배열의 내용을 새 배열의 첫 절반 부분에 복사한 후, 기존 배열이 점유한 메모리를 반환하여 이루어진다. 해당 과정에서 실제로 수행되는 작업의 양을 구하는 과정은 아래와 같다:

1. 배열이 n개의 항목을 저장할 메모리를 할당 받기까지는 $\lceil lo{g}_2(n)\rceil$번의 메모리 복사가 필요하다. 
2. $n=2^j$인 어떤 j에서 마지막으로 삽입하면 한 번더 복사해야 한다.(n이 최악의 경우)
3. 1, 2에 따르면 복사 작업은 첫 번째/두 번째/네 번째.../n번째 삽입 후에 일어난다. 
4. 이때 i 번째 삽입에서 메모리 복사 작업을 진행할 때, 총 메모리 복사 횟수는 $2^{i-1}$이므로, 총 복사 횟수는:
$M=n+\sum _{i=1}^{lo{g}_2(n)}{2}^{i-1}=1+2+4+8+\cdots +n+n=\sum _{i=0}^{lo{g}_2(n)}\frac{n}{2^i}\le n\sum _{i=0}^{\mathrm{\infty }}\frac{1}{2^i}=2n$

따라서 n개의 각 원소는 배열에 차례되로 삽입될 때 평균적으로 단 두번만 접근된다. 따라서 동적 배열을 관리하는 총 작업량은 처음부터 충분히 큰 단일 배열을 미리 할당했을 때와 마찬가지로 O(n)이다. 동적 배열을 사용할 때의 단점은 각 삽입이 상수 시간에 이루어진다는 보장을 받지 못한다는 것이다. 모든 인덱스 접근과 대부분의 삽입은 빠르지만, 배열의 복사를 야기하는 소수의 삽입이 존재하기 때문이다. 하지만 그럼에도 n번째 원소 삽입까지 요구되는 시간 복잡도는 O(n^2)이라는 점에서 충분히 빠르다고 볼 수 있다.

Sentinels

삽입 정렬과 같은 알고리즘에서, 원소를 왼쪽으로 이동시키며 삽입할 때 검사하는 인덱스에 대한 경계 조건을 체크해야 한다. 이러한 경계 조건의 체크는 코드를 복잡하게 만든다. 이러한 문제를 해결하기 위해서 감시자 원소(sentinel)를 사용한다. 이는 $\pm \mathrm{\infty }$와 같이 비교에서 절대 선택되지 않을 값을 택하는 방식으로 구현된다. 예를 들어 삽입 정렬에서 배열의 왼쪽 끝에 $-\mathrm{\infty }$와 같이 가짜 원소를 두어 경계 조건을 체크할 필요성을 없애는 것이다. 이는 코드를 더욱 깔끔하게 만들 수 있으며, 성능에도 영향을 주지 않아 권장되는 구현 방식 중 하나이다.