개발자가 반드시 알아야 할 핵심 알고리즘 20선: 시간 복잡도부터 그래프·DP·탐색까지 실무 관점 총정리

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 시간과 메모리)을 아끼기 위해 문제를 어떻게 쪼개고 다룰 것인가”에 있습니다.

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;

1. 탐색의 기술: 선형 탐색 vs 이진 탐색(Binary Search)

40억 명의 사용자가 저장된 데이터베이스에서 특정 사용자 한 명을 찾아야 합니다: * 선형 탐색 (Linear Search, \(O(N)\)): 1번부터 40억 번까지 하나씩 비교합니다. 최악의 경우 40억 번을 비교해야 합니다. * 이진 탐색 (Binary Search, \(O(\log N)\)): 데이터가 정렬되어 있다면, 항상 정중앙을 확인하고 범위를 절반씩 버립니다. 40억 개의 데이터도 단 32번의 비교만으로 찾아냅니다! (\(2^{32} \approx 42억\))

sequenceDiagram
    autonumber
    actor Dev as 개발자
    participant Search as 이진 탐색 (1~100 사이 73 찾기)

    Dev->>Search: 1. 중앙값 50 확인
    Search-->>Dev: "73은 50보다 큽니다. 왼쪽(1~50)은 전부 버립니다!"
    Dev->>Search: 2. 남은 절반(51~100)의 중앙값 75 확인
    Search-->>Dev: "73은 75보다 작습니다. 오른쪽(75~100)은 전부 버립니다!"
    Dev->>Search: 3. 남은 절반(51~74)의 중앙값 62 확인
    Search-->>Dev: "73은 62보다 큽니다!"
    Dev->>Search: 4. 몇 번 더 좁히면 단 몇 번 만에 73 적중!

🎯 실무 팁: 파라메트릭 서치 (Parametric Search)

이진 탐색은 단순 값 찾기를 넘어 “최적화 문제를 결정 문제(Yes/No)로 바꾸어 푸는 파라메트릭 서치”로 실무에서 널리 쓰입니다. 예: “동영상 품질을 얼마로 맞춰야 버퍼링 없이 재생 가능한가?” \(\rightarrow\) 품질 비트레이트 범위를 이진 탐색으로 좁혀가며 최적값을 초고속으로 찾아냅니다.

2. 정렬 알고리즘의 진화: 거품 정렬에서 팀소트(Timsort)까지

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정성(Stable)	실무 특징 및 용도
버블/선택/삽입	\(O(N^2)\)	\(O(N^2)\)	\(O(1)\)	버블/삽입: O	교육용. 데이터 100건 이하의 매우 작은 배열에만 사용
퀵 정렬 (Quick Sort)	\(O(N \log N)\)	\(O(N^2)\)	\(O(\log N)\)	X	캐시 지역성이 매우 뛰어나 평균적으로 가장 빠름
병합 정렬 (Merge Sort)	\(O(N \log N)\)	\(O(N \log N)\)	\(O(N)\)	O	안정적이나 추가 메모리 버퍼가 필요함
힙 정렬 (Heap Sort)	\(O(N \log N)\)	\(O(N \log N)\)	\(O(1)\)	X	추가 메모리 없이 최악에도 \(O(N \log N)\) 보장
팀소트 (Timsort)	\(O(N \log N)\)	\(O(N \log N)\)	\(O(N)\)	O	현대 언어의 표준 (Python, Java Arrays.sort). 삽입+병합 하이브리드

Timsort가 최강자인 이유: 현실 세계의 데이터는 완전 무작위(Random)가 아니라 이미 일부분이 정렬되어 있는 덩어리(Run)가 많습니다. 팀소트는 이를 감지하여 정렬된 구간은 건너뛰고 작은 구간은 삽입 정렬로 초고속 처리합니다.

3. 그래프 탐색의 양대 산맥: BFS vs DFS

네트워크, 지도 길찾기, SNS 친구 추천, 웹 크롤러 등 관계를 다루는 모든 문제는 그래프(Graph)로 모델링됩니다.

flowchart TD
    subgraph GraphSearch["그래프 탐색 2대 접근법"]
        BFS["BFS (너비 우선 탐색)<br>- 큐(Queue) 자료구조 사용<br>- 시작점부터 1촌, 2촌, 3촌 순서로 넓게 퍼져나감<br>- 가중치 없는 그래프의 '최단 거리' 보장!"]
        DFS["DFS (깊이 우선 탐색)<br>- 스택(Stack) 또는 재귀함수 사용<br>- 한 우물만 바닥까지 끝까지 파고든 뒤 되돌아옴<br>- 미로 탐색, 사이클 감지, 모든 경로 순회에 최적!"]
    end
    style BFS fill:#DCFCE7,stroke:#16A34A,stroke-width:2px;
    style DFS fill:#FEF3C7,stroke:#D97706,stroke-width:2px;

SNS 친구 추천: 나와 가장 가까운 사람부터 탐색해야 하므로 BFS가 정답입니다.
체스/바둑 AI의 수읽기: 한 가지 수를 끝까지 두어보고 승패를 판단한 뒤 다른 수를 검토해야 하므로 DFS + 백트래킹이 정답입니다.

4. 최단 경로(Shortest Path) 3총사

다익스트라 (Dijkstra, \(O((V+E) \log V)\)):
- 도로망처럼 간선의 가중치(거리/시간)가 모두 양수일 때 최단 경로를 찾는 표준 알고리즘.
- 우선순위 큐(Min Heap)를 사용하여 현재 가장 가까운 노드를 그리디(Greedy)하게 확정해 나갑니다.
벨만-포드 (Bellman-Ford, \(O(VE)\)):
- 금융 환율 차익 거래처럼 음수 가중치(Negative Weight)나 음수 사이클이 존재할 때 사용합니다. 다익스트라보다 느리지만 안전합니다.
A* (A-Star) 알고리즘:
- 내비게이션 및 게임 유닛 길찾기의 제왕.
- 다익스트라에 “목적지까지의 직선 거리 예상치(휴리스틱 Heuristic)”를 더하여, 목적지와 반대 방향인 엉뚱한 길은 아예 탐색하지 않고 목표 지점을 향해 쐐기처럼 파고듭니다.

5. 동적 계획법(DP): 똑똑하게 기억하며 풀기 (Memoization)

복잡한 문제를 작은 부분 문제로 나누어 푸는 방법에는 두 가지가 있습니다: * 분할 정복 (Divide & Conquer): 퀵 정렬, 병합 정렬처럼 부분 문제들이 서로 독립적일 때 각각 풉니다. * 동적 계획법 (Dynamic Programming): 피보나치 수열처럼 동일한 부분 문제가 수없이 중복 반복될 때, 이미 계산한 결과를 메모리(배열/해시맵)에 적어두고 재사용(Memoization)합니다.

피보나치 f(5)를 단순 재귀로 풀면:
f(5) = f(4) + f(3)
     = [f(3) + f(2)] + [f(2) + f(1)]
     ... 동일한 f(3), f(2)를 수십 번 중복 계산 (O(2^N) 지수 폭발!)

DP(메모이제이션)를 적용하면:
f(2)=1 계산 후 배열에 저장! -> 다음에 f(2)가 필요하면 0.001초 만에 꺼내 씀!
연산 복잡도가 O(2^N)에서 단 O(N)으로 기적처럼 압축됨!

6. 개발자를 위한 알고리즘 학습 로드맵

1단계 (기본기): 배열, 해시맵 기반의 Big-O 시간/공간 복잡도 감각 익히기
2단계 (탐색/정렬): 이진 탐색 및 투 포인터(Two Pointers), 슬라이딩 윈도우 패턴 정복
3단계 (그래프): 인접 리스트 기반 BFS/DFS 구현 및 최단 경로(다익스트라)
4단계 (최적화): 메모이제이션 기반 DP(동적 계획법)와 가지치기(Backtracking)

📚 참고 문헌 및 공식 출처

구분	자료명	주요 내용	링크
알고리즘 교과서	Introduction to Algorithms (CLRS 4th Ed.)	Cormen, Leiserson, Rivest, Stein 저, 전 세계 대학 컴퓨터공학과 표준 교재	MIT Press
명강의	Tim Roughgarden’s Algorithms Specialization	스탠퍼드 대학교 알고리즘 명강의, 분할정복·그래프·NP-Complete	Coursera
시각화 사이트	VisuAlgo	정렬, 트리, 그래프 알고리즘 동작 과정을 인터랙티브 애니메이션으로 시각화	visualgo.net
실전 문제 해결	프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (종만북)	구종만 저, 백트래킹, DP, 최단 경로 문제의 직관적 모델링	인사이트