자료구조 설명

모든 프로그램은 데이터를 어딘가에 담아 두며, 그 방식이 무엇이 빠르고 무엇이 느린지를 정합니다. 이름 백만 개가 든 목록은 이름 하나하나를 차례로 훑을 수도 있고, 어떤 이름이든 스무 번의 비교로 찾도록 정리해 둘 수도 있습니다. 자료구조는 바로 그런 정리 방식입니다. 대부분 개인용 컴퓨터보다 오래된 몇 가지 아이디어가 모든 데이터베이스, 운영체제, 브라우저, 게임 안에 들어 있습니다.

빨간색과 검은색으로 칠한 이진 탐색 트리, 상자를 쌓은 스택, 충돌한 키들이 사슬로 이어진 해시 버킷 줄, 리스트의 노드를 잇는 화살표
빨간색과 검은색으로 칠한 이진 탐색 트리, 상자를 쌓은 스택, 충돌한 키들이 사슬로 이어진 해시 버킷 줄, 리스트의 노드를 잇는 화살표

자료구조는 무엇에 쓰이나

자료구조는 답해야 할 질문에 따라 고릅니다. 휴대폰의 통화 기록은 가장 최근 통화를 먼저, 프린터의 작업은 가장 오래된 것을 먼저, 사전은 십만 단어 중 한 단어의 뜻을, 길 찾기는 아직 가지 않은 가장 가까운 교차로를 필요로 합니다. 각 구조는 어떤 연산을 빠르게 하는 대신 다른 연산을 포기하며, 빅오 표기법이 그 거래를 나타냅니다. O(1)은 원소 수 n이 늘어도 시간이 늘지 않음을, O(log n)은 n이 두 배가 되면 한 단계가 더해짐을, O(n)은 시간이 n에 비례해 늘어남을 뜻합니다.

스택, 큐, 덱

스택은 같은 끝에서 넣고 뺍니다. 나중에 들어온 것이 먼저 나갑니다. 실행 취소 기록, 뒤로 가기 버튼, 실행 중인 프로그램의 함수 호출이 스택입니다. 큐는 뒤에 넣고 앞에서 뺍니다. 먼저 들어온 것이 먼저 나가며, 키보드 입력이나 인쇄 대기열이 그 예입니다. 덱은 양쪽 끝에서 둘 다 할 수 있습니다. 세 가지 모두 연산 한 번에 상수 시간이 걸립니다. 큐는 흔히 원형 버퍼에 담깁니다. 고정된 배열에서 앞과 뒤가 마지막 칸을 지나면 처음으로 돌아오고, 가득 차면 원소들을 두 배 크기의 배열로 복사합니다. 복사에는 O(n)이 들지만 아주 드물게 일어나므로 연산 한 번은 평균적으로 여전히 O(1)이며, 이를 분할 상환 한계라고 합니다.

연결 리스트

연결 리스트는 각 값을 다음 노드를 가리키는 포인터와 함께 노드에 담습니다. 삽입이나 삭제는 포인터 한두 개만 바꾸면 되고 아무것도 옮길 필요가 없지만, 열 번째 노드로 곧장 건너뛸 수는 없습니다. 헤드부터 링크를 따라가야 합니다. 헤드만 아는 리스트는 꼬리까지 O(n)단계가 걸립니다. 실제 리스트는 보통 꼬리 포인터도 두고, 이중 연결 리스트는 뒤로 가는 포인터도 둡니다. 브라우저 방문 기록이나 LRU 캐시가 이렇게 만들어집니다.

이진 탐색 트리

이진 탐색 트리는 각 노드에서 작은 값을 왼쪽 서브트리에, 큰 값을 오른쪽 서브트리에 둡니다. 검색은 비교한 뒤 왼쪽이나 오른쪽으로 가고, 중위 순회는 값을 정렬된 순서로 읽습니다. 잎을 지우는 것은 그냥 떼어 내는 것이고, 자식이 하나인 노드는 그 자식으로, 자식이 둘인 노드는 중위 후속자, 즉 오른쪽 서브트리의 가장 작은 값으로 바꿉니다. 이 모든 일은 트리 높이에 비례하는 시간이 걸립니다. 트리가 무성하면 대략 log n이지만, 값이 정렬된 순서로 들어와 트리가 리스트로 퇴화하면 n이 됩니다.

AVL 트리와 레드-블랙 트리

자가 균형 트리는 바뀔 때마다 모양을 고칩니다. 1962년 아델슨-벨스키와 란디스가 만든 AVL 트리는 모든 노드의 두 서브트리 높이 차이를 1 이내로 유지합니다. 어떤 노드의 균형 인수가 ±2가 되면 회전 한 번(LL, RR 경우)이나 두 번(LR, RL)으로 균형을 되찾습니다. 레드-블랙 트리는 루트가 검은색이고, 빨간 노드가 빨간 자식을 갖지 않으며, 아래로 가는 모든 경로가 같은 수의 검은 노드를 지나도록 노드를 칠합니다. 그래서 가장 긴 경로가 가장 짧은 경로의 두 배를 넘지 않습니다. 다시 칠하기와 많아야 몇 번의 회전으로 스스로를 고치며, 자바의 TreeMap, C++의 std::map, 리눅스 스케줄러 안에 있는 트리가 바로 이것입니다.

힙과 우선순위 큐

이진 힙은 포인터 없이 배열에 담은 완전 이진 트리입니다. 위치 i의 자식은 2i + 1과 2i + 2에 있습니다. 최소 힙에서는 모든 부모가 자식보다 크지 않으므로 가장 작은 값이 언제나 루트에 있습니다. 새 값은 끝에 놓인 뒤 더 큰 부모를 지나 위로 올라가고, 루트를 꺼내면 마지막 값이 맨 위로 옮겨져 아래로 내려갑니다. 둘 다 O(log n)이며, 배열 전체를 O(n)에 힙으로 만들 수 있습니다. 힙은 다익스트라 최단 경로, 이벤트 시뮬레이션, 운영체제 스케줄러의 우선순위 큐를 움직이고, 힙 정렬도 만들어 냅니다.

해시 테이블

해시 테이블은 해시 함수로 키를 배열 인덱스로 바꾼 뒤 곧장 그곳으로 갑니다. 서로 다른 키가 같은 인덱스에 떨어질 수 있는데, 이것이 충돌입니다. 체이닝은 버킷마다 작은 리스트를 둡니다. 선형 탐사 같은 개방 주소법은 빈칸을 찾을 때까지 다음 칸을 시도하며, 키를 지울 때는 나중의 검색이 계속 탐사하도록 묘비를 남겨야 합니다. 좋은 해시 함수를 쓰고 테이블을 키워 적재율(버킷당 키 수)을 낮게 유지하면 삽입, 검색, 삭제는 평균 O(1)입니다. 단어의 문자 코드를 더하는 것 같은 나쁜 함수는 애너그램을 같은 버킷에 보냅니다. 파이썬의 dict, 자바스크립트 객체, 데이터베이스 인덱스 뒤에는 해시 테이블이 있습니다.

트라이와 유니온-파인드

트라이, 즉 접두사 트리는 문자열을 한 층에 한 글자씩 저장하므로, 시작이 같은 단어는 경로를 공유하고 노드가 단어가 끝나는 곳을 표시합니다. 길이 L인 단어를 찾는 데는 저장된 단어 수와 상관없이 L단계가 걸리며, 어떤 접두사로 시작하는 단어는 모두 한 서브트리에 있습니다. 자동 완성과 맞춤법 검사기가 이렇게 동작합니다. 유니온-파인드는 원소를 서로소 집합으로 나누어 두며, 각 집합은 루트가 집합을 대표하는 트리입니다. Find는 부모 링크를 루트까지 따라가고, Union은 한 루트를 다른 루트 아래에 매답니다. 랭크 기준 합치기와 경로 압축을 쓰면 긴 연산 순서에서 연산 한 번의 비용이 거의 상수, 즉 역 아커만 함수 α(n)이 되며, 현실적인 어떤 n에서도 4를 넘지 않습니다. 최소 신장 트리를 구하는 크루스칼 알고리즘이 여기에 기댑니다.

자주 묻는 질문

배열과 연결 리스트는 무엇이 다른가요?

배열은 원소를 메모리에 나란히 두므로 어느 위치든 곧바로 닿지만, 중간에 넣으려면 그 뒤의 모든 것을 옮겨야 합니다. 연결 리스트는 포인터를 바꿔 어디에든 넣을 수 있지만, 어떤 위치에 닿으려면 헤드부터 걸어가야 합니다. 배열은 프로세서 캐시도 훨씬 잘 활용하므로 실제로는 대개 더 빠릅니다.

분할 상환 시간이란 무엇인가요?

개별 연산이 가끔 비싸더라도, 긴 연산 순서 전체에서 연산 한 번에 드는 평균 비용입니다. 가득 차면 두 배로 커지는 원형 버퍼는 가끔 원소 n개를 모두 복사하지만, 버퍼가 커질수록 복사가 드물어지므로 추가 n번에 드는 비용은 합해서 O(n), 즉 평균 한 번에 O(1)입니다.

힙은 이진 탐색 트리와 같은 것인가요?

아니요. 이진 탐색 트리는 모든 왼쪽 서브트리를 그 노드 앞에, 모든 오른쪽 서브트리를 뒤에 두므로 모든 값을 순서대로 나열하고 어떤 값이든 빨리 찾을 수 있습니다. 힙은 모든 부모가 자식보다 앞에 온다는 것만 약속합니다. 이것으로 최솟값이나 최댓값은 바로 찾을 수 있지만, 임의의 값을 찾기에는 부족합니다.

유니온-파인드는 두 원소가 연결되었는지 어떻게 아나요?

각 원소에서 부모 링크를 따라 트리의 루트까지 갑니다. 둘이 같은 루트에 닿으면 같은 집합입니다. 그 뒤 경로 압축이 경로 위의 모든 노드가 루트를 곧바로 가리키게 하므로, 다음에 같은 질문을 하면 한 단계면 됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

자료구조 시각화 열기