[MIT 6.006] 2. Data Structures and Dynamic Arrays

인공·2025년 10월 28일

Algorithms

목록 보기

2/3

이 글은 MIT 6.006 의 강의 내용을 기반으로 작성되었습니다.

Data Stucture and Interface

이전 강의에서는 알고리즘, 즉 문제를 정확하고 효율적이게 해결하는 방법이라는 것을 알았다. 이번 강의에서는 이러한 문제를 실제로 해결하기 위해 필요한 개념인 Interface와 Data structure에 대해서 다룬다.

1. Interface

: 문제가 주어졌을때 이 문제를 구체화 시키는 과정을 정의하는 것이다.

어떤 자료구조가 어떤 연산을 수행해야하는지를 설명해놓은 것이다. 즉 Specificiation 이자 이전 챕터의 problem
- 어떤 종류를 저장할지에 대해서 정의
- 어떤 연산을 수행할지와 의미를 정의
이번 강의에서는 Sequence 랑 Set interface에 대해서 살펴볼 것 이다.
- Sequence : extrinsic order item, 즉 순서는 외부적인 순서를 사용한다.
- Set : intrinsic order item. 즉 순서는 내부적으로 정해진다.

2. Data structure

: interface를 기반으로 실제로 해결과정을 구현하는 것이다.

실제로 이 Interface를 구체화하는 representation의 역할을 한다. 이전 챕터의 solution에 해당한다.
- 데이터를 저장하는 방법
- 연산들을 수행할 알고리즘

interface : 문제 해결 설명서(정의)

data structure : 문제 해결 실제 구현

Sequence Interface

순서가 있는 item들에 대해 정의한 연산들, 즉 문제 해결 정의 interface는 다음과 같은 것들이 있을 수 있다.

그리고 이러한 sequence interface의 자료구조 data structure로는 아래와 같이 두가지가 있다.
1. static sequence interface를 위한 static data structure
2. dynamic sequence interface를 위한 dynamic data structure
각각의 자료구조에 대해서 자세히 살펴보자

Static data structure

Static Array

: 아래와 같이 static sequence interface를 수행하기 가장 효율적인 static data structure는 static array이다. static array는 처음 선언될 때 크기가 정해져있고 메모리 상에서 연속된 주소공간을 할당받는다.

Static array는 연속적인 메모리 공간을 할당 받기 때문에 $array[i]=memory[address(array)+i]$
=> $A[i]=x$ 처럼 index $i$ 를 통해 바로 원소에 접근 가능하다.
get_at(i),set_at(i,x)는 따라서 원소에 바로 접근하므로 $O(1)$ 시간이 걸린다.
하지만 iter_seq(), build(x)와 같이 array를 새로 만들거나 하나씩 반환해야 한다면 모든 원소를 처리해야 하므로 $O(n)$ 시간이 걸린다.

만약, insert_last(x) 라는 daynamic sequence iteration을 static array로 수행하게 된다면 시간복잡도는 어떻게 될까?

흔히 배열 뒤에 원소를 하나 붙이는거니까 $$ O(1) $$ 이라고 생각할 수 있다. 하지만 static array는 처음 생성될 때 크기가 정해진다는 것을 잊으면 안된다.

따라서 insert_last(x)를 수행하기 위해서는 현재 배열의 2배 사이즈의 배열을 만들고 원래 있던 원소들을 복사해야된다.

이는 매우 비효율적인 해결책이 된다.

Dynamic data structure

위 와 같은 문제가 발생하기 때문에 dynamic sequence interface operation에서는 dynamic data structure를 사용하는 것이 더 효율적으로 연산된다. 이에 대해 더 자세히 살펴보자.

Linked List

연결 리스트는 대표적인 dynamic data structure 중 하나로 포인터 자료구조이다. 각 아이템은 node에 저장이 되고 이 node는 그 다음 node를 포인터로 가르키게 된다.

linked list image
(출처 : https://www.geeksforgeeks.org/dsa/linked-list-data-structure)

insert_last() 와 같은 dynamic sequence interface의 연산의 경우에는 새로 들어가는 노드의 pointer와 이전 노드의 pointer만 잘 연결해주면 된다. 즉 시간복잡도는 $\Theta(1)$ 이다.
다만, static data structure와 다르게 static sequence interface operation, get_at(i), set_at(i) 같은 경우에는 static array처럼 인덱스로 접근 할 수 없고, 첫번째 노드부터 포인터가 가르키는 다음 노드를 순차적으로 방문해서 i번째 요소를 찾을 수 있기 때문에 시간복잡도는 $O(n)$ 이다.

Dynamic Array

동적 배열은 링크드 리스트와 정적 배열의 장점을 합친 자료구조로 배열기반으로 크기를 자동으로 조절할 수 있는 자료구조이다.

일반 배열처럼 연속적인 메모리 공간을 사용하지만, 원소를 추가하다가 공간이 꽉 차면 더 큰 배열로 복사해 자동 확장한다
python의 list, C++ vector가 동적배열이다.

Amortized Analysis

보통 동적 배열은 확장할때 현재 크기의 2배로 확장한다. 왜 2 배라는 값을 사용하게 되었는지 살펴보자.

동적배열은 꽉 차면 새로운 배열을 만들고, 기존 데이터를 모두 복사해야된다. 즉 다음과정이 반복된다.

capacity = 1 → 2 → 4 → 8 → 16 → …

이때 중요한 건:

너무 자주 복사하면 느려짐 (성능 저하)
너무 많이 늘리면 메모리를 낭비함

그래서 “몇 배로 늘릴지”는 성능과 메모리 효율의 트레이드오프(Trade-off) 문제이다.

ex ) 2배로 늘리게 된다면 아래와 같은 연산과정을 거친다.

capacity 1 → 2 : 1개 복사
capacity 2 → 4 : 2개 복사
capacity 4 → 8 : 4개 복사
capacity 8 → 16 : 8개 복사
capacity 16 → 32 : 16개 복사 $\\$
복사 비용(총 n개의 원소) = $1+2+4+8+16+⋯+$ (가장 큰 값은 대략 n/2 정도)
$n = 2^k$ 이므로 아래와 같은 등비수열의 합으로 나타낼 수 있다.
= $1+2+4+⋯+2^k=2^{k+1}1$
= $\Theta(2^{k+1}-1) = \Theta(2n-1) = \Theta(n)$