📚 지식 노트

배열과 동적 배열

배열(array)은 같은 크기의 칸을 메모리에 빈틈없이 이어 붙인 것이다. 칸 크기와 시작 주소만 알면 i번째 칸의 주소는 시작 + i × 칸 크기로 곧장 나온다. 그래서 몇 번째 칸이든 읽고 쓰는 데 O(1)이다. 이것을 임의 접근(random access)이라 한다. 칸이 붙어 있으니 훑을 때 캐시도 잘 맞는다(복잡도와 기초 노트의 캐시 지역성 절).

대가는 크기다. 고정 배열은 만들 때 크기를 정해야 하고, 가운데에 값을 넣거나 빼려면 그 뒤의 값을 모두 한 칸씩 밀거나 당겨야 해서 O(n)이 든다. 메모리를 직접 들여다보면 이 배치가 그대로 보인다(헥스 뷰어).

동적 배열(dynamic array)은 크기 문제를 푼다. 실제로 잡아 둔 칸 수(capacity)와 쓰는 칸 수(size)를 따로 들고, 가득 차면 두 배쯤 큰 배열을 새로 잡아 옮긴다. 끝에 넣기는 분할 상환 O(1)이다(증명은 복잡도와 기초 노트의 분할 상환 절). C++ vector, Java ArrayList, 파이썬 list, JavaScript 배열이 모두 이 구조다. 주의할 점은 늘어날 때 주소가 바뀐다는 것이다. 늘기 전에 받아 둔 포인터나 참조는 옛 메모리를 가리키게 된다.

문제 풀기 →Python 코드 →

연결 리스트

연결 리스트(linked list)는 값을 노드(node)에 하나씩 담고, 노드마다 다음 노드의 주소(next 포인터)를 적어 줄줄이 잇는다. 노드는 메모리 어디에 있어도 된다. 그래서 어떤 노드를 가리키고 있기만 하면 그 뒤에 넣거나 빼는 일이 포인터 한두 개를 바꾸는 O(1)이다. 다른 값은 한 칸도 옮기지 않는다.

대가는 찾기다. i번째 노드에 가려면 head부터 i번 걸어야 하니 접근이 O(n)이다. "O(1)에 넣는다"는 말은 넣을 자리를 이미 쥐고 있을 때의 이야기이고, 값으로 자리를 찾는 데는 여전히 O(n)이 든다. 노드마다 포인터 공간이 더 들고, 노드가 흩어져 있어 훑기가 배열보다 몇 배 느리다.

단일 연결 리스트(singly linked list)는 앞으로만 갈 수 있어, 어떤 노드를 지우려면 그 앞 노드를 알아야 한다. 이중 연결 리스트(doubly linked list)는 노드에 prev 포인터를 하나 더 두어 양쪽으로 걷는다. 노드 하나만 쥐고 있어도 바로 떼어 낼 수 있고, 꼬리(tail)를 들고 있으면 끝에 넣기·빼기도 O(1)이다.

실무에서 연결 리스트가 빛나는 곳은 "노드를 쥔 채로 자주 떼었다 붙이는" 경우다. 운영체제의 작업 큐, 메모리 할당기의 빈 블록 목록, 그리고 해시 표와 이중 연결 리스트를 묶은 LRU 캐시(더 나아가기 노트)가 그렇다. 그냥 값을 모아 두고 훑는 용도라면 거의 언제나 동적 배열이 빠르다.

문제 풀기 →Python 코드 →

스택: 마지막에 넣은 것부터

스택(stack)은 한쪽 끝에서만 넣고(push) 꺼내는(pop) 자료구조다. 마지막에 넣은 것이 먼저 나오는 후입선출(LIFO, last in first out)이다. 동적 배열의 끝을 쓰면 두 연산 모두 O(1)이고, 맨 위를 꺼내지 않고 보기만 하는 peek도 O(1)이다.

"가장 최근에 열린 것을 먼저 닫는다"는 구조가 보이면 스택이다. 괄호 짝 맞추기가 대표 예다. 여는 괄호는 쌓고, 닫는 괄호를 만나면 맨 위와 짝이 맞는지 본다. 짝이 틀리거나, 꺼낼 것이 없거나, 끝에 남은 것이 있으면 틀린 괄호다. 글자를 한 번씩만 보니 O(n)이다.

같은 모양이 곳곳에 있다. 함수 호출은 호출 스택에 쌓이고(복잡도와 기초 노트의 재귀 절), 편집기의 되돌리기(undo)는 작업을 스택에 쌓았다가 꺼낸다. 브라우저의 뒤로 가기, 깊이 우선 탐색(DFS)을 반복문으로 쓸 때, 수식의 후위 표기 계산도 스택이다.

스택의 단골 응용이 단조 스택(monotonic stack)이다. "각 원소의 왼쪽에서 가장 가까운, 나보다 작은 값"을 모두 구한다고 하자. 왼쪽부터 훑으며 스택 맨 위가 지금 값 이상이면 계속 꺼내고, 남은 맨 위가 답이며, 마지막에 지금 값을 넣는다. 꺼낸 값은 지금 값에 가려 뒤의 어떤 원소의 답도 될 수 없기 때문이다. 이중 반복처럼 보여도 원소마다 한 번 넣고 많아야 한 번 꺼내므로 O(n)이다. 훑는 방향과 부등호만 바꾸면 "오른쪽에서 가장 가까운 큰 값"도 같은 방법으로 찾는다(Wikipedia의 All nearest smaller values).

문제 풀기 →Python 코드 →

큐와 덱

큐(queue)는 뒤(rear)로 넣고 앞(front)에서 꺼낸다. 먼저 온 것이 먼저 나가는 선입선출(FIFO, first in first out)이다. 차례를 지켜야 하는 곳, 곧 프린터 대기열, 네트워크 패킷 버퍼, 작업 스케줄러, 그리고 가까운 것부터 넓혀 가는 너비 우선 탐색(BFS)에 쓴다.

구현에 함정이 하나 있다. 동적 배열의 맨 앞을 지우면 나머지를 모두 당겨야 해서 O(n)이다. 파이썬에서 list.pop(0)을 큐처럼 쓰면 n개를 꺼내는 데 O(n²)이 든다. 앞 위치를 가리키는 인덱스를 따로 두거나(다음 절의 원형 버퍼), 연결 리스트로 만들면 두 연산 모두 O(1)이 된다.

면접에 자주 나오는 변형이 스택 두 개로 큐 만들기다. 넣을 때는 입력 스택에 쌓고, 꺼낼 때 출력 스택이 비어 있으면 입력 스택의 값을 모두 옮겨 담는다. 옮기면서 순서가 뒤집혀 가장 오래된 값이 출력 스택 맨 위에 온다. 원소마다 넣기·옮기기·꺼내기가 한 번씩뿐이라 분할 상환 O(1)이다. 스택마다 최솟값을 함께 들고 다니면 "최솟값을 O(1)에 아는 큐"도 된다(cp-algorithms의 Minimum stack / Minimum queue).

덱(deque, double-ended queue)은 양 끝 모두에서 O(1)로 넣고 꺼낸다. 스택과 큐를 한 자료구조로 대신할 수 있어 표준 라이브러리에 흔하다(파이썬 collections.deque, C++ std::deque, Java ArrayDeque). 구현은 보통 원형 버퍼나, 고정 크기 블록을 이어 붙인 구조를 쓴다. 미끄러지는 창에서 최댓값을 O(1)에 유지하는 단조 덱(monotonic deque) 같은 기법도 덱 위에서 돈다.

문제 풀기 →Python 코드 →

원형 버퍼

원형 버퍼(circular buffer, ring buffer)는 고정 크기 배열의 끝과 처음을 이어 붙인 것처럼 쓰는 큐다. 가장 오래된 값을 가리키는 head와 다음에 쓸 칸을 가리키는 tail 두 인덱스만 움직이고, 끝에 닿으면 mod 연산으로 0번 칸으로 돌아간다. 값은 한 번도 옮기지 않으므로 넣기와 꺼내기가 언제나 O(1)이고, 메모리를 새로 잡지도 않는다.

head와 tail이 같은 칸을 가리키는 순간은 비었을 때와 가득 찼을 때 두 경우라 구별이 필요하다. 그림처럼 든 개수(size)를 따로 세거나, 한 칸을 일부러 비워 두어 "tail 다음이 head면 가득 참"으로 정한다. 가득 찼을 때 새 값을 거부할지, 가장 오래된 값을 덮어쓸지도 용도에 따라 고른다.

크기가 정해져 있고 할당이 없다는 점이 실시간 시스템에 맞는다. 오디오 장치와 프로그램 사이의 샘플 버퍼, 키보드 입력 버퍼, 네트워크 카드의 수신 링, 최근 N개만 남기는 로그, 게임의 입력 기록 (되감기·리플레이)이 모두 원형 버퍼다. 크기를 2의 거듭제곱으로 잡으면 mod를 비트 AND 한 번으로 바꿀 수 있다. 생산자 하나·소비자 하나라면 잠금 없이도(lock-free) 안전하게 만들 수 있다.

문제 풀기 →Python 코드 →

연산별 비용 한눈에 보기

여섯 가지를 연산별로 나란히 놓으면, 어디에 넣고 어디서 꺼내는지가 자료구조를 고르는 기준이라는 것이 보인다. 표의 "가운데 넣기"는 넣을 자리를 이미 알 때의 비용이다.

고르는 순서는 대개 이렇다. 먼저 동적 배열을 생각한다. 앞에서도 빼야 하면 덱이나 원형 버퍼로 바꾼다. 쥐고 있는 노드를 자주 떼었다 붙여야 할 때만 연결 리스트를 쓴다. 값으로 찾는 일이 잦으면 이 노트의 어느 것도 답이 아니다. 해시 노트나 트리 노트로 넘어간다.