출제기준 세세항목: 스택 · 큐 · 리스트 등
| 선형 (5) | 비선형 (2) |
|---|---|
| 배열 | 트리 |
| 리스트 | 그래프 |
| 스택 | |
| 큐 | |
| 덱 |
같은 물건이라도 어떤 그릇에 담느냐에 따라 꺼내기 쉬운 정도가 달라집니다. 접시를 쌓아 두면 맨 위 접시만 쉽게 집을 수 있고, 줄을 세우면 맨 앞사람부터 차례로 들어갑니다. 프로그램도 마찬가지로 데이터를 어떤 규칙으로 담고 꺼낼지를 먼저 정하는데, 이 규칙과 모양을 자료구조라고 합니다. 자료구조를 잘 고르면 같은 알고리즘도 훨씬 빠르고 간단해집니다.
시험에서는 자료구조를 크게 두 갈래로 나눕니다. 데이터가 앞뒤 한 줄로 이어져 '내 다음은 누구'가 하나로 정해지는 구조를 선형 구조라고 하며, 배열, 리스트, 스택, 큐, 덱이 여기에 속합니다. 반대로 한 데이터 뒤에 여러 갈래가 이어지거나 서로 그물처럼 얽힌 구조를 비선형 구조라고 하며, 트리와 그래프가 대표적입니다.
구분이 헷갈릴 때는 '한 칸에서 다음 칸으로 가는 길이 하나뿐인가'를 떠올리면 됩니다. 길이 하나뿐이면 선형, 여러 갈래로 나뉠 수 있으면 비선형입니다. 이 항목에서는 선형 구조부터 차례로 보고, 이어서 트리와 그래프, 그리고 스택을 활용한 수식 표기 변환까지 다룹니다.
배열은 같은 종류의 데이터를 메모리의 연속된 칸에 차례로 담는 구조입니다. 칸이 붙어 있으니 '7번째 칸'처럼 위치(인덱스)만 알면 계산 한 번으로 바로 찾아갈 수 있습니다. 이렇게 데이터를 순서대로 연속된 공간에 저장하는 리스트를 선형 리스트(순차 리스트)라고 부르며, 시험에서는 배열로 구현한 리스트로 다룹니다. 대신 중간에 데이터를 하나 끼워 넣거나 빼려면 그 뒤에 있는 데이터를 한 칸씩 밀거나 당겨야 해서, 데이터가 많을수록 삽입·삭제가 느려집니다. 처음에 크기를 정해 두어야 하는 경우가 많다는 점도 불편합니다.
연결 리스트는 데이터를 흩어진 곳에 저장하고, 각 칸(노드)에 '다음 노드가 어디 있는지'를 적은 포인터를 함께 담아 줄줄이 이어 붙인 구조입니다. 보물찾기 쪽지가 다음 쪽지의 위치를 알려 주는 것과 비슷합니다. 중간에 노드를 넣거나 뺄 때는 앞뒤 노드의 포인터만 바꿔 주면 되므로 데이터를 옮길 필요가 없습니다. 하지만 7번째 노드를 보려면 첫 노드부터 포인터를 일곱 번 따라가야 해서 원하는 위치를 찾는 속도는 배열보다 느리고, 노드마다 포인터를 담을 공간이 더 듭니다.
연결 리스트는 연결 방식에 따라 이름이 나뉩니다. 다음 노드만 가리키는 단순 연결 리스트, 앞 노드와 다음 노드를 모두 가리켜 양방향으로 오갈 수 있는 이중 연결 리스트, 마지막 노드가 다시 첫 노드를 가리켜 고리 모양이 되는 원형 연결 리스트가 있습니다.
정리하면 '자주 읽고 위치로 바로 찾는다'면 배열이, '자주 끼워 넣고 뺀다'면 연결 리스트가 유리합니다. 뒤에 나오는 스택과 큐도 배열로 만들 수도 있고 연결 리스트로 만들 수도 있습니다. 스택과 큐는 담는 방식이 아니라 넣고 꺼내는 규칙으로 정의되는 구조이기 때문입니다.
스택은 한쪽 끝에서만 넣고 꺼내는 구조입니다. 좁은 통에 동전을 쌓으면 맨 나중에 넣은 동전을 가장 먼저 꺼내게 되는 것과 같습니다. 이 성질을 후입선출(LIFO, Last In First Out)이라고 합니다. 넣는 동작을 push, 꺼내는 동작을 pop이라 하고, 지금 맨 위 데이터의 위치를 가리키는 표시를 top이라고 부릅니다.
스택이 가득 찼는데 또 넣으려 하면 오버플로(overflow), 비어 있는데 꺼내려 하면 언더플로(underflow)가 일어납니다. 배열로 만든 스택이라면 push 전에는 '가득 찼는가', pop 전에는 '비었는가'를 먼저 확인하는 것이 기본입니다.
스택은 '가장 최근 일로 먼저 돌아가야 하는' 상황에 쓰입니다. 함수가 다른 함수를 부를 때 돌아올 위치를 쌓아 두었다가 끝난 순서의 반대로 돌아오는 함수 호출(서브루틴 복귀 주소 저장), 그 연장선인 재귀 호출, 문서 편집기의 실행 취소, 괄호 짝 검사, 뒤에 나올 후위 표기식 계산과 깊이 우선 탐색이 모두 스택을 씁니다.
직접 따라가 보겠습니다. 빈 스택에 push 8, push 3, pop, push 5, push 1, pop, pop, push 9를 차례로 하면, 첫 pop에서 3이 나오고 스택에는 8만 남습니다. 5와 1을 넣은 뒤 두 번 꺼내면 1, 5 순서로 나옵니다. 마지막에 9를 넣으면 스택에는 아래부터 8, 9가 남고 top은 9입니다. 꺼낸 순서는 3, 1, 5입니다.
큐는 한쪽 끝(rear, 뒤)으로 넣고 반대쪽 끝(front, 앞)으로 꺼내는 구조입니다. 매표소 줄처럼 먼저 온 사람이 먼저 나갑니다. 이 성질을 선입선출(FIFO, First In First Out)이라고 합니다. 넣는 동작을 enqueue, 꺼내는 동작을 dequeue라고 부르며, 들어오는 쪽과 나가는 쪽이 다르기 때문에 위치 표시도 front와 rear 두 개를 씁니다.
앞의 스택 예와 똑같은 순서로 큐에 넣고 꺼내 보면 차이가 분명해집니다. 8, 3을 넣고 하나 꺼내면 먼저 들어온 8이 나옵니다. 5, 1을 넣은 뒤 두 번 꺼내면 3, 5가 나오고, 마지막에 9를 넣으면 큐에는 앞에서부터 1, 9가 남습니다. 꺼낸 순서는 8, 3, 5로, 스택의 3, 1, 5와 전혀 다릅니다.
큐는 '도착한 순서대로 공평하게 처리해야 하는' 곳에 쓰입니다. 운영체제가 실행을 기다리는 작업을 줄 세우는 작업 스케줄링, 여러 사람이 보낸 인쇄 작업을 차례로 처리하는 프린터 대기열(스풀), 속도가 다른 장치 사이에서 데이터를 잠시 모아 두는 버퍼, 그리고 너비 우선 탐색이 대표적입니다.
배열로 큐를 만들면 꺼낼 때마다 앞쪽에 빈칸이 생기는데, rear가 배열 끝에 닿으면 앞에 빈칸이 남아 있어도 더 넣을 수 없는 문제가 생깁니다. 그래서 배열의 끝과 처음을 이어 고리처럼 쓰는 원형 큐를 많이 씁니다.
덱(Deque, Double-Ended Queue)은 양쪽 끝 모두에서 넣고 꺼낼 수 있는 구조입니다. 한쪽만 쓰면 스택처럼, 넣는 쪽과 꺼내는 쪽을 나눠 쓰면 큐처럼 동작하므로 둘을 합친 구조라고 볼 수 있습니다. 넣기는 한쪽에서만 허용하고 꺼내기는 양쪽에서 허용하는 입력 제한 덱을 스크롤(Scroll), 반대로 넣기는 양쪽에서 허용하고 꺼내기는 한쪽에서만 허용하는 출력 제한 덱을 셸프(Shelf)라고 부릅니다.
트리는 하나의 시작점에서 아래로 가지가 갈라지는 계층 구조입니다. 회사 조직도나 컴퓨터의 폴더 구조를 떠올리면 됩니다. 각 데이터를 노드, 노드를 잇는 선을 간선(링크)이라 하고, 맨 위의 시작 노드를 루트(Root)라고 합니다. 어떤 노드 바로 아래에 이어진 노드는 그 노드의 자식, 위에 있는 노드는 부모, 같은 부모를 둔 노드끼리는 형제입니다. 사이클(돌고 돌아 제자리로 오는 길)이 없다는 점이 그래프와 구별되는 특징입니다.
시험에 자주 나오는 용어가 차수입니다. 노드의 차수(Degree)는 그 노드가 가진 자식의 수이고, 트리의 차수는 트리 안에서 가장 큰 노드 차수입니다. 자식이 하나도 없는(차수가 0인) 노드를 단말 노드 또는 리프(Leaf) 노드라고 합니다. 루트를 레벨 1로 두고 한 층 내려갈 때마다 레벨이 1씩 늘며, 트리에서 가장 큰 레벨을 트리의 깊이(또는 높이)라고 합니다.
모든 노드의 자식이 최대 두 개인 트리를 이진 트리라고 합니다. 자식을 왼쪽과 오른쪽으로 구분하는 것이 특징입니다. 루트를 레벨 1로 볼 때 레벨 i에는 노드가 최대 2의 (i-1)제곱 개 들어가고, 깊이가 k인 이진 트리는 노드를 최대 (2의 k제곱 - 1)개 가질 수 있습니다. 모든 레벨이 빈틈없이 꽉 찬 트리를 포화 이진 트리, 마지막 레벨을 뺀 나머지는 꽉 차 있고 마지막 레벨은 왼쪽부터 빈틈없이 채워진 트리를 완전 이진 트리라고 합니다. 포화 이진 트리는 완전 이진 트리이기도 하지만 그 반대는 성립하지 않습니다.
트리의 모든 노드를 한 번씩 빠짐없이 방문하는 것을 순회라고 합니다. 이진 트리 순회는 세 가지가 있는데, 왼쪽 서브트리를 오른쪽보다 먼저 도는 점은 같고 루트(현재 노드)를 언제 방문하느냐만 다릅니다. 루트를 먼저 들르면 전위 순회(Preorder: 루트 → 왼쪽 → 오른쪽), 가운데에 들르면 중위 순회(Inorder: 왼쪽 → 루트 → 오른쪽), 마지막에 들르면 후위 순회(Postorder: 왼쪽 → 오른쪽 → 루트)입니다. 이름의 '전·중·후'가 루트의 위치를 뜻한다고 기억하면 됩니다.
순회는 재귀적으로 적용한다는 점이 중요합니다. 왼쪽 서브트리를 돈다는 것은 그 서브트리의 루트를 기준으로 다시 같은 규칙을 적용한다는 뜻입니다. 큰 트리를 한 번에 보려 하지 말고, 서브트리마다 괄호로 묶어 안쪽부터 풀면 실수가 줄어듭니다.
예를 들어 보겠습니다. 루트 P의 왼쪽 자식은 K, 오른쪽 자식은 T입니다. K의 왼쪽 자식은 D, 오른쪽 자식은 M이고, M은 왼쪽 자식 L 하나만 가집니다. T는 오른쪽 자식 W 하나만 가집니다. 전위 순회는 P를 먼저 쓰고, K 서브트리를 (K, D, M, L) 순서로, T 서브트리를 (T, W) 순서로 돌아 P K D M L T W가 됩니다.
중위 순회는 K 서브트리를 먼저 끝내야 P를 쓸 수 있습니다. K 서브트리 안에서는 D, K를 쓴 뒤 M 서브트리를 중위로 돌아 L, M을 씁니다. 그다음 P, 그리고 T 서브트리는 왼쪽 자식이 없으므로 T, W 순서입니다. 결과는 D K L M P T W입니다. 후위 순회는 자식을 모두 끝낸 뒤 부모를 쓰므로 D, L, M, K를 먼저 쓰고, W, T를 쓴 다음 마지막에 루트 P를 써서 D L M K W T P가 됩니다. 후위 순회의 마지막이 항상 루트이고, 전위 순회의 처음이 항상 루트라는 점을 검산에 쓰면 좋습니다.
우리가 평소 쓰는 'A + B'처럼 연산자를 피연산자 사이에 두는 방식을 중위 표기(Infix)라고 합니다. 연산자를 앞에 두는 '+ A B'는 전위 표기(Prefix), 뒤에 두는 'A B +'는 후위 표기(Postfix)입니다. 앞에서 본 트리 순회 이름과 같은 원리로, 수식을 트리로 그리면 각 순회 결과가 그대로 해당 표기가 됩니다.
중위식을 다른 표기로 바꿀 때는 연산 순서대로 괄호를 빠짐없이 친 다음, 각 괄호 안의 연산자를 괄호의 앞(전위) 또는 뒤(후위)로 옮기고 괄호를 지우면 됩니다. 예를 들어 (G - H) * K + M / N은 곱셈·나눗셈이 덧셈보다 먼저이므로 ( ( (G - H) * K ) + (M / N) )로 묶입니다. 연산자를 각 괄호 뒤로 옮기면 후위 표기 G H - K * M N / +, 앞으로 옮기면 전위 표기 + * - G H K / M N이 됩니다. 거꾸로 후위식을 중위식으로 바꿀 때는 왼쪽부터 읽다가 연산자를 만날 때마다 바로 앞의 피연산자 두 개와 묶어 괄호를 치면 됩니다.
후위 표기의 장점은 괄호도 연산자 우선순위도 따질 필요 없이 스택 하나로 왼쪽부터 계산할 수 있다는 것입니다. 숫자를 만나면 push하고, 연산자를 만나면 두 개를 pop해 계산한 뒤 결과를 다시 push합니다. 이때 먼저 꺼낸 값이 오른쪽 피연산자, 나중에 꺼낸 값이 왼쪽 피연산자라는 점에 주의해야 합니다. 빼기와 나누기는 순서가 바뀌면 답이 달라지기 때문입니다.
7 3 - 4 * 9 3 / +를 계산해 보겠습니다. 7과 3을 넣고 '-'를 만나면 3, 7을 꺼내 7 - 3 = 4를 넣습니다. 4를 넣고 '*'를 만나면 4 * 4 = 16을 넣습니다. 9와 3을 넣고 '/'를 만나면 9 / 3 = 3을 넣고, 마지막 '+'에서 16 + 3 = 19가 됩니다. 이 식을 중위로 바꾸면 (7 - 3) * 4 + 9 / 3이며, 직접 계산해도 19로 같습니다.
그래프는 정점(Vertex)과 정점을 잇는 간선(Edge)으로 이루어진 구조입니다. 지하철 노선도나 친구 관계처럼 계층 없이 서로 자유롭게 연결된 관계를 나타냅니다. 간선에 방향이 없으면 무방향 그래프, 방향이 있으면 방향 그래프라고 하고, 간선에 거리나 비용 같은 값을 붙이면 가중치 그래프가 됩니다. 정점이 n개일 때 모든 정점끼리 간선이 있는 완전 그래프의 간선 수는 무방향이면 n(n-1)/2개, 방향이면 n(n-1)개입니다.
그래프를 컴퓨터에 저장하는 방법은 두 가지가 대표적입니다. 정점 수만큼의 가로세로 표를 만들어 연결된 칸에 1을 적는 인접 행렬은 두 정점이 연결됐는지 바로 알 수 있지만, 간선이 적으면 빈칸이 많아 공간이 낭비됩니다. 정점마다 연결된 정점 목록을 연결 리스트로 달아 두는 인접 리스트는 실제 간선만큼만 공간을 씁니다.
그래프의 모든 정점을 방문하는 방법으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. DFS는 갈 수 있는 데까지 한 방향으로 깊이 들어갔다가 막히면 바로 직전 갈림길로 되돌아와 다른 길을 찾습니다. 되돌아갈 곳을 기억해야 하므로 스택(또는 재귀 호출)을 씁니다. BFS는 시작점에서 가까운 정점들을 한 겹씩 모두 방문한 뒤 그다음 겹으로 넓혀 갑니다. 먼저 발견한 정점부터 차례로 처리해야 하므로 큐를 씁니다.
정점 A~F가 있고 간선이 A-B, A-D, B-E, D-C, D-E, E-F인 무방향 그래프를, 이웃이 여럿이면 알파벳이 앞선 정점부터 간다는 규칙으로 A에서 출발해 탐색해 봅시다. DFS는 A에서 B로, B에서 E로 들어간 뒤 E의 이웃 중 아직 안 간 D, 다시 D의 이웃 C까지 내려갑니다. C에서 막히면 D, E로 되돌아와 남은 F를 방문하므로 A B E D C F입니다. BFS는 A의 이웃 B, D를 먼저 큐에 넣고, B를 꺼내며 E를, D를 꺼내며 C를 넣고, E를 꺼내며 F를 넣으므로 A B D E C F입니다. 같은 그래프라도 탐색 방식에 따라 순서가 달라집니다.
W, X, Y, Z를 이 순서로만 스택에 넣을 수 있고 중간중간 언제든 꺼낼 수 있다고 합시다. Y, Z, X, W는 W·X·Y를 넣고 Y를 꺼낸 뒤, Z를 넣고 꺼내고, 남은 X, W를 꺼내면 만들 수 있습니다. 하지만 Y, W, ...로 시작하는 순서는 불가능합니다. Y를 꺼낸 순간 스택 맨 위에는 X가 있어서, W를 꺼내려면 X가 먼저 나와야 하기 때문입니다. 이런 문제는 실제로 push와 pop을 손으로 적어 보면 빠르게 판단할 수 있습니다.
본문의 순회 예시 트리(루트 P)에서 자식이 없는 단말 노드는 D, L, W의 세 개입니다. 자식이 가장 많은 노드는 P와 K로 각각 2개이므로 트리의 차수는 2입니다. 레벨은 P가 1, K와 T가 2, D·M·W가 3, L이 4이므로 트리의 깊이는 4입니다. 깊이가 4인 이진 트리는 노드를 최대 15개 가질 수 있는데 이 트리는 7개뿐이므로 포화 이진 트리가 아닙니다.
그림판 앱을 만든다고 해 봅시다. 사용자가 그린 획을 하나씩 스택에 push해 두면, 실행 취소를 누를 때 pop으로 가장 최근 획부터 지울 수 있습니다. 반면 여러 사용자가 보낸 이미지 저장 요청은 큐에 넣어 두고 먼저 들어온 요청부터 처리해야 순서가 뒤엉키지 않습니다. 같은 '쌓아 두기'라도 꺼내는 순서가 무엇이어야 하는지가 자료구조를 고르는 기준입니다.