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개의 항목을 저장할 메모리를 할당 받기까지는 번의 메모리 복사가 필요하다. 2. 인 어떤 j에서 마지막으로 삽입하면 한 번더 복사해야 한다.(n이 최악의 경우) 3. 1, 2에 따르면 복사 작업은 첫 번째/두 번째/네 번째.../n번째 삽입 후에 일어난다. 4. 이때 i 번째 삽입에서 메모리 복사 작업을 진행할 때, 총 메모리 복사 횟수는 이므로, 총 복사 횟수는:
따라서 n개의 각 원소는 배열에 차례되로 삽입될 때 평균적으로 단 두번만 접근된다. 따라서 동적 배열을 관리하는 총 작업량은 처음부터 충분히 큰 단일 배열을 미리 할당했을 때와 마찬가지로 O(n)이다. 동적 배열을 사용할 때의 단점은 각 삽입이 상수 시간에 이루어진다는 보장을 받지 못한다는 것이다. 모든 인덱스 접근과 대부분의 삽입은 빠르지만, 배열의 복사를 야기하는 소수의 삽입이 존재하기 때문이다. 하지만 그럼에도 n번째 원소 삽입까지 요구되는 시간 복잡도는 O(n^2)이라는 점에서 충분히 빠르다고 볼 수 있다.
Sentinels
삽입 정렬과 같은 알고리즘에서, 원소를 왼쪽으로 이동시키며 삽입할 때 검사하는 인덱스에 대한 경계 조건을 체크해야 한다.[1] 이러한 경계 조건의 체크는 코드를 복잡하게 만든다. 이러한 문제를 해결하기 위해서 감시자 원소(sentinel)를 사용한다. 이는 와 같이 비교에서 절대 선택되지 않을 값을 택하는 방식으로 구현된다. 예를 들어 삽입 정렬에서 배열의 왼쪽 끝에 와 같이 가짜 원소를 두어 경계 조건을 체크할 필요성을 없애는 것이다. 이는 코드를 더욱 깔끔하게 만들 수 있으며, 성능에도 영향을 주지 않아 권장되는 구현 방식 중 하나이다.
Pointers and Linked Structures
연결 자료구조(linked structure)는 기본적으로 아래와 같은 구조를 지닌다:
typedef struct list {
item_type item; /* data item */
struct list *next; /* point to successor */
} list;
위에서 연결 자료구조(list)의 각 노드는 데이터를 저장하는 하나 이상의 필드(item)를 포함한다. 또한 각 노드는 적어도 하나의 다른 노드(*next)에 대한 포인터 필드(next)를 포함한다. 마지막으로 연결 자료구조의 시작 노드(head)를 가리키는 포인터가 필요하다. 이러한 구조는 보통 연결 리스트(linked list)라고도 불리며, 가장 단순한 연결 자료구조에 속한다. 리스트가 지원하는 세 가지 기본 연산은 탐색, 삽입, 삭제이다.
Searching a List
연결 리스트에서 항목 x를 탐색하는 것은 반복적으로(iterative) 또는 재귀적으로(recursive) 할 수 있다. 본 문서에서는 재귀적인 탐색 방식을 다룬다. 이는 아래와 같이 구현된다.
list *search_list(list *l, item_type x) { // l은 현재 탐색을 시작할 노드를 가리킴
if (l == NULL) {
return(NULL);
}
if (l->item == x) {
return(l);
} else {
return(search_list(l->next, x));
}
}
Insertion into a List
리스트를 어떤 특정한 순서로 유지할 필요는 없기 때문에, 편리한 위치에 항목을 새로 삽입하면 된다. 이는 아래와 같이 구현된다.
void insert_list(list **l, item_type x) { //l은 리스트의 head 노드에 대한 포인터임을 나타냄
list *p; /* temporary pointer */
p = malloc(sizeof(list));
p->item = x;
p->next = *l;
*l = p;
}
Deletion From a List
연결 리스트에서 특정 노드를 삭제하는 것은 다소 복잡하다. 이를 구현하기 위해서는 먼저 삭제하고자 하는 노드를 가리키는 포인터를 찾아야 한다. 이는 아래와 같이 구현된다:
list *item_ahead(list *l, list *x) { //l은 리스트의 탐색할 한 노드, x는 삭제하고자 하는 노드의 주소
if ((l == NULL) || (l->next == NULL)) { //결국 찾지 못한 경우
return(NULL);
}
if ((l->next) == x) { // 찾고자 하는 노드를 찾았음
return(l);
} else { // 해당 노드는 찾고자 하는 노드가 아님
return(item_ahead(l->next, x));
}
}
- item_ahead() 함수는 삭제하고자하는 노드의 선행 노드(혹은 head)를 반환한다. 따라서 해당 선행 노드의 next 포인터(혹은 head 자체)를 변경해야 한다. 이는 아래와 같이 구현된다.
void delete_list(list **l, list **x) { // l은 탐색이 이뤄지는 연결 리스트, x는 삭제할 노드
list *p; /* item pointer */
list *pred; /* predecessor pointer */
p = *l;
pred = item_ahead(*l, *x); // 삭제할 노드의 선행 노드(혹은 head) 탐색
if (pred == NULL) { /* splice out of list */
*l = p->next;
} else {
pred->next = (*x)->next;
}
free(*x); /* free memory used by node */
}
각주
- ↑ j >= 0과 같은 조건을 의미한다. 즉, 빈 배열인지? 인덱스가 음수가 아닌지? 등을 확인하기 위한 것이다.
