자료구조&알고리즘 | Data Structures & Algorithms
내가 볼려고 작성한 CS 공부.
⚙️ 자료구조 & 알고리즘
✅ 1. 배열 (Array)
1.1 정의
배열은 같은 종류의 데이터를 연속된 공간에 저장하는 자료구조다.
모든 요소는 인덱스(index)를 통해 접근할 수 있다.
예: 정수 배열
[10, 20, 30, 40]→ 인덱스 0~3
1.2 특징
| 항목 | 설명 |
|---|---|
| 크기 | 처음 생성 시 고정된 크기를 가짐 |
| 메모리 배치 | 연속된 공간에 저장됨 |
| 인덱스 접근 | O(1) 시간에 가능 (매우 빠름) |
| 삽입/삭제 | 특정 위치에선 느림 (데이터 밀기/당기기 필요) |
인덱스를 통한 직접 접근이 가능하다는 점에서 가장 빠르고 단순한 구조다.
1.3 배열의 장단점
| 장점 | 단점 |
|---|---|
| 인덱스로 빠르게 접근 가능 | 크기 변경 불가 |
| 구현이 단순함 | 중간 삽입/삭제 느림 |
| 캐시 친화적 (속도 빠름) | 메모리 낭비 가능 |
1.4 메모리 구조 예시
1
2
3
배열: [7, 9, 3, 5]
인덱스: 0 1 2 3
주소: 100 104 108 112 (int형이라면 4바이트 간격)
연속된 메모리 공간에 저장되므로 주소 계산이 가능 → O(1) 접근
1.5 배열과 리스트의 차이
|항목|배열 (Array)| 연결리스트 (Linked List)| |—|—|—| |메모리| 연속된 공간 |비연속적 (포인터로 연결)| |접근 속도| 인덱스로 빠름 |순차 탐색만 가능| |삽입/삭제| 느림 (복사 필요) |빠름 (포인터만 조정)|
배열은 읽기 성능에 강하고, 연결리스트는 삽입/삭제 성능에 강하다.
1.6 실제 활용 예시
- 데이터베이스 테이블 (고정된 행렬)
- 이미지 픽셀 정보 저장
- 연산 시 빠른 조회가 필요한 상황
✅ 2. 연결 리스트 (Linked List)
2.1 정의
연결 리스트는 데이터와 다음 위치를 가리키는 포인터를 함께 저장한 노드들의 집합이다.
데이터들이 메모리상 연속되지 않아도 연결해서 사용할 수 있다.
각 노드는 값 + 다음 노드의 주소(pointer)로 구성된다.
2.2 기본 구조
1
[10 | ○ ] → [20 | ○ ] → [30 | null]
- 각 노드는
[데이터 | 포인터]형태로 구성됨 - 마지막 노드는 다음 노드가 없으므로
null또는None을 가리킴
2.3 특징
| 항목 | 설명 |
|---|---|
| 삽입/삭제 | 포인터만 조정하면 되어 빠름 |
| 접근 방식 | 순차 접근 (인덱스 직접 접근 불가) |
| 메모리 사용 | 동적으로 공간 할당 (낭비 적음) |
| 메모리 위치 | 비연속적, 필요할 때마다 새 공간 사용 |
포인터를 통해 노드끼리 연결되어 있으므로, 메모리 연속성이 없어도 됨
2.4 종류
| 유형 | 설명 |
|---|---|
| 단일 연결 리스트 | 한 방향으로만 연결됨 (next) |
| 이중 연결 리스트 | 앞뒤 양방향 연결 (prev, next) |
| 원형 연결 리스트 | 마지막 노드가 다시 첫 노드를 가리킴 (순환 구조) |
2.5 배열과의 비교
| 항목 | 연결 리스트 | 배열 |
|---|---|---|
| 메모리 배치 | 비연속적 | 연속적 |
| 접근 속도 | 느림 (순차 접근) | 빠름 (인덱스 접근) |
| 삽입/삭제 | 빠름 (포인터만 수정) | 느림 (데이터 이동 필요) |
| 메모리 크기 | 유동적 (필요할 때마다 추가) | 고정 크기 또는 재할당 필요 |
연결 리스트는 삽입과 삭제가 빈번한 작업에 유리하고,
배열은 조회가 빈번한 상황에 유리하다.
2.6 실제 활용 예시
- 운영체제의 프로세스 관리 큐
- 브라우저의 방문 기록 (이중 연결 리스트)
- 메모리 동적 할당 관리 (free list)
✅ 3. 스택 (Stack)
3.1 정의
스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조다.
가장 마지막에 들어온 데이터가 가장 먼저 나간다.
이를 후입선출(Last-In, First-Out, LIFO) 구조라고 한다.
3.2 기본 구조
1
2
[ 1 | 2 | 3 | 4 ] ← top
(4가 가장 최근에 추가된 요소, pop 시 가장 먼저 제거됨)
push: 데이터를 스택에 넣는 연산pop: 스택에서 데이터를 꺼내는 연산peek또는top: 스택의 맨 위 값을 확인 (제거는 하지 않음)
3.3 특징
| 항목 | 설명 |
|---|---|
| 구조 | 한 방향(위쪽)에서만 접근 가능 |
| 삽입/삭제 | 항상 같은 위치(top)에서 수행 |
| 사용 방식 | 후입선출 (LIFO) |
| 메모리 | 일반적으로 배열 또는 연결 리스트로 구현됨 |
스택은 구조가 단순하고, 함수 호출이나 실행 흐름 제어에 매우 적합하다.
3.4 배열 vs 연결 리스트 기반 구현
| 기준 | 배열 기반 | 연결 리스트 기반 |
|---|---|---|
| 메모리 크기 | 고정 크기 필요 | 동적으로 늘어남 |
| 속도 | 인덱스 접근 빠름 | 삽입/삭제가 유연함 |
| 구현 | 단순함 | 약간 복잡함 |
3.5 실제 활용 예시
- 함수 호출 시 호출 스택(Call Stack) 사용
- 웹 브라우저의 뒤로 가기/앞으로 가기 기능
- 수식 계산, 괄호 검사
- 깊이 우선 탐색(DFS) 알고리즘의 기본 구조
✅ 4. 큐 (Queue)
4.1 정의
큐는 먼저 들어온 데이터가 먼저 나가는 자료구조다.
이를 선입선출(First-In, First-Out, FIFO) 구조라고 한다.
줄을 서는 구조를 떠올리면 이해가 쉽다.
먼저 들어간 데이터가 먼저 나와야 순서가 맞다.
4.2 기본 구조
1
2
front → [ A ][ B ][ C ][ D ] ← rear
(dequeue는 A부터, enqueue는 D 뒤에 추가)
enqueue: 데이터를 큐에 넣는 연산 (뒤에서)dequeue: 데이터를 큐에서 꺼내는 연산 (앞에서)peek또는front: 맨 앞의 데이터를 확인
4.3 특징
| 항목 | 설명 |
|---|---|
| 구조 | 앞(front)에서 꺼내고, 뒤(rear)에서 추가 |
| 삽입/삭제 | 양쪽이 다름 (스택과 비교됨) |
| 사용 방식 | 선입선출 (FIFO) |
| 구현 방식 | 배열 또는 연결 리스트 기반으로 구현 가능 |
큐는 순서를 유지하면서 처리해야 하는 작업에 적합하다.
4.4 큐의 종류
| 종류 | 설명 |
|---|---|
| 일반 큐 | 가장 기본적인 선입선출 구조 |
| 원형 큐 | 배열 기반 큐에서 공간 재활용을 위해 순환 구조 사용 |
| 덱(Deque) | 양쪽에서 삽입/삭제가 모두 가능한 큐 |
| 우선순위 큐 | 값의 우선순위에 따라 먼저 꺼냄 (힙 기반으로 구현됨) |
4.5 스택과의 비교
| 항목 | 스택 | 큐 |
|---|---|---|
| 제거 위치 | top (맨 위) | front (맨 앞) |
| 접근 순서 | 후입선출 (LIFO) | 선입선출 (FIFO) |
| 사용 예시 | 함수 호출, DFS | 작업 스케줄링, BFS |
4.6 실제 활용 예시
- 운영체제의 프로세스 스케줄링 큐
- 인쇄 대기열, 요청 처리 순서
- 너비 우선 탐색(BFS) 알고리즘의 핵심 구조
- 실시간 메시지 처리 시스템 (예: Kafka, RabbitMQ 등)
✅ 5. 트리 (Tree)
5.1 정의
트리는 계층적인 구조를 표현할 수 있는 비선형 자료구조다.
여러 노드가 부모-자식 관계를 이루며 연결되어 있다.
예: 폴더 구조, 가계도, 조직도 등
5.2 기본 용어
| 용어 | 설명 |
|---|---|
| 노드(Node) | 트리의 구성 요소 (데이터를 담고 있음) |
| 루트(Root) | 트리의 시작점 (부모가 없는 노드) |
| 부모/자식 | 한 노드 아래 연결된 하위 노드 관계 |
| 리프(Leaf) | 자식이 없는 노드 (말단 노드) |
| 깊이(Depth) | 루트에서 특정 노드까지의 거리 |
| 높이(Height) | 노드에서 리프까지 가장 먼 거리 |
1
2
3
4
5
6
예시 트리 구조:
A
/ \
B C
/ \ \
D E F
- 루트: A
- 자식 노드: B, C
- 리프 노드: D, E, F
- B의 부모는 A, B의 자식은 D와 E
5.3 특징
| 항목 | 설명 |
|---|---|
| 구조 | 순환이 없는 계층적 구조 |
| 탐색 | DFS, BFS 등 다양한 순회 방식 존재 |
| 노드 수 | N개의 노드 → 항상 N-1개의 간선 |
| 구현 | 재귀적 구조와 잘 어울림 |
5.4 이진 트리
모든 노드가 최대 2개의 자식 노드를 가지는 트리
- 왼쪽 자식: left child
- 오른쪽 자식: right child
이진 트리는 가장 많이 사용되는 트리의 기본형이다.
5.5 이진 탐색 트리 (BST)
이진 탐색 트리는 왼쪽 < 루트 < 오른쪽의 조건을 만족하는 이진 트리다.
| 노드 위치 | 조건 |
|---|---|
| 왼쪽 자식 | 루트보다 작음 |
| 오른쪽 자식 | 루트보다 큼 |
BST에서는 탐색, 삽입, 삭제가 평균 O(log n)의 효율을 가진다.
단, 편향 트리가 되면 최악의 경우 O(n)
5.6 트리의 순회 (Traversal)
| 방식 | 설명 |
|---|---|
| 전위 순회 (Preorder) | 루트 → 왼쪽 → 오른쪽 |
| 중위 순회 (Inorder) | 왼쪽 → 루트 → 오른쪽 (BST일 경우 정렬됨) |
| 후위 순회 (Postorder) | 왼쪽 → 오른쪽 → 루트 |
| 레벨 순회 (Level Order) | 위에서 아래로, 왼쪽에서 오른쪽으로 (BFS 기반) |
5.7 실제 활용 예시
- 파일 시스템 구조 (폴더/파일)
- 데이터베이스 인덱스(B+ Tree)
- HTML DOM 트리 구조
- AI 게임 트리, 계산식 파싱, 이진 힙/우선순위 큐
✅ 6. 그래프 (Graph)
6.1 정의
그래프는 노드(정점, vertex)와 노드 간 연결(간선, edge)으로 이루어진 자료구조다.
사람 간 관계, 도로망, 네트워크 등 복잡한 연결 구조를 표현할 수 있다.
1
2
3
4
예시 그래프:
A --- B
| |
D --- C
- 정점: A, B, C, D
- 간선: (A-B), (B-C), (C-D), (A-D)
6.2 특징
| 항목 | 설명 |
|---|---|
| 정점(Vertex) | 연결의 주체 (노드) |
| 간선(Edge) | 정점 간의 연결선 |
| 방향성 | 방향 그래프 / 무방향 그래프 |
| 가중치 | 간선에 비용(weight)이 있을 수도 있음 |
| 순환성 | 순환(사이클)이 있을 수도 있음 |
그래프는 트리보다 자유로운 구조이며,
루트나 계층 개념이 없음
6.3 종류
| 분류 기준 | 유형 | 설명 |
|---|---|---|
| 방향성 | 무방향 그래프 | 양방향 연결 (A-B = B-A) |
| 방향 그래프 | 방향 있는 연결 (A→B ≠ B→A) | |
| 가중치 | 가중치 그래프 | 간선마다 비용이 있음 (예: 지도, 비용) |
| 비가중치 그래프 | 간선에 특별한 값 없음 | |
| 사이클 | 순환 그래프 | 한 바퀴 돌아 제자리로 돌아올 수 있음 |
| 비순환 그래프 | 순환이 없음 (예: 트리) |
6.4 표현 방식
| 방식 | 설명 |
|---|---|
| 인접 행렬 (Adjacency Matrix) | 정점 간 연결을 2차원 배열로 표시 (공간 복잡도 O(n²)) |
| 인접 리스트 (Adjacency List) | 연결된 정점만 리스트로 저장 (공간 효율 O(n + e)) |
대부분의 경우 인접 리스트가 메모리 효율이 좋다.
6.5 그래프 탐색
| 알고리즘 | 설명 |
|---|---|
| DFS (깊이 우선 탐색) | 한 방향으로 깊게 들어갔다가, 더 이상 갈 곳 없으면 되돌아옴 |
| BFS (너비 우선 탐색) | 가까운 정점부터 차례대로 방문 (큐 사용) |
DFS는 재귀적 구조와 잘 어울리고,
BFS는 최단 거리 탐색에 자주 사용된다.
6.6 실제 활용 예시
- 소셜 네트워크 친구 추천
- 지도 및 길찾기 알고리즘 (다익스트라, A*)
- 컴파일 순서 계산 (위상 정렬)
- 네트워크 패킷 라우팅
- 웹 크롤링 (링크 연결 구조)
✅ 7. 힙 (Heap)
7.1 정의
힙은 완전 이진 트리를 기반으로 한 우선순위 기반 자료구조다.
항상 최댓값 또는 최솟값이 루트에 위치하도록 구성된다.
힙은 정렬된 구조는 아니지만, 루트를 기준으로 부분 정렬 성질을 가진다.
7.2 종류
| 종류 | 설명 |
|---|---|
| 최소 힙 (Min Heap) | 부모 노드 ≤ 자식 노드 → 루트는 최솟값 |
| 최대 힙 (Max Heap) | 부모 노드 ≥ 자식 노드 → 루트는 최댓값 |
1
2
3
4
5
6
최소 힙 예시:
3
/ \
8 10
/ \
15 20
- 루트가 항상 가장 작은 값(3)을 유지
7.3 특징
| 항목 | 설명 |
|---|---|
| 구조 | 완전 이진 트리 (왼쪽부터 채우는 트리) |
| 정렬 | 전체 정렬은 아님, 부모-자식 간 규칙만 유지 |
| 삽입 | 마지막 위치에 넣고 위로 올리며 정렬 (heapify-up) |
| 삭제 | 루트를 제거하고 마지막 노드를 루트로 옮긴 뒤 아래로 정렬 (heapify-down) |
힙은 배열로 구현할 수 있으며, 자식 인덱스를 수학적으로 계산해 접근한다.
7.4 배열 기반 인덱스 규칙
| 관계 | 인덱스 계산 방식 (0-based) |
|---|---|
| 부모 → 자식 | 왼쪽 = 2i + 1, 오른쪽 = 2i + 2 |
| 자식 → 부모 | 부모 = ⌊(i - 1) / 2⌋ |
1
예: 배열 [3, 8, 10, 15, 20] → 최소 힙 구조
- 루트 인덱스: 0 (값: 3)
- 자식 인덱스: 1(8), 2(10)
- 자식의 자식: 3(15), 4(20)
7.5 힙의 시간 복잡도
| 연산 | 시간 복잡도 |
|---|---|
| 삽입 | O(log n) |
| 삭제 (최댓값/최솟값) | O(log n) |
| 최댓값/최솟값 확인 | O(1) |
트리의 높이가 log n이기 때문에, 삽입과 삭제 모두 로그 시간에 처리된다.
7.6 실제 활용 예시
- 우선순위 큐 구현 (Priority Queue)
- 힙 정렬 (Heap Sort) 알고리즘
- 실시간 최댓값/최솟값 유지
- 다익스트라 알고리즘에서 최단 거리 선택
✅ 8. 해시테이블 (Hash Table)
8.1 정의
해시테이블은 키(key)를 통해 값(value)을 빠르게 찾을 수 있는 자료구조다.
내부적으로 해시 함수(hash function)를 사용해 데이터를 배열 인덱스로 변환하여 저장한다.
배열처럼 빠른 접근(O(1)) + 키 기반 검색의 장점을 동시에 갖는다.
8.2 동작 원리
- 데이터를 저장할 때, 키를 해시 함수에 넣는다.
- 해시 함수는 고유한 인덱스를 계산해낸다.
- 그 인덱스에 값을 저장하거나 가져온다.
1
예: key = "apple" → hash("apple") → index 3 → table[3] = 120
8.3 해시 함수란?
해시 함수는 키를 입력받아 고정된 범위의 정수값(배열 인덱스)으로 변환하는 함수다.
좋은 해시 함수는 서로 다른 키가 같은 위치로 가지 않도록 충돌을 줄이는 것이 핵심이다.
8.4 충돌(Collision)과 해결 방법
충돌이란 서로 다른 키가 같은 인덱스로 해시되는 현상이다.
| 방식 | 설명 |
|---|---|
| 체이닝 (Chaining) | 같은 인덱스에 여러 값을 리스트로 저장 |
| 오픈 주소법 (Open Addressing) | 빈 인덱스를 찾아 다음 위치에 저장 (선형 탐사 등) |
충돌은 완전히 피할 수 없기 때문에, 효율적인 충돌 처리 전략이 중요하다.
8.5 시간 복잡도
| 연산 | 평균 시간 | 최악 시간 (충돌 시) |
|---|---|---|
| 검색 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
충돌이 적을수록 평균적으로 매우 빠른 성능을 보인다.
8.6 실제 활용 예시
- 딕셔너리(dictionary) 또는 Map 자료형
- 중복 검사 (ex: 방문 체크, 캐시 시스템)
- 학생번호 → 성적, 사용자ID → 정보 등 키-값 저장
- 알고리즘 문제에서 빠른 탐색 요구 시 자주 사용됨
✅ 9. 탐색 & 정렬 알고리즘
9.1 탐색 (Searching)
탐색은 데이터 집합에서 원하는 값을 찾는 과정이다.
정렬 여부에 따라 사용할 수 있는 알고리즘이 달라진다.
9.1.1 선형 탐색 (Linear Search)
데이터를 처음부터 끝까지 순서대로 확인하면서 원하는 값을 찾는다.
| 특징 | 설명 |
|---|---|
| 정렬 필요 여부 | 정렬되지 않아도 됨 |
| 시간 복잡도 | O(n) |
| 장점 | 단순하고 구현 쉬움 |
| 단점 | 느림, 대량 데이터에 부적합 |
9.1.2 이진 탐색 (Binary Search)
정렬된 데이터에서만 사용할 수 있는 효율적인 탐색 방법.
중간 값을 기준으로 좌/우를 나누며 탐색 범위를 반씩 줄인다.
| 특징 | 설명 |
|---|---|
| 정렬 필요 여부 | 필수 (오름차순 등) |
| 시간 복잡도 | O(log n) |
| 장점 | 빠름 |
| 단점 | 정렬된 상태만 사용 가능 |
1
예: [10, 20, 30, 40, 50] → 찾는 값 30
중간값 30과 비교 → 바로 찾음
9.2 정렬 (Sorting)
정렬은 데이터를 일정한 기준(크기, 알파벳 등)에 따라 순서대로 재배열하는 작업이다.
정렬을 하면:
- 이진 탐색 가능
- 데이터 분석, 중복 제거, 출력 등에 유리
9.2.1 버블 정렬 (Bubble Sort)
인접한 두 값을 비교하고 교환하는 방식.
가장 큰 수가 점점 뒤로 “떠오르는” 느낌.
| 시간 복잡도 | O(n²) |
| 구현 난이도 | 매우 쉬움 |
| 효율성 | 낮음 (연습용, 소규모 데이터에만 사용) |
9.2.2 선택 정렬 (Selection Sort)
가장 작은 값을 찾아서 맨 앞과 교환하는 방식.
| 시간 복잡도 | O(n²) |
| 교환 횟수 | 적음 |
| 안정성 | 불안정 정렬 |
9.2.3 삽입 정렬 (Insertion Sort)
정렬된 부분에 하나씩 삽입하면서 확장해나가는 방식.
| 시간 복잡도 | 평균 O(n²), 거의 정렬된 경우 O(n) |
| 특징 | 단순하고 직관적 |
9.2.4 병합 정렬 (Merge Sort)
데이터를 반으로 나눈 뒤 정렬하고 병합하는 분할 정복 방식
| 시간 복잡도 | O(n log n) |
| 안정성 | 안정 정렬 |
| 특징 | 추가 메모리 사용 |
9.2.5 퀵 정렬 (Quick Sort)
기준값(pivot)을 잡고, 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬
| 시간 복잡도 | 평균 O(n log n), 최악 O(n²) |
| 특징 | 빠르고 메모리 효율적 |
9.2.6 힙 정렬 (Heap Sort)
힙(우선순위 큐)을 활용해 정렬하는 방식
| 항목 | 설명 |
|---|---|
| 시간 복잡도 | O(n log n) |
| 특징 | 메모리 추가 필요 없음 (제자리 정렬) |
9.3 정렬 알고리즘 비교 요약
| 정렬 알고리즘 | 시간복잡도 | 공간복잡도 | 특징 |
|---|---|---|---|
| 버블 / 선택 / 삽입 | O(n²) | O(1) | 구현은 쉬우나 비효율적 |
| 병합 정렬 | O(n log n) | O(n) | 안정적이지만 메모리 사용 |
| 퀵 정렬 | 평균 O(n log n) | O(log n) | 빠르지만 최악 O(n²) 가능 |
| 힙 정렬 | O(n log n) | O(1) | 공간 효율적, 불안정 정렬 |
✅ 10. 재귀와 백트래킹
10.1 재귀 (Recursion)
재귀는 함수가 자기 자신을 호출하는 방식이다.
큰 문제를 같은 형태의 더 작은 문제로 나눠서 해결할 때 유용하다.
1
2
3
4
예: 팩토리얼
5! = 5 × 4!
= 5 × 4 × 3!
= ...
10.1.1 구조
- Base Case (종료 조건): 더 이상 재귀 호출하지 않음
- Recursive Case (재귀 호출): 자기 자신을 호출함
1
2
3
4
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
재귀 호출은 스택(stack) 을 기반으로 동작한다.
너무 깊어지면 스택 오버플로우가 발생할 수 있다.
10.1.2 재귀 vs 반복
| 항목 | 재귀 | 반복 |
|---|---|---|
| 이해 | 더 직관적 | 명확한 흐름 |
| 성능 | 느릴 수 있음 (호출 비용) | 빠름 |
| 용도 | 트리, DFS 등 구조적 문제 | 단순 반복, 누적 계산 등 |
10.2 백트래킹 (Backtracking)
백트래킹은 가능한 모든 경우를 탐색하면서,
조건에 맞지 않으면 되돌아가서 다른 경로를 시도하는 방식이다.
완전탐색(브루트포스)이지만, 불필요한 경로는 빨리 포기한다는 점이 핵심이다.
10.2.1 핵심 원리
- 어떤 선택을 하고
- 다음 단계로 진행
- 실패 시, 직전 상태로 되돌아감
- 다른 선택지를 시도
가능한 해를 모두 탐색하되, 유망하지 않으면 가지치기(pruning) 한다.
10.2.2 예시 문제
- N-Queen 문제
- 미로 탈출
- 순열/조합/부분집합 생성
10.2.3 예제 코드 – 순열 생성
1
2
3
4
5
6
def permute(nums, path=[]):
if not nums:
print(path)
return
for i in range(len(nums)):
permute(nums[:i] + nums[i+1:], path + [nums[i]])
위 코드에서 각 재귀 호출은 한 가지 선택지를 정하고,
나머지 숫자에 대해 재귀적으로 다시 탐색하는 구조다.
10.2.4 시간복잡도
| 상황 | 복잡도 예시 |
|---|---|
| 순열 생성 | O(n!) |
| 조합 생성 | O(2ⁿ) |
| 조건 가지치기 포함 | 훨씬 줄어듦 (효율적 백트래킹) |
백트래킹은 지수 시간이 걸릴 수 있으므로,
가지치기 조건이 굉장히 중요하다.
✅ 11. 동적 프로그래밍 (Dynamic Programming)
11.1 정의
동적 프로그래밍(DP)은 문제를 작은 부분 문제로 나누고,
한 번 계산한 결과를 저장(Memoization) 해서 중복 계산을 피하는 최적화 기법이다.
재귀 + 캐시 = DP
같은 하위 문제를 반복해서 푸는 경우에 매우 효과적이다.
11.2 조건 (DP를 사용할 수 있는 경우)
- 중복되는 부분 문제가 존재해야 함
같은 계산을 여러 번 반복하는 경우
- 최적 부분 구조를 가져야 함
전체 문제의 최적해가 부분 문제의 최적해로 구성됨
11.3 메모이제이션 vs 타뷸레이션
| 방식 | 설명 | 구현 방법 |
|---|---|---|
| 메모이제이션 | Top-down 방식 (재귀 + 캐시) | 함수 호출하면서 결과 저장 |
| 타뷸레이션 | Bottom-up 방식 | 작은 문제부터 차례로 해결 |
보통은 재귀 + 캐시 형태로 많이 사용하지만,
반복문 기반의 타뷸레이션이 더 빠르고 안정적일 수 있다.
11.4 피보나치 수열 예시
일반 재귀 (비효율적)
1
2
3
4
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
O(2ⁿ)의 시간 복잡도 → 중복 호출이 많음
메모이제이션 방식
1
2
3
4
5
6
7
8
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
타뷸레이션 방식
1
2
3
4
5
def fib(n):
dp = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
O(n) 시간에 계산 가능
이전 값을 저장하면서 효율적 계산
11.5 DP 문제의 일반적인 접근법
- 점화식(상태 정의) 세우기
- base case 정의하기
- 상향식 또는 하향식 구현
문제에서 “최댓값, 최소값, 경우의 수, 길이, 비용”을 묻는다면
DP 적용을 의심해보는 게 좋다
11.6 대표 문제 예시
- 피보나치 수열
- 계단 오르기
- 배낭 문제 (Knapsack)
- 최장 증가 부분 수열 (LIS)
- 격자 경로 탐색 (DP 테이블)
11.7 시간/공간 복잡도
| 구현 방식 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 메모이제이션 | O(n) | O(n) |
| 타뷸레이션 | O(n) | O(n) or O(1) (공간 최적화 시) |
공간 최적화는 최근 값 두 개만 저장해서 구현 가능 (예: 피보나치)
✅ 12. 시간복잡도 & 공간복잡도
12.1 시간복잡도 (Time Complexity)
알고리즘이 입력 크기(n) 에 따라 얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것
핵심은 “입력 크기가 커질수록 얼마나 느려지는가“를 분석하는 것
주요 시간복잡도 종류
| 표기 | 의미 | 예시 |
|---|---|---|
| O(1) | 상수 시간 (입력 크기와 무관) | 배열 인덱스 접근 |
| O(log n) | 로그 시간 | 이진 탐색 |
| O(n) | 선형 시간 | 선형 탐색 |
| O(n log n) | 로그 선형 | 병합정렬, 퀵정렬 평균 |
| O(n²) | 이차 시간 | 이중 반복문, 버블 정렬 |
| O(2ⁿ), O(n!) | 지수적 시간 | 백트래킹, 완전탐색 |
Big-O 표기법은 최악의 경우를 기준으로 한다.
12.2 공간복잡도 (Space Complexity)
알고리즘이 동작 중 사용하는 메모리의 양을 입력 크기 n에 따라 분석한 것
| 공간 복잡도 예시 | 설명 |
|---|---|
| O(1) | 변수 몇 개만 사용 (정적 공간) |
| O(n) | 배열, 리스트 등 입력 크기만큼 공간 필요 |
| O(n²) | 2차원 배열 (예: 그래프 인접 행렬) |
공간 최적화는 시간과의 trade-off를 고려해서 설계해야 한다.
12.3 분석 시 주의점
- 상수, 미세한 차이는 무시하고 큰 틀만 본다
O(2n) → O(n), O(n + log n) → O(n)
- 최악/평균/최선의 시간복잡도를 구분하는 경우도 있다
12.4 예시 분석
예 1: 이중 반복문
1
2
3
for i in range(n):
for j in range(n):
print(i, j)
O(n²)
예 2: 로그 탐색
1
2
3
4
5
6
7
8
9
10
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
O(log n)
12.5 시간복잡도 비교 차트
| 입력 크기(n) | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | ✔️ | ✔️ | ✔️ | ✔️ | ✔️ | 느림 |
| 100 | ✔️ | ✔️ | ✔️ | ✔️ | 느림 | ❌ |
| 1,000 | ✔️ | ✔️ | ✔️ | ✔️ | ❌ | ❌❌ |
| 100,000 | ✔️ | ✔️ | ✔️ | 경계 | ❌❌ | ❌❌❌ |
O(n log n)보다 느린 알고리즘은 대규모 입력에서는 사용 불가