graph LR
subgraph BigOLadder["Big-O 시간 복잡도 사다리 (왼쪽이 압도적으로 빠름)"]
O1["O(1) 상수 시간"] --> OlogN["O(log N) 로그 시간"]
OlogN --> ON["O(N) 선형 시간"]
ON --> ONlogN["O(N log N) 선형로그 시간"]
ONlogN --> ON2["O(N^2) 이차 시간"]
ON2 --> O2N["O(2^N) 지수 시간"]
O2N --> ONfact["O(N!) 팩토리얼 시간 (재앙)"]
end
style O1 fill:#DCFCE7,stroke:#16A34A,stroke-width:2px;
style OlogN fill:#DCFCE7,stroke:#16A34A,stroke-width:2px;
style ON fill:#BAE6FD,stroke:#0284C7,stroke-width:2px;
style ONlogN fill:#BAE6FD,stroke:#0284C7,stroke-width:2px;
style ON2 fill:#FEF3C7,stroke:#D97706,stroke-width:2px;
style O2N fill:#FEE2E2,stroke:#EF4444,stroke-width:2px;
style ONfact fill:#FEE2E2,stroke:#DC2626,stroke-width:2px;
0. 알고리즘은 ’연산 비용(돈)’을 아끼는 기술이다
많은 개발자가 알고리즘을 “취업 코딩 테스트용 문제 풀이”로 오해합니다. 하지만 클라우드 컴퓨팅 시대에 알고리즘은 회사의 서버 비용(AWS 청구서)과 직결되는 공학 기술입니다.
데이터가 100만 건일 때: * \(O(N^2)\) 알고리즘은 연산 횟수가 1조 번 (\(1,000,000,000,000\))에 달해 서버 CPU를 100% 태우며 수 분 동안 멈춰버립니다. * \(O(N \log N)\) 알고리즘은 단 2,000만 번 (\(20,000,000\))의 연산으로 0.05초 만에 완료됩니다.
알고리즘의 본질은 “유한한 컴퓨터 자원(CPU 시간과 메모리)을 아끼기 위해 문제를 어떻게 쪼개고 다룰 것인가”에 있습니다.
[탐색 알고리즘 군] 1 ~ 3
1. 선형 탐색 (Linear Search)
- 개념: 데이터의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾는 가장 단순한 탐색 기법입니다.
- 시간 복잡도: 최선 \(O(1)\), 평균 및 최악 \(O(N)\)
- 실무 활용: 데이터가 정렬되어 있지 않거나 크기가 수십 개 이하로 매우 작을 때 가장 직관적으로 사용됩니다.
2. 이진 탐색 (Binary Search)
개념: 정렬된 배열에서 중앙값을 확인하고, 타겟 값과의 대소 관계에 따라 탐색 범위를 매번 절반씩 날려버리는 분할 정복 기법입니다.
시간 복잡도: \(O(\log N)\) (40억 개 데이터도 단 32번의 비교로 탐색 완료)
핵심 코드:
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 return -1
3. 파라메트릭 서치 (Parametric Search)
- 개념: “조건을 만족하는 최댓값/최솟값을 구하라”는 최적화 문제를 “이 값으로 조건을 만족하는가?(Yes/No)”라는 결정 문제로 변환하여 이진 탐색으로 해를 좁혀가는 기법입니다.
- 시간 복잡도: 결정 문제 검증 비용이 \(O(K)\)일 때 \(O(K \log(\text{Range}))\)
- 실무 활용: 라우터 대역폭 쓰로틀링 임계치 탐색, 동영상 버퍼링 최적 비트레이트 결정, 떡볶이 떡 자르기(백준 2805번).
[정렬 알고리즘 군] 4 ~ 8
4. 기초 정렬 3종 (버블·선택·삽입 정렬)
- 개념:
- 버블 정렬(Bubble): 인접한 두 원소를 비교하여 큰 값을 뒤로 계속 밀어냅니다.
- 선택 정렬(Selection): 남은 구간에서 최솟값을 찾아 맨 앞과 교환합니다.
- 삽입 정렬(Insertion): 새로운 원소를 이미 정렬된 앞쪽 구간의 적절한 위치에 끼워 넣습니다. (부분 정렬 시 \(O(N)\) 근접)
- 시간 복잡도: \(O(N^2)\), 공간 복잡도 \(O(1)\)
5. 퀵 정렬 (Quick Sort)
- 개념: 하나의 기준값(Pivot)을 골라 피벗보다 작은 그룹과 큰 그룹으로 쪼갠 뒤 재귀적으로 정렬하는 알고리즘입니다.
- 시간 복잡도: 평균 \(O(N \log N)\), 최악 \(O(N^2)\) (이미 정렬된 배열에서 편향 피벗 선택 시)
- 강점: CPU 캐시 지역성(Locality)이 매우 우수하여 실무에서 평균 속도가 대단히 빠릅니다.
6. 병합 정렬 (Merge Sort)
- 개념: 배열을 원소가 1개가 될 때까지 절반으로 쪼갠 뒤, 정렬하면서 하나로 합쳐 나가는 완전한 분할 정복(Divide and Conquer) 방식입니다.
- 시간 복잡도: 최선/평균/최악 모두 \(O(N \log N)\) 보장, 공간 복잡도 \(O(N)\)
- 특징: 동일한 값의 원래 순서가 유지되는 안정 정렬(Stable Sort)이며, 대용량 외장 정렬(External Sort)의 뼈대입니다.
7. 힙 정렬 (Heap Sort)
- 개념: 정렬할 데이터를 완전 이진 트리 기반의 최대 힙(Max Heap)에 넣었다가 루트 노드를 하나씩 꺼내어 정렬하는 방식입니다.
- 시간 복잡도: 모든 경우 \(O(N \log N)\), 공간 복잡도 \(O(1)\)
- 특징: 추가 메모리 버퍼 없이도 최악의 경우에 \(O(N \log N)\)을 철저히 보장합니다.
8. 팀소트 (Timsort)
- 개념: 삽입 정렬과 병합 정렬의 장점을 결합한 하이브리드 정렬 알고리즘으로, 현대 언어(Python
sorted(), JavaArrays.sort())의 표준 엔진입니다. - 시간 복잡도: 최선 \(O(N)\), 평균 및 최악 \(O(N \log N)\)
- 동작 원리: 실제 현실의 데이터는 무작위가 아니라 부분적으로 이미 정렬되어 있는 덩어리(Run)가 많다는 점에 착안하여, 기존 정렬 흐름을 그대로 활용합니다.
[선형 최적화 기법] 9 ~ 10
graph LR
subgraph TwoPointer["투 포인터 (양 끝에서 좁혀오기)"]
L["Left ->"] --- Mid["... 구간 탐색 ..."] --- R["<- Right"]
end
subgraph SlideWindow["슬라이딩 윈도우 (고정 크기 윈도우 이동)"]
W1["[ a, b, c ] d, e"] --> W2["a, [ b, c, d ] e"]
end
style TwoPointer fill:#E0F2FE,stroke:#0284C7,stroke-width:1px;
style SlideWindow fill:#DCFCE7,stroke:#16A34A,stroke-width:1px;
9. 투 포인터 (Two Pointers)
개념: 정렬된 1차원 배열에서 두 개의 인덱스 포인터(Left, Right)를 서로 반대 방향이나 같은 방향으로 움직이며 조건을 만족하는 구간을 단 한 번의 순회로 찾아냅니다.
시간 복잡도: 이중 루프 \(O(N^2)\) 문제를 단 \(O(N)\)으로 단축
핵심 코드:
# 정렬된 배열에서 두 수의 합이 target이 되는 쌍 찾기 def two_sum(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return (left, right) elif s < target: left += 1 else: right -= 1 return None
10. 슬라이딩 윈도우 (Sliding Window)
- 개념: 배열이나 문자열에서 고정된 크기(또는 가변 크기)의 윈도우(창문)를 오른쪽으로 한 칸씩 밀어가며 중복 연산을 제거하는 기법입니다.
- 시간 복잡도: \(O(N)\)
- 실무 활용: 최근 7일간의 이동 평균 매출 계산, TCP 네트워크 패킷 흐름 제어, 문자열 내 아나그램 탐색.
[그래프 탐색 및 백트래킹] 11 ~ 13
11. 너비 우선 탐색 (BFS - Breadth-First Search)
- 개념: 큐(Queue)를 사용하여 시작 정점에서 가까운 이웃(1촌, 2촌, 3촌)부터 수평으로 넓게 퍼져나가며 탐색합니다.
- 시간 복잡도: 인접 리스트 기준 \(O(V + E)\)
- 핵심 특성: 가중치가 없는 그래프에서 시작점부터 목표점까지의 ‘최단 경로(최소 이동 횟수)’를 수학적으로 보장합니다.
12. 깊이 우선 탐색 (DFS - Depth-First Search)
- 개념: 스택이나 재귀 함수를 사용하여 갈 수 있는 경로가 끝날 때까지 한 우물만 깊게 파고든 뒤, 막히면 직전 갈림길로 되돌아와 다른 경로를 탐색합니다.
- 시간 복잡도: \(O(V + E)\)
- 실무 활용: 미로 탈출의 모든 경로 경우의 수 탐색, 그래프 내 사이클(Cycle) 존재 유무 판별, 연결 요소(Connected Component) 개수 세기.
13. 백트래킹 (Backtracking)
- 개념: 해를 찾아가는 도중 현재 경로가 정답이 될 가능성이 없다고 판단되면, 더 이상 깊이 들어가지 않고 즉시 가지치기(Pruning)하여 이전 상태로 되돌아가는 지능형 완전 탐색입니다.
- 시간 복잡도: 최악 \(O(2^N)\) 또는 \(O(N!)\)이지만, 효율적인 가지치기로 실질 탐색 공간을 극적으로 압축합니다.
- 대표 문제: N-Queens 문제, 스도쿠 풀이, 외판원 순회 문제(TSP).
[최단 경로 알고리즘 군] 14 ~ 17
flowchart TD
Q{"그래프 최단 경로 알고리즘 선택 가이드"}
Q -->|가중치 없음| BFS["11. BFS (O(V+E))"]
Q -->|양수 가중치 1:N| Dijk["14. 다익스트라 (O((V+E) log V))"]
Q -->|음수 가중치 존재| Bell["15. 벨만-포드 (O(VE))"]
Q -->|모든 노드 쌍 N:N| Floyd["16. 플로이드-워셜 (O(V^3))"]
Q -->|좌표/목적지 휴리스틱| AStar["17. A* 알고리즘 (게임/내비게이션)"]
style Q fill:#F1F5F9,stroke:#475569,stroke-width:2px;
style Dijk fill:#DCFCE7,stroke:#16A34A,stroke-width:1px;
style AStar fill:#BAE6FD,stroke:#0284C7,stroke-width:1px;
14. 다익스트라 (Dijkstra)
- 개념: 시작점에서부터 다른 모든 정점까지의 최단 거리를 그리디(Greedy)하게 확정해 나가는 알고리즘입니다. 모든 간선의 가중치가 0 이상(양수)이어야 합니다.
- 시간 복잡도: 우선순위 큐(Min Heap) 사용 시 \(O((V + E) \log V)\)
- 실무 활용: 전국 고속도로 및 내비게이션 최단 주행 시간 산출, 네트워크 OSPF 라우팅 프로토콜.
15. 벨만-포드 (Bellman-Ford)
- 개념: 모든 간선에 대해 완화(Relaxation) 작업을 \(V-1\)번 반복하여 최단 거리를 갱신합니다. 음수 가중치 간선이 있어도 정상 작동합니다.
- 시간 복잡도: \(O(VE)\)
- 핵심 기능: \(V\)번째 순회에서도 거리가 줄어드는 간선이 있다면 ’음수 사이클(무한 루프 감가)’이 존재함을 즉시 감지합니다. (환율 차익 재정거래 탐지)
16. 플로이드-워셜 (Floyd-Warshall)
- 개념: 3중 반복문을 통해 “노드 \(k\)를 거쳐서 가는 경로가 기존 경로보다 더 짧은가?”를 점진적으로 검토하는 2차원 DP 기반 알고리즘입니다.
- 시간 복잡도: \(O(V^3)\)
- 점화식: \(D[i][j] = \min(D[i][j], D[i][k] + D[k][j])\)
- 실무 활용: 정점 개수가 500개 이하인 소규모 네트워크에서 모든 출발점과 모든 도착점 쌍 간의 최단 거리 표를 한 번에 뽑아낼 때 유용합니다.
17. A* (A-Star) 탐색 알고리즘
- 개념: 다익스트라에 목적지까지의 예상 직선거리인 휴리스틱 함수 \(h(n)\)을 결합하여, 목표 지점 방향의 유망한 노드를 우선적으로 탐색하는 최고 성능의 길찾기 알고리즘입니다.
- 평가 함수: \(f(n) = g(n) + h(n)\) (시작점부터 현재까지 실제 비용 + 목적지까지의 추정 비용)
- 실무 활용: 스타크래프트/RPG 게임 유닛의 장애물 회피 길찾기, 자율주행 로봇 주행 경로 생성.
[최적화 및 의존성 분석] 18 ~ 20
18. 그리디 알고리즘 (Greedy)
- 개념: 전체를 고려하지 않고 현재 시점에서 가장 좋아 보이는 최선의 선택만을 반복하여 최종 해답에 도달하는 기법입니다.
- 성립 2대 조건:
- 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 뒤의 선택에 영향을 주지 않음.
- 최적 부분 구조(Optimal Substructure): 부분 문제의 최적해가 전체 문제의 최적해로 이어짐.
- 실무 예시: 거스름돈 동전 개수 최소화, 회의실 배정 스케줄링, 허프만 인코딩.
19. 동적 계획법 (Dynamic Programming, DP)
- 개념: 큰 문제를 작은 하위 문제로 쪼갠 뒤, 이미 계산한 하위 문제의 정답을 메모리에 저장(메모이제이션/타뷸레이션)하여 중복 연산을 0으로 만드는 최적화 기법입니다.
- 접근법: Top-Down (재귀 + 메모이제이션) vs Bottom-Up (반복문 + DP 테이블 채우기)
- 대표 유형: 배낭 문제(Knapsack 0/1), 최장 증가 부분 수열(LIS), 문자열 편집 거리(Levenshtein Distance).
20. 위상 정렬 (Topological Sort)
- 개념: 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 선행 작업의 순서를 거스르지 않도록 모든 정점을 일렬로 나열하는 알고리즘입니다.
- 시간 복잡도: 진입 차수(Indegree)와 큐를 사용하는 Kahn 알고리즘 기준 \(O(V + E)\)
- 실무 활용: 컴파일러의 소스코드 빌드 의존성 순서 결정, 선수과목 이수 체계도 생성, CI/CD 파이프라인의 태스크 실행 순서 정렬.
20대 핵심 알고리즘 총괄 비교 매트릭스
| 번호 | 알고리즘 명칭 | 핵심 분류 | 시간 복잡도 (평균) | 주요 특징 및 대표 실무 적용처 |
|---|---|---|---|---|
| 1 | 선형 탐색 | 탐색 | \(O(N)\) | 단순 배열 순차 비교, 정렬되지 않은 소규모 데이터 |
| 2 | 이진 탐색 | 탐색 | \(O(\log N)\) | 정렬 배열 절반 분할, 대규모 데이터 초고속 조회 |
| 3 | 파라메트릭 서치 | 최적화 | \(O(K \log R)\) | 최적화 \(\rightarrow\) 결정 문제 변환, 네트워크 대역폭 한계선 탐색 |
| 4 | 기초 정렬 3종 | 정렬 | \(O(N^2)\) | 버블/선택/삽입 정렬, 교육용 및 100건 이하 정렬 |
| 5 | 퀵 정렬 | 정렬 | \(O(N \log N)\) | 피벗 분할, 뛰어난 CPU 캐시 지역성으로 실무 선호 |
| 6 | 병합 정렬 | 정렬 | \(O(N \log N)\) | 안정 정렬(Stable), 추가 버퍼 필요, 외장 정렬 뼈대 |
| 7 | 힙 정렬 | 정렬 | \(O(N \log N)\) | 추가 메모리 없는 in-place \(O(N \log N)\) 보장 |
| 8 | 팀소트 | 정렬 | \(O(N \log N)\) | 삽입+병합 하이브리드, Python/Java 표준 정렬 엔진 |
| 9 | 투 포인터 | 선형 최적화 | \(O(N)\) | 정렬 배열 양단 좁히기, \(O(N^2)\) 구간합을 \(O(N)\)으로 단축 |
| 10 | 슬라이딩 윈도우 | 선형 최적화 | \(O(N)\) | 고정/가변 윈도우 우측 이동, 이동평균선 및 실시간 버퍼 |
| 11 | BFS (너비우선) | 그래프 | \(O(V+E)\) | 큐 사용, 가중치 없는 그래프의 ‘최단 경로’ 수학적 보장 |
| 12 | DFS (깊이우선) | 그래프 | \(O(V+E)\) | 스택/재귀 사용, 미로 탐색, 모든 경로 탐색, 사이클 판별 |
| 13 | 백트래킹 | 완전 탐색 | \(O(K^N)\) | 유망하지 않은 경로 조기 가지치기(Pruning), N-Queens |
| 14 | 다익스트라 | 최단 경로 | \(O((V+E)\log V)\) | 양수 가중치 최단 거리, 우선순위 큐, 내비게이션 라우팅 |
| 15 | 벨만-포드 | 최단 경로 | \(O(VE)\) | 음수 가중치 허용, 음수 사이클 감지, 외환 차익거래 |
| 16 | 플로이드-워셜 | 최단 경로 | \(O(V^3)\) | 모든 정점 쌍 간의 최단거리 2차원 표 한 번에 완성 |
| 17 | A* 알고리즘 | 최단 경로 | 휴리스틱 의존 | \(g(n)+h(n)\) 추정치 결합, 게임 유닛/로봇 길찾기 제왕 |
| 18 | 그리디 알고리즘 | 탐욕법 | 보통 \(O(N \log N)\) | 매 순간의 국소 최적 선택, 거스름돈, 회의실 스케줄링 |
| 19 | 동적 계획법 (DP) | 최적화 | 문제별 \(O(N)\)~\(O(N^2)\) | 중복 하위 문제 메모이제이션, 배낭 문제, 편집 거리 |
| 20 | 위상 정렬 | 그래프 DAG | \(O(V+E)\) | 작업 의존성 순서화, 빌드 시스템 의존성 해석 (Make, Gradle) |
📚 참고 문헌 및 공식 출처
| 구분 | 자료명 | 주요 내용 | 링크 |
|---|---|---|---|
| 알고리즘 교과서 | Introduction to Algorithms (CLRS 4th Ed.) | Cormen et al., 전 세계 컴퓨터공학과 표준 알고리즘 교재 | MIT Press |
| 스탠퍼드 명강의 | Tim Roughgarden’s Algorithms Specialization | 분할정복, 그래프 탐색, 그리디, DP, NP-Complete 완벽 해설 | Coursera |
| 시각화 사이트 | VisuAlgo | 알고리즘 동작 과정을 인터랙티브 벡터 애니메이션으로 시각화 | visualgo.net |
| 실전 문제 해결 | 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (종만북) | 구종만 저, 백트래킹, DP, 최단 경로 문제의 직관적 모델링 | 인사이트 |