§ 1 · 출발점데이터를 조직한다는 것
컴퓨터 프로그램은 데이터를 받아들이고, 처리하고, 반환하는 일을 반복한다. 두 숫자를 더하는 간단한 프로그램이든 기업 전체를 운영하는 대규모 소프트웨어든 모두 데이터 위에서 동작한다.
자료구조(data structure)란 데이터가 어떻게 조직되어 있는지를 뜻한다. 다음 코드를 보자.
x = "Hello! " y = "How are you " z = "today?" print x + y + z
이 프로그램은 각각 변수가 가리키는 세 개의 독립적인 문자열을 다룬다. 이것이 이 데이터의 조직 방식이다. 이 책에서 배우게 될 핵심은, 데이터를 조직하는 방식이 단순한 정리 차원이 아니라 프로그램이 얼마나 빠르게 실행되는지에 큰 영향을 미친다는 사실이다.
이 장에서는 두 자료구조—배열(array)과 집합(set)—을 분석한다. 둘은 얼핏 거의 같아 보이지만, 성능 분석법을 배우고 나면 그 차이가 명확해진다.
§ 2 · 연산배열의 네 가지 연산
자료구조의 성능을 이해하려면, 코드가 그 구조와 상호작용하는 일반적인 방식—연산(operation)—을 분석해야 한다. 대부분의 자료구조는 네 가지 기본 연산으로 쓰인다.
읽기(read) — 자료구조의 특정 위치에서 값을 조회한다. 배열이라면 특정 인덱스의 값을 본다.
탐색(search) — 특정 값이 자료구조에 존재하는지, 어느 위치에 있는지 찾는다.
삽입(insert) — 새로운 값을 자료구조에 추가한다.
삭제(delete) — 자료구조에서 값을 제거한다.
배열의 인덱스(index)는 배열 내에서 데이터가 어디 있는지 가리키는 번호다. 대부분의 언어에서 인덱스는 0부터 시작한다. 쇼핑 목록 배열 ["apples", "bananas", "cucumbers", "dates", "elderberries"]에서 "apples"는 인덱스 0, "elderberries"는 인덱스 4에 있다.
컴퓨터의 메모리는 거대한 셀(cell)의 집합이다. 각 셀에는 고유한 메모리 주소가 있고, 각 주소는 이전 셀보다 정확히 1씩 크다. 배열을 선언하면 컴퓨터는 연속된 빈 셀 그룹을 할당한다. 이 사실이 곧 보게 될 읽기의 놀라운 속도를 만든다.
§ 3 · 1단계 vs N단계읽기와 탐색
배열에서 읽기는 단 1단계면 된다. 컴퓨터는 배열의 시작 메모리 주소를 알고, 인덱스가 0부터 시작한다는 것을 안다. 인덱스 3을 읽으라고 하면 컴퓨터는 이렇게 계산한다.
- 이 배열은 인덱스 0이 메모리 주소 1010이다.
- 인덱스 3은 0으로부터 정확히 3칸 뒤에 있다.
- 따라서 주소
1010 + 3 = 1013으로 한 번에 점프한다.
반면 탐색은 다르다. 컴퓨터는 눈이 없으므로, 어떤 값이 배열에 있는지 찾으려면 인덱스 0부터 한 칸씩 확인해야 한다. 이것을 선형 탐색(linear search)이라 한다.
§ 4 · 자리 만들기삽입과 삭제
삽입의 효율성은 어디에 넣느냐에 달렸다. 배열 끝에 추가하면 1단계로 끝난다. 그러나 시작이나 중간에 넣으려면, 자리를 만들기 위해 뒤쪽 데이터를 모두 오른쪽으로 밀어야 한다.
아래 모션에서 인덱스 2에 "figs"를 삽입해 보자. 세 개의 값을 오른쪽으로 옮긴 뒤에야 빈 자리에 새 값을 넣을 수 있다.
최악의 경우는 배열 시작에 삽입하는 것이다. 모든 N개 값을 옮긴 뒤 1번 삽입하므로 N + 1 단계가 든다. 삭제는 삽입의 반대다. 값 하나를 지우면 가운데 빈 셀이 생기고, 배열은 빈 공간을 허용하지 않으므로 뒤쪽 값들을 왼쪽으로 당겨 메워야 한다. 최악의 경우(첫 요소 삭제)는 N단계다.
| 연산 | 최선의 경우 | 최악의 경우 |
|---|---|---|
| 읽기 | 1단계 | 1단계 |
| 탐색 | 1단계 | N단계 |
| 삽입 | 1단계 (끝) | N+1단계 (시작) |
| 삭제 | 1단계 (끝) | N단계 (시작) |
§ 5 · 제약의 대가집합 — 하나의 규칙
집합(set)은 중복된 값을 허용하지 않는 자료구조다. 여기서 다루는 배열 기반 집합은 일반 배열과 똑같지만, 중복 값이 삽입되는 것을 절대 허용하지 않는다는 단 하나의 제약이 있다. 온라인 전화번호부처럼 같은 항목이 두 번 나타나면 안 되는 곳에 유용하다.
읽기·탐색·삭제는 배열과 집합이 동일하다. 그러나 삽입은 갈라진다. 집합은 중복을 막아야 하므로, 모든 삽입 전에 먼저 "이 값이 이미 있는가?"를 탐색해야 한다.
N + 1 단계가 든다(N단계 탐색 + 1단계 삽입). 최악의 경우(시작에 삽입)는 N단계 탐색 + N단계 이동 + 1단계 삽입 = 2N + 1 단계다. 집합의 안전함에는 속도라는 대가가 있다.
§ 6 · 정리이 장이 남긴 것
연산이 거치는 단계 수를 세는 것이 자료구조 성능 분석의 핵심이다. 올바른 자료구조 선택은 큰 부하를 견디느냐 무너지느냐를 가른다. 중복이 없어야 한다면 집합을, 빠른 삽입이 필요하다면 배열을 — 애플리케이션의 필요를 분석해 고르는 것이 엔지니어의 일이다.
다음 장에서는 같은 분석법으로 경쟁하는 알고리즘들을 비교한다.