9. 자료구조 & 알고리즘 필수

규미·2025년 11월 15일

배열 스택 연결리스트 자료구조 정렬 큐 힙

CS-study

목록 보기

9/10

1. 배열 (Array) vs 연결 리스트 (Linked List)

데이터를 순차적으로 저장하는 가장 기본적인 두 가지 선형 자료구조입니다. 하지만 메모리상에서의 동작 방식은 완전히 다릅니다.

1.1. 배열 (Array)

연속된 메모리 공간에 나란히 저장된 데이터의 집합

배열은 같은 타입의 데이터가 메모리상에 연속적으로 저장되는 구조입니다.

가장 큰 특징은 인덱스(Index)를 통해 데이터에 직접 접근(Random Access)할 수 있다는 점입니다. 0번부터 시작하는 인덱스를 알면, [주소 + 인덱스 데이터 타입 크기] 공식을 통해 O(1)의 속도로 원하는 값을 즉시 찾아낼 수 있습니다.

주요 특징:

빠른 조회 (읽기): 인덱스를 통한 접근 속도가 O(1)로 매우 빠릅니다.
느린 삽입/삭제: 중간에 데이터를 삽입하거나 삭제하면, 그 뒤의 모든 데이터를 한 칸씩 밀거나(삽입) 당겨야(삭제) 합니다. 이 과정에서 O(n)의 시간이 소요됩니다.
정적 크기: 대부분의 언어에서 배열은 처음에 크기를 지정해야 하며, 이 크기를 동적으로 변경하기 어렵습니다.

1.2. 연결 리스트 (Linked List)

데이터와 포인터가 한 몸! 노드(Node)들이 사슬처럼 연결된 구조

연결 리스트는 데이터가 메모리상에 흩어져 저장됩니다. 각 데이터는 값(Value)과 다음 노드를 가리키는 포인터(Pointer/Next)를 함께 가진 '노드(Node)'라는 단위로 존재합니다.

데이터에 접근하려면 반드시 첫 번째 노드(Head)부터 포인터를 따라 순차적으로 이동해야 합니다.

// 연결 리스트의 노드 구조 (Java 예시)
class Node {
    Object data; // 실제 데이터
    Node next;   // 다음 노드를 가리키는 포인터

    Node(Object data) {
        this.data = data;
        this.next = null;
    }
}

주요 특징

빠른 삽입/삭제: 특정 위치의 노드를 알고 있다면, 포인터(주소) 두 개의 연결만 변경하면 되므로 O(1)의 속도로 빠릅니다. (단, 그 위치를 찾아가는 과정은 O(n)입니다.)
느린 조회 (읽기): K번째 데이터를 찾으려면 첫 번째 노드부터 순차적으로 탐색해야 하므로 O(n)의 시간이 걸립니다.
동적 크기: 크기가 정해져 있지 않고, 필요할 때마다 노드를 추가하거나 삭제할 수 있어 유연합니다.

1.3. 비교표: 배열 vs 연결 리스트

특징	배열 (Array)	연결 리스트 (Linked List)
데이터 접근 (읽기)	O(1) (매우 빠름)	O(n) (느림)
데이터 삽입/삭제	O(n) (느림)	O(1) (해당 노드 접근 후)
메모리 구조	연속적인 공간 (Cache-friendly)	불연속적인 공간
메모리 크기	정적 (Static)	동적 (Dynamic)
추가 공간	없음	포인터를 위한 추가 공간 필요
주요 사용처	데이터 조회/접근이 빈번할 때	데이터 삽입/삭제가 빈번할 때

2. 스택 (Stack), 큐 (Queue), 힙 (Heap)

데이터를 저장하는 방식에 특별한 규칙을 적용한 자료구조들입니다.

2.1. 스택 (Stack)

LIFO (Last-In, First-Out) : 마지막에 들어온 것이 가장 먼저 나간다

스택은 한쪽 끝에서만 데이터가 들어가고(Push) 나가는(Pop) 구조입니다. 마치 쌓아 올린 접시나 프링글스 통을 생각하면 쉽습니다.

주요 연산:
- Push(data): 스택의 맨 위에 데이터를 추가합니다.
- Pop(): 스택의 맨 위 데이터를 꺼내고(삭제) 반환합니다.
- Peek(): 스택의 맨 위 데이터를 삭제하지 않고 조회만 합니다.
시간 복잡도: 모든 연산(Push, Pop, Peek)이 O(1)입니다.
사용 예: 함수 호출 스택(재귀), 웹 브라우저 '뒤로 가기' 기능, 깊이 우선 탐색(DFS)

2.2. 큐 (Queue)

FIFO (First-In, First-Out) : 먼저 들어온 것이 가장 먼저 나간다

큐는 한쪽 끝(Rear)에서는 데이터가 들어가고(Enqueue), 반대쪽 끝(Front)에서는 나오는(Dequeue) 구조입니다. 은행 창구의 대기 줄과 같습니다.

주요 연산:
- Enqueue(data): 큐의 맨 뒤(Rear)에 데이터를 추가합니다.
- Dequeue(): 큐의 맨 앞(Front) 데이터를 꺼내고(삭제) 반환합니다.
- Peek(): 큐의 맨 앞 데이터를 삭제하지 않고 조회만 합니다.
시간 복잡도: 모든 연산(Enqueue, Dequeue, Peek)이 O(1)입니다.
사용 예: 너비 우선 탐색(BFS), 작업 대기열(Task Queue), 프린터 인쇄 대기열

2.3. 힙 (Heap)

우선순위 큐 (Priority Queue) : 가장 중요한(크거나 작은) 데이터가 먼저 나온다

힙은 일반적인 스택이나 큐와 달리, 우선순위가 가장 높은 데이터를 가장 먼저 꺼낼 수 있도록 설계된 자료구조입니다. '완전 이진 트리' 구조를 기반으로 합니다.

최대 힙 (Max Heap): 부모 노드가 항상 자식 노드보다 크거나 같습니다. (루트 = 최댓값)
최소 힙 (Min Heap): 부모 노드가 항상 자식 노드보다 작거나 같습니다. (루트 = 최솟값)
주요 연산:
- Insert(data): 데이터를 힙에 추가하고, 힙의 구조를 재조정합니다. (O(log n))
- Extract(): 루트 노드(최댓값 또는 최솟값)를 꺼내고, 힙의 구조를 재조정합니다. (O(log n))
사용 예: 우선순위 기반의 스케줄링(운영체제), 다익스트라 알고리즘, 힙 정렬

3. 정렬 알고리즘 (퀵, 병합, 힙 정렬)

데이터를 순서대로 나열하는 알고리즘 중, 가장 효율이 좋은 O(n log n) 복잡도의 대표 3인방입니다.

3.1. 퀵 정렬 (Quick Sort)

기준(Pivot)을 잡아라! 기준보다 작은 건 왼쪽, 큰 건 오른쪽

이름처럼 평균적으로 가장 빠른 속도를 자랑하는 분할 정복 (Divide and Conquer) 알고리즘입니다.

배열 내에서 '피벗(Pivot)'이라는 기준점을 하나 정합니다.
피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할(Partition)합니다.
나누어진 왼쪽 그룹과 오른쪽 그룹에 대해 이 과정을 재귀적으로 반복합니다.

장점: 평균 속도가 O(n log n)으로 매우 빠릅니다. 추가 메모리가 거의 필요 없는 In-place 정렬입니다.
단점: 피벗을 최악(예: 이미 정렬된 배열에서 첫 번째 값)으로 선택하면, 최악의 경우 O(n^2)의 시간이 걸릴 수 있습니다.

3.2. 병합 정렬 (Merge Sort)

일단 쪼개고, 나중에 합치면서 정렬한다

안정적인 성능을 보장하는 분할 정복 (Divide and Conquer) 알고리즘입니다.

데이터를 1개가 될 때까지 절반으로 계속 쪼갭니다(분할).
나누어진 두 개의 (이미 정렬된) 작은 배열을 하나로 합치면서(병합) 정렬합니다.

장점: 항상 O(n log n)의 성능을 보장합니다. (최악의 경우에도) 중복된 값의 순서가 유지되는 안정(Stable) 정렬입니다.
단점: 정렬된 결과를 담을 추가 메모리 공간 (원본 배열과 같은 크기)이 필요합니다. (O(n))

3.3. 힙 정렬 (Heap Sort)

힙(Heap) 자료구조를 이용한 정렬

위에서 설명한 '힙' 자료구조를 활용하는 정렬 방식입니다. (보통 '최대 힙' 사용)

전체 데이터를 '최대 힙(Max Heap)' 구조로 만듭니다. (가장 큰 값이 루트(맨 위)에 옴)
루트 노드(가장 큰 값)를 배열의 맨 뒤로 보냅니다.
남은 데이터(맨 뒤로 보낸 것 제외)로 다시 힙 구조를 만듭니다(Heapify).
2~3번 과정을 데이터가 하나 남을 때까지 반복합니다.

장점: 항상 O(n log n)의 성능을 보장합니다. 추가 메모리 공간이 거의 필요 없는 In-place 정렬입니다.
단점: 퀵 정렬보다 평균적인 속도는 약간 느릴 수 있으며, 안정 정렬이 아닙니다.

3.4. 퀵 정렬 vs 병합 정렬 vs 힙 정렬

알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도 (추가 메모리)	안정성 (Stable)
퀵 정렬	O(n log n)	O(n^2)	O(log n) (In-place)	X (불안정)
병합 정렬	O(n log n)	O(n log n)	O(n)	O (안정)
힙 정렬	O(n log n)	O(n log n)	O(1) (In-place)	X (불안정)