자료구조: 해설이 있는 연습 문제

1자료 구조란 무엇인가

자료 구조는 항목 찾기, 추가, 삭제 같은 특정 연산이 빨라지도록 메모리에 데이터를 조직하는 방법입니다.

모든 것에서 빠른 구조는 없습니다. 구조를 고른다는 것은 어떤 연산을 싸게 만들지 고르는 것입니다. 비용은 빅오로 쓰며, n은 항목의 수입니다.

두 가지 기본 구성 요소는 배열과 연결 리스트입니다.

배열은 항목을 한 덩어리의 메모리에 차례로 저장합니다. 컴퓨터가 항목 i의 위치를 계산할 수 있으므로 a[i]를 읽는 데 O(1)이 걸립니다. 맨 앞에 삽입하려면 모든 항목을 밀어야 합니다: O(n).

연결 리스트는 각 항목을 다음 노드를 가리키는 포인터가 있는 노드에 저장합니다. 마지막 포인터는 null입니다. 머리(h)에 삽입하는 것은 포인터 하나만 바꾸므로 O(1)입니다. 하지만 항목 i에 닿으려면 포인터를 i번 따라가야 합니다: O(n).

이중 연결 리스트는 이전 노드를 가리키는 포인터도 있어서 양방향으로 걸을 수 있습니다.

2스택과 큐

스택은 접시 더미와 같습니다. 맨 위에서만 넣고 뺍니다. 마지막에 들어온 것이 먼저 나옵니다: LIFO.

• push는 맨 위에 항목을 올리고, pop은 맨 위 항목을 제거하며, peek은 제거하지 않고 맨 위를 읽습니다. 모두 O(1)입니다.
• 쓰임: 편집기의 실행 취소 기능, 프로그램의 호출 스택, 괄호 짝 확인, 깊이 우선 탐색.

큐는 계산대의 줄과 같습니다. 뒤에서 줄을 서고 앞에서 나갑니다. 처음에 들어온 것이 먼저 나옵니다: FIFO.

• enqueue는 뒤에 추가하고 dequeue는 앞에서 제거합니다. 둘 다 O(1)입니다.
• 쓰임: 인쇄 작업, 처리를 기다리는 메시지, 너비 우선 탐색.

덱(deque, 양쪽 끝 큐)은 양쪽 끝에서 추가와 제거를 허용합니다. 우선순위 큐는 항상 우선순위가 가장 높은 항목을 먼저 제거하며, 보통 힙으로 만듭니다.

3트리, 힙, 해시 테이블, 그래프

트리에는 맨 위의 노드인 루트가 하나 있습니다. 다른 모든 노드는 부모가 정확히 하나입니다. 자식이 없는 노드는 리프입니다. 노드가 n개인 트리는 간선이 n − 1개입니다.

이진 트리에서는 모든 노드의 자식이 최대 둘입니다. 이진 탐색 트리(BST)는 규칙을 하나 더합니다. 왼쪽 서브트리의 키는 노드보다 작고, 오른쪽 서브트리의 키는 노드보다 큽니다.

BST 탐색은 한 경로를 따라 내려가므로 O(높이)가 듭니다. 균형 트리(AVL, 레드-블랙)는 높이를 log₂ n 가까이로 유지합니다. 정렬된 순서로 키를 삽입하면 높이 n의 사슬이 됩니다.

힙은 모든 부모가 자식보다 작은(최소 힙) 또는 큰(최대 힙) 이진 트리입니다. 최솟값이나 최댓값이 루트에 있으며 삽입과 제거는 O(log n)입니다.

해시 테이블은 키–값 쌍을 저장합니다. 해시 함수가 키를 인덱스로 바꾸므로 삽입과 조회가 평균 O(1)입니다. 같은 인덱스를 갖는 두 키는 충돌이며, 체이닝(칸마다 리스트)이나 개방 주소법(다른 칸을 시도)으로 해결합니다.

그래프는 간선으로 이어진 정점들로 이루어지며, 간선에는 방향이나 가중치가 있을 수 있습니다. 인접 행렬(메모리 O(V²)) 또는 인접 리스트(O(V + E))로 저장합니다.

4단계별 방법

문제는 흔히 과제를 설명하고 어떤 구조가 맞는지 묻거나, 몇 가지 연산 뒤 구조가 어떤 모양인지 묻습니다.

1. 빨라야 하는 연산을 찾으세요: 위치로 접근, 키로 접근, 가장 새로운 항목, 가장 오래된 항목, 가장 작은 항목, 또는 범위.
2. 구조와 짝지으세요: 인덱스 → 배열, 키 → 해시 테이블, 가장 새로운 것 → 스택, 가장 오래된 것 → 큐, 가장 작거나 큰 것 → 힙, 정렬된 순서나 범위 → 균형 탐색 트리.
3. 과제에 필요한 다른 연산의 비용도 빅오로 확인하세요.
4. 추적 문제에서는 연산을 하나씩 수행하고 매번 뒤의 상태를 적으세요.
5. 최종 상태를 구조의 규칙에 비추어 확인하세요: LIFO, FIFO, BST 순서, 힙 순서.

5풀이 예제

모든 단계를 따라가 보세요. 다음 단계를 열기 전에 미리 예측해 보세요.

6흔한 실수

• LIFO와 FIFO를 혼동하는 것. 스택은 가장 새로운 항목을, 큐는 가장 오래된 항목을 돌려줍니다.
• 연결 리스트가 인덱스로 빠르게 접근할 수 있다고 생각하는 것. 머리부터 걸어가야 합니다.
• BST가 항상 O(log n)이라고 가정하는 것. 균형 트리만 그렇고, 정렬된 삽입은 O(n)을 줍니다.
• 해시 테이블의 충돌을 잊는 것. O(1)은 평균이지 최악의 경우가 아닙니다.
• 순회 방식을 혼동하는 것. 전위: 노드가 먼저. 중위: 노드가 가운데. 후위: 노드가 마지막.
• 큰 희소 그래프에 인접 행렬을 쓰는 것. O(V²) 메모리를 낭비합니다.

7시험 문제의 유형

• 쉬움: 핵심 용어와 사실. LIFO와 FIFO, 노드·루트·리프란 무엇인가, BST 규칙, 해시 함수가 하는 일.
• 보통: 개념 적용. 과제에 맞는 구조, push와 pop 또는 BST 삽입의 결과, 트리 순회, 선형 탐사를 쓰는 해시 테이블, 빅오 비용.
• 어려움: 사례와 분석. 균형 트리, 배열로 저장한 힙, B-트리, 트라이, 유니온-파인드, 블룸 필터, LRU 캐시 같은 설계.

인덱스 0부터 배열에 저장한 힙에서 인덱스 i의 자식은 2i + 1과 2i + 2에 있고, 부모는 ⌊(i − 1) / 2⌋에 있습니다.