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 array)를 통해서 일정 부분 해결할 수 있다. 크기를 1의 배열로 시작하여 공간이 모자랄 때마다 크기를 m에서 2m으로 두 배로 만드는 방식으로 동적 배열을 구현한다고 가정하자. 해당 과정에서 실제로 수행되는 작업의 양을 구하는 과정은 아래와 같다: