알고리즘과 자료구조 3강. 데이터를 어떻게 담을 것인가

같은 알고리즘이 어떤 그릇에서는 순식간에 끝나고 어떤 그릇에서는 하루 종일 돕니다. 자료구조는 데이터를 담는 방식이 아니라 무엇을 싸게 만들지 고르는 선택입니다.

풀고 시작

나란히 놓을 것인가 끈으로 이을 것인가

배열(array)은 같은 크기의 칸을 메모리에 나란히 붙여 놓은 구조입니다. 첫 칸의 주소에 번호와 칸 크기를 곱해 더하면 원하는 칸의 주소가 곧바로 나오니, 1만 번째 원소를 읽는 데도 계산 한 번이면 충분합니다. 대신 중간에 하나를 끼워 넣으려면 뒤의 원소를 전부 한 칸씩 밀어야 하죠. 연결 리스트(linked list)는 정반대입니다. 각 원소가 값과 함께 다음 원소의 위치를 들고 있어서 흩어져 있어도 상관없고, 삽입은 고리 두 개를 고쳐 매면 끝납니다. 대신 다섯 번째 원소를 보려면 처음부터 다섯 번 따라가야 합니다. 여기서 교과서가 덜 강조하는 사실을 하나 덧붙이겠습니다. 현대 컴퓨터는 메모리를 읽을 때 주변 데이터를 묶어서 캐시에 올려 두기 때문에, 이론상 삽입이 빠른 연결 리스트가 실제 측정에서는 배열에 지는 경우가 흔합니다. 자료구조의 성능은 연산 횟수만이 아니라 메모리가 실제로 어떻게 읽히는지에도 달려 있습니다.

일부러 손발을 묶는 구조

스택(stack)과 큐(queue)는 기능을 늘린 것이 아니라 오히려 줄인 구조입니다. 스택은 마지막에 넣은 것을 먼저 꺼내고(후입선출), 큐는 먼저 넣은 것을 먼저 꺼냅니다(선입선출). 아무 데나 손대지 못하게 막았을 뿐인데, 그 제약이 곧바로 쓸모가 됩니다. 함수가 다른 함수를 부르고 돌아올 자리를 기억하는 호출 스택, 편집기의 실행 취소, 수식의 괄호 짝 검사는 전부 스택입니다. 프린터 대기열, 메시지 처리, 그래프를 가까운 곳부터 넓게 훑는 탐색은 큐죠. 재귀 호출이 너무 깊어질 때 나는 스택 오버플로 오류도 이 구조를 알면 바로 이해됩니다. 돌아갈 자리를 쌓아 두는 공간이 바닥난 것이니까요.

열쇠를 주소로 바꾸는 마법

이름으로 전화번호를 찾는다고 해 봅시다. 배열을 처음부터 훑으면 느리고, 정렬해 두고 이진 탐색을 해도 로그 시간이 듭니다. 해시 테이블(hash table)은 아예 발상을 바꿉니다. 이름을 해시 함수에 넣어 숫자 하나를 뽑고, 그 숫자를 배열의 칸 번호로 씁니다. 찾을 때도 같은 계산을 한 번 하면 바로 그 칸입니다. 훑지 않으니 데이터가 백만 개든 천만 개든 평균 상수 시간이죠. 문제는 서로 다른 이름이 같은 칸으로 떨어지는 충돌입니다. 그리고 충돌은 재수가 없어서가 아니라 반드시 일어납니다. 가능한 이름은 무한한데 칸은 유한하니 비둘기집 원리에 따라 피할 길이 없죠. 그래서 같은 칸에 작은 리스트를 매달아 두거나(체이닝), 다음 빈칸을 찾아 밀어 넣는(개방 주소법) 방식으로 처리합니다. 여기서 정직하게 짚을 점이 있습니다. 해시 테이블의 상수 시간은 평균입니다. 값이 한 칸에 몰리면 최악에는 리스트를 훑는 것과 다를 바 없어지고, 이 성질을 악용해 서버를 마비시키는 공격이 실제로 보고된 적이 있습니다. 그래서 실제 언어 런타임은 해시 함수에 무작위 값을 섞어 공격자가 충돌을 미리 계산하지 못하게 막습니다.

가지를 치며 절반씩 버리기

이진 탐색 트리(binary search tree)는 각 노드의 왼쪽에는 작은 값, 오른쪽에는 큰 값을 두는 규칙 하나로 만들어집니다. 찾을 값을 노드와 비교해 한쪽 가지로 내려가면 나머지 절반이 통째로 사라지니, 정렬된 배열의 이진 탐색을 삽입과 삭제까지 되는 형태로 옮겨 놓은 셈이죠. 그런데 함정이 있습니다. 이미 정렬된 데이터를 순서대로 넣으면 트리가 한쪽으로만 자라 사실상 연결 리스트가 되고 장점이 전부 사라집니다. 그래서 삽입할 때마다 모양을 스스로 고쳐 높이를 로그 규모로 유지하는 균형 트리가 나왔습니다. 1962년 아델손벨스키와 란디스가 제안한 AVL 트리가 최초이며, 레드블랙 트리는 오늘날 여러 표준 라이브러리의 정렬된 자료구조를 떠받치고 있습니다. 데이터베이스와 파일 시스템은 한 노드에 원소를 여러 개 담아 디스크 읽기 횟수를 줄이는 B 트리 계열을 씁니다. 트리의 모양이 곧 성능이라는 사실이 여기서 분명해집니다.

연결 자체가 데이터일 때

관계가 나무처럼 위아래로만 뻗지 않을 때, 그러니까 지하철 노선이나 친구 관계처럼 아무나 아무와 이어질 때 필요한 것이 그래프입니다. 담는 방법은 둘입니다. 정점 수만큼의 정사각 표를 만들어 이어짐을 표시하는 인접 행렬은 두 정점이 이어졌는지 즉시 알 수 있지만 정점 수의 제곱만큼 공간을 먹습니다. 각 정점마다 이웃 목록을 매다는 인접 리스트는 연결이 희박한 현실의 망에 훨씬 알맞죠. 순회 방법도 둘인데, 한 방향으로 끝까지 파고들었다가 되돌아오는 깊이 우선 탐색은 스택으로, 가까운 곳부터 층층이 훑는 너비 우선 탐색은 큐로 구현됩니다. 앞 절에서 만든 두 구조가 여기서 정확히 제 몫을 하는 것입니다. 그래프 자체의 수학은 이산수학의 그래프 이론에서 다뤘습니다. 다음 강에서는 이 모든 선택을 비교할 공통 자를 세웁니다.

인출 문제

이전: 알고리즘과 자료구조 2강 · 다음: 알고리즘과 자료구조 4강