자료구조 완전정복

🎯 학습 목표

이 강을 마치면 다음을 할 수 있습니다.

• 선형 자료구조(배열·연결 리스트·스택·큐·덱)의 특성과 연산 시간복잡도를 비교할 수 있습니다.
• 스택을 이용한 후위표기법 변환과 계산 과정을 추적할 수 있습니다.
• 트리의 전위·중위·후위 순회 결과를 주어진 트리에서 직접 구할 수 있습니다.
• 그래프의 인접 행렬과 인접 리스트 표현 방식을 변환할 수 있습니다.
• 주요 알고리즘의 Big-O 시간복잡도를 비교할 수 있습니다.

📋 선형 자료구조 — 배열과 연결 리스트

이 섹션에서는 데이터를 순서대로 저장하는 가장 기본적인 선형 자료구조를 살펴보겠습니다.

배열(Array)은 동일한 타입의 데이터를 메모리에 연속적으로 저장하는 자료구조입니다. 인덱스를 통한 임의 접근(Random Access)이 O(1)로 매우 빠릅니다. 반면 삽입·삭제 시 요소를 이동시켜야 하므로 O(n)이 걸립니다. 크기가 고정(정적 배열)되거나 미리 크기를 지정해야 합니다.

연결 리스트(Linked List)는 데이터와 다음 노드의 주소(포인터)를 함께 저장하는 노드들의 연결로 구성됩니다. 삽입·삭제가 O(1)(위치를 알 때)로 빠르지만, 임의 접근은 처음부터 순차 탐색해야 하므로 O(n)이 걸립니다. 세 종류가 있습니다.

• 단순(단방향) 연결 리스트: 각 노드가 다음 노드만 가리킵니다. 마지막 노드의 포인터는 NULL.
• 이중 연결 리스트: 각 노드가 이전·다음 노드 모두 가리킵니다. 양방향 탐색 가능, 메모리 더 사용.
• 원형 연결 리스트: 마지막 노드가 첫 번째 노드를 가리킵니다. 순환 구조.

연산	배열	연결 리스트
임의 접근	O(1)	O(n)
삽입(앞)	O(n)	O(1)
삽입(뒤)	O(1)~O(n)	O(n) 또는 O(1)(꼬리 포인터 있으면)
삭제	O(n)	O(1)(위치 알 때)
검색	O(n)	O(n)

📚 스택·큐·덱과 응용

이 섹션에서는 제한적인 접근 방식으로 특정 문제를 효율적으로 해결하는 스택·큐·덱을 살펴보겠습니다.

스택(Stack)은 LIFO(Last In, First Out) — 나중에 들어온 것이 먼저 나가는 자료구조입니다. 연산은 Push(삽입), Pop(꺼내기), Peek/Top(맨 위 확인)입니다. 함수 호출 스택, 브라우저 뒤로가기, 수식 계산에 사용됩니다. 큐(Queue)는 FIFO(First In, First Out) — 먼저 들어온 것이 먼저 나가는 자료구조입니다. 연산은 Enqueue(삽입), Dequeue(꺼내기)입니다. 프린터 대기열, BFS, CPU 스케줄링에 사용됩니다. 덱(Deque, Double-ended Queue)은 앞뒤 양쪽에서 삽입·삭제가 모두 가능한 자료구조입니다.

스택 응용 — 후위표기법(Postfix)이 기출에서 자주 출제됩니다. 수식 표기법은 세 종류입니다: 전위(Prefix) — 연산자가 피연산자 앞, 중위(Infix) — 연산자가 피연산자 사이(일반적 수식), 후위(Postfix) — 연산자가 피연산자 뒤. 컴퓨터는 후위표기법으로 수식을 계산합니다(괄호 없이 연산 순서 표현 가능).

중위 → 후위 변환 규칙: 피연산자는 바로 출력, 연산자는 스택에 쌓되 우선순위가 높은 것부터 출력합니다. 예: A + B * C → 후위: A B C * +. 후위 계산: 피연산자는 스택에 push, 연산자 만나면 스택에서 두 개 pop하여 계산 후 push. 예: 3 4 2 * + → 4*2=8 → 3+8=11.

🌲 트리와 순회

이 섹션에서는 계층적 데이터를 표현하는 트리 자료구조와 세 가지 순회 방법을 살펴보겠습니다.

트리(Tree)는 계층적 관계를 표현하는 비선형 자료구조입니다. 핵심 용어를 정리해 보겠습니다. 루트(Root): 최상위 노드(부모 없음). 단말 노드(Leaf): 자식이 없는 노드. 내부 노드(Internal): 자식이 있는 루트 외 노드. 깊이(Depth): 루트에서 해당 노드까지의 거리. 높이(Height): 트리의 최대 깊이. 차수(Degree): 노드의 자식 수.

이진 트리(Binary Tree)는 모든 노드의 자식이 최대 2개인 트리입니다. 기출에서 가장 중요한 것은 트리 순회(Tree Traversal)입니다. 주어진 트리의 순회 결과를 직접 구하는 문제가 자주 출제됩니다.

순회 방식	방문 순서	루트 위치	예시 결과 (루트=A, 왼=B, 오=C)
전위(Preorder)	루트 → 왼쪽 → 오른쪽	맨 앞	A, B, C
중위(Inorder)	왼쪽 → 루트 → 오른쪽	가운데	B, A, C
후위(Postorder)	왼쪽 → 오른쪽 → 루트	맨 뒤	B, C, A

이진 탐색 트리(BST)에서 중위 순회 결과는 항상 오름차순 정렬됩니다. 기출 포인트: 순회 결과로 역으로 트리 구조를 추측하는 문제도 출제됩니다.

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 최댓값·최솟값을 O(log n)으로 빠르게 찾는 데 사용됩니다. 최대 힙(Max Heap)은 부모가 항상 자식보다 크거나 같고, 최소 힙(Min Heap)은 부모가 항상 자식보다 작거나 같습니다. 삽입·삭제 O(log n), 최솟값·최댓값 접근 O(1). 우선순위 큐 구현에 사용됩니다.

🕸️ 그래프와 Big-O

이 섹션에서는 복잡한 관계를 표현하는 그래프 자료구조와 알고리즘 성능 분석의 기준인 시간복잡도를 살펴보겠습니다.

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성되는 자료구조입니다. 트리는 그래프의 특수한 형태(사이클 없는 연결 그래프)입니다. 방향에 따라 방향 그래프(Directed)와 무방향 그래프(Undirected)로 구분됩니다. 가중치가 있으면 가중치 그래프(Weighted Graph)라고 합니다.

그래프를 표현하는 두 가지 방법이 기출에서 중요합니다.

• 인접 행렬(Adjacency Matrix): n×n 2차원 배열. [i][j]=1이면 정점 i→j 간선 존재. 간선 확인이 O(1)로 빠르지만 공간이 O(n²) 필요. 밀집 그래프에 적합.
• 인접 리스트(Adjacency List): 각 정점마다 연결된 정점 목록을 저장. 공간이 O(V+E)로 효율적. 희소 그래프에 적합. 모든 간선 순회가 효율적.

시간복잡도 Big-O는 알고리즘의 실행 시간이 입력 크기 n에 따라 어떻게 증가하는지를 나타냅니다.

Big-O	명칭	예시	속도
O(1)	상수	배열 인덱스 접근, 해시 테이블	가장 빠름
O(log n)	로그	이진 탐색, 힙 삽입/삭제	빠름
O(n)	선형	선형 탐색, 배열 순회	보통
O(n log n)	선형로그	합병 정렬, 힙 정렬, 퀵 정렬(평균)	보통~느림
O(n²)	이차	버블·선택·삽입 정렬, 이중 반복문	느림
O(2ⁿ)	지수	재귀적 피보나치(메모이제이션 없이)	매우 느림
O(n!)	팩토리얼	순열 생성, 외판원 문제(완전 탐색)	가장 느림

📝 핵심 요약

6강에서 배운 내용을 정리해 보겠습니다.

• 스택: LIFO(Last In First Out) — 후위표기법 계산, 재귀 호출
• 큐: FIFO(First In First Out) — BFS, 프린터 대기열
• 트리 순회: 전위=루트먼저, 중위=루트가운데, 후위=루트마지막
• BST 중위 순회: 항상 오름차순
• 인접 행렬: O(n²) 공간, 밀집 그래프 / 인접 리스트: O(V+E) 공간, 희소 그래프
• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

다음 강인 7강 — 알고리즘 정렬과 탐색에서는 6대 정렬 알고리즘의 단계별 추적, 복잡도 비교표, 이진 탐색, 동적계획법·탐욕 알고리즘 기출 유형을 완전히 정복합니다!