[Algorithm] 선형 자료 구조

선형 자료구조는 데이터를 1차원으로 저장하는 가장 기본적인 형태이다. 그 구현 형태인 동적 배열과 연결 리스트에 대해 알아본다.

동적 배열

배열은 선언할 때 크기가 고정되고, 그 크기를 벗어날 수 없다는 단점을 가지는데 이러한 점을 자료의 개수에 따라 크기가 조절되도록 고안된 것이 동적 배열이다.

배열의 기본적인 특징

• 원소들이 메모리의 연속된 위치에 저장된다.
• 특정 위치의 원소를 반환, 변경하는 연산을 O(1)에 할 수 있다.

동적 배열만이 가지는 특징

• 배열의 크기를 변경하는 resize() 연산을 제공하며 O(N)에 할 수 있다.
• 배열의 마지막에 원소를 추가하는 append() 연산을 지원하며, O(1)에 할 수 있다.

resize() 작업은 단순히 더 큰 크기를 가지는 배열을 새롭게 선언하고 기존의 데이터를 복사하는 작업이다. 동적 배열 객체는 아래와 같은 정보를 가지고 있어야 한다.

int size; // 배열 크기
ElementType* array; // 실제 배열을 가리키는 포인터

append() 연산은 어떻게 동작할까? 동적 배열이 항상 데이터의 수와 같은 크기를 가지고 매 번 resize()를 호출한다면 결국 연산의 비용은 O(N)이 든다.

이를 해결하기 위한 전략은, 메모리를 할당받을 때 메모리 크기를 미리 넉넉하게 받아두는 것이다. 그렇다면 append() 연산은 아래와 같이 간단하게 구현될 수 있다.

array[size++] = newValue;

하지만 데이터의 수가 고정되어 있지 않다는 점에서 미리 할당해둔 capacity를 초과하는 시점은 반드시 온다. 이 때는 resize() 연산이 들어가야한다.

if(size == capcaity){
	int newCapacity = capacity + M;
	int * newArray = new int[newCapacity];

	// 기존 데이터 카피
	for(int i = 0 ; i < size ; i++) newArray[i] = array[i];

	// 기존 배열 삭제
	if(array) delete[] arr;
	
	// 배열 정보 교체
	array = newArray;
	capacity = newCapacity;
}

각 언어의 표준 라이브러리에서 제공되며, cpp의 vector, java의 ArrayList가 여기에 속한다.

동적 배열 메모리 할당 전략

위의 연산에서 M이 여분의 크기라고 할 수 있다. 여기서 M은 상수가 아니다.

만약 M을 그냥 상수 100이라고 하고, 크기가 1만인 배열을 만든다고 가정했을 때 resize()는 100 단위로 일어난다. 그에 따라 크기 1만인 배열을 만들기 위한 copy 연산 수는, 아래와 같이 범죄 행위에 준한다.

$ 100 + 200 + 300 + … + 9900 = 495,000 $

M을 상수로 잡을 시 copy 연산 수는 아래와 같으며 append()를 상수 시간에 구현할 수 없다.

$ M + 2M + 3M + … + K*M = O(K^2) = O(N^2) $

일반적으로 M은 현재 크기에 비례하여 잡으며 2배로 많이 구현된다. 이러한 전략으로 구현한다면, 데이터 크기와 같은 O(N)으로 구현 가능하다.

재할당 시점	1	2	4	8	16	…	2048	4096	8192
새 배열 크기	2	4	8	16	32	…	4096	8192	16348

연결 리스트

배열 원소의 순서를 유지하면서 중간에 데이터를 삽입하거나, 데이터를 삭제하는 것은 오래 걸리는 작업이다. 연산 위치보다 뒤에 있는 모든 데이터를 이동시키는 작업이 필요하기 때문이다.

하지만, 연결 리스트는 특정 위치에서의 삽입과 삭제를 O(1)에 할 수 있다는 특징을 가지며 구조는 아래와 같다.

struct ListNode{
	int element; // 값
	ListNode * prev; // 이전 노드
	ListNode * next; // 다음 노드
}

삽입과 삭제를 빠르게할 수 있지만, 배열과는 반대로 메모리가 연속적이지 않기 때문에 특정 위치의 원소를 찾는 작업이 처음부터 따라가며 찾아야하며 이는 결국 O(N)의 비용이 든다.

각 언어의 표준 라이브러리에서 제공되며, cpp의 list, java의 LinkedList가 여기에 속한다.

동적 배열과 연결 리스트 비교

배열의 중간에서 삽입과 삭제가 너무 빈번하게 일어나지 않는 경우, 동적 배열이 항상 더 좋은 선택이다. 메모리에 연속해 배치되어 있다는 점이 CPU 캐시의 효율도 더 높다.

작업	동적 배열	연결 리스트
이전 원소/다음 원소 탐색	O(1)	O(1)
맨 뒤에 원소 추가/삭제	O(1)	O(1)
맨 뒤 이외 위치에 원소 추가/삭제	O(n)	O(1)
임의의 취이 원소 찾기	O(1)	O(n)
크기 구하기	O(1)	O(n)

참고

• 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략