알고리즘 및 고급 자료구조
3단계: 불완전한 세계를 다루는 알고리즘
이론적 기초 — "왜 어떤 문제는 영원히 못 푸는가?"
1단계에서 배운 Big-O를 잠깐 상기해보자. O(n log n)은 빠르고, O(n²)은 조금 느리고, O(2ⁿ)은 입력이 30개만 넘어도 10억 번 이상 연산이 필요하다고 했다. 그렇다면 자연스럽게 이런 의문이 생겨야 한다: 세상의 모든 문제에 다항 시간 알고리즘이 존재할까? 직관적으로는 "충분히 영리한 알고리즘을 짜면 되지 않나?"라고 생각할 수 있다. 이 직관이 맞는지 틀린지를 따지는 것이 컴퓨터 과학 역사상 가장 위대한 미해결 문제, P vs NP 문제다.
P(Polynomial Time) 는 다항 시간 안에 풀 수 있는 문제들의 집합이다. 정렬, 최단경로, 최대공약수 계산 같은 것들이다. 반면 NP(Nondeterministic Polynomial Time) 는 조금 다른 개념인데, "정답 후보를 하나 줬을 때 그것이 정답인지 다항 시간 안에 검증할 수 있는" 문제들의 집합이다. 이 차이가 왜 중요한지 실제 예시로 이해해보자. 택배 기사가 서울 전역의 100개 배송지를 최소 거리로 돌아야 한다고 가정하자. 어떤 경로가 최적인지 찾는 것은 엄청나게 어렵다(100!가지 경우의 수). 그런데 누군가 "이 경로가 최적이야"라고 경로 하나를 줬을 때, 총 거리를 계산해서 맞는지 확인하는 건 O(n)으로 빠르게 된다. 이 문제가 NP 에 속한다. P는 NP의 부분집합임이 분명한데(풀 수 있으면 검증도 된다), "P = NP인가?"는 아직 모른다. 클레이 수학연구소에서 100만 달러 상금을 걸었고, 대부분의 컴퓨터 과학자들은 P ≠ NP라고 믿는다.
[노트 기록] P: 다항 시간에 풀 수 있는 문제 집합 / NP: 다항 시간에 검증 가능한 문제 집합 / NP-complete: NP 중 가장 어려운 문제들(모든 NP 문제가 다항 시간 환원 가능) / NP-hard: NP-complete보다 어렵거나 동등하게 어려운 문제들(검증조차 어려울 수 있음)
NP-complete 는 NP 안에서도 특별한 위치를 차지한다. "모든 NP 문제를 이 문제 하나로 다항 시간 안에 변환(환원, Reduction)할 수 있다"는 성질을 가진다. 즉 NP-complete 문제 하나만 다항 시간으로 풀 수 있으면 P = NP가 증명된다. 최초의 NP-complete 문제는 1971년 Stephen Cook이 증명한 SAT(Boolean Satisfiability Problem) 인데, 이후 Richard Karp가 그래프 채색, 집합 커버, 외판원 문제(TSP) 등 21개의 문제가 NP-complete임을 보였다. 오늘 배울 내용들은 바로 이 "사실상 최적해를 구할 수 없는 문제들"을 현실에서 어떻게 다룰 것인가에 대한 이야기다.
1. 근사 알고리즘 — "완벽하지 않아도, 얼마나 나쁜지는 보장한다"
NP-hard 문제에 부딪혔을 때 실무에서 선택지는 세 가지다: ① 문제를 더 작게 바꾼다(제약 완화), ② 특수 구조가 있는 경우에만 정확히 푼다, ③ 근사 알고리즘(Approximation Algorithm) 을 쓴다. 근사 알고리즘은 최적해를 보장하지는 않지만, "최적해의 α배 이내"임을 수학적으로 보장한다. 이 α를 근사 비율(Approximation Ratio) 이라고 한다. 예를 들어 "2-근사 알고리즘"은 내가 구한 해가 최적해의 최대 두 배라는 것을 보장한다. 최적이 100이면 내 답은 200 이하라는 뜻이다.
가장 직관적인 예시로 Vertex Cover(정점 커버) 문제를 보자. 그래프 G = (V, E)에서, 모든 간선이 적어도 한 끝점이 선택된 정점 집합에 포함되도록 하는 최소 정점 집합을 찾는 문제다. 경비원이 사무실 복도(간선)들을 다 감시하려면 최소 몇 명이 어디에 서야 하는가의 문제라고 생각하면 된다. 이 문제는 NP-complete이다. 그런데 놀랍도록 단순한 2-근사 알고리즘이 존재한다:
임의의 간선 (u, v)를 고른다
u와 v를 둘 다 커버에 넣는다
u, v에 연결된 모든 간선을 그래프에서 제거한다
남은 간선이 없을 때까지 반복한다
왜 이게 2-근사인지 스스로 생각해보자. 이 알고리즘이 선택한 간선들의 집합 M을 매칭(Matching)이라고 부른다. M의 각 간선은 서로 공유하는 정점이 없다(알고리즘이 연결된 간선을 다 제거하니까). 그러므로 최적해 OPT는 M의 각 간선마다 적어도 하나의 정점을 포함해야 한다. 즉 |OPT| ≥ |M| 이다. 우리 알고리즘은 M의 각 간선에서 정점 2개씩을 넣으니 |ALG| = 2|M| ≤ 2|OPT| 가 된다. 이게 2-근사 증명의 전부다. 이처럼 근사 알고리즘 분석은 "내 알고리즘의 출력"과 "최적해의 하한"을 연결하는 부등식 체인을 만드는 것이다.
[노트 기록] 근사비율 증명 패턴: ① 알고리즘 출력값 ALG(I)와 최적값 OPT(I)의 관계식을 구한다 ② OPT의 하한(또는 상한)을 구한다 ③ ALG(I) / OPT(I) ≤ α임을 보인다
더 어려운 예시로 집합 커버(Set Cover) 를 보자. 전체 집합 U와 부분집합들의 모임 S가 있을 때, S에서 최소 개수의 부분집합을 골라 U 전체를 커버하는 문제다. 2단계에서 배운 네트워크 플로우가 특정 구조의 자원 배분을 정확히 풀었던 것과 달리, 이 문제는 일반적인 경우에는 NP-hard다. 여기서 그리디 알고리즘을 적용하면 O(log n)-근사가 된다: 매 단계마다 아직 커버되지 않은 원소를 가장 많이 커버하는 집합을 선택한다. 이게 최적의 ln(n)배 이내임은 1979년 Lovász가 증명했다. 직관적으로, 최적이 k개의 집합을 쓴다면 처음 선택에서 최소 1/k 비율의 원소가 커버된다는 걸 귀납적으로 보이면 된다.
PTAS(Polynomial-Time Approximation Scheme) 라는 개념도 중요하다. 이것은 임의의 ε > 0에 대해 (1+ε)-근사를 보장하는 알고리즘 패밀리인데, 단 실행 시간이 ε에 의존한다. 예를 들어 배낭 문제(Knapsack)는 FPTAS(Fully Polynomial-Time Approximation Scheme)가 존재한다: 입력 값들을 적절히 스케일링해서 DP 테이블 크기를 줄이면 O(n²/ε)에 (1+ε)-근사가 가능하다. 반면 TSP는 삼각 부등식을 만족하는 특수 경우에 Christofides 알고리즘으로 3/2-근사가 가능하지만, 일반 TSP는 P ≠ NP 가정 하에 어떤 상수 α에 대한 α-근사도 불가능하다. 이 차이가 매우 중요한데, 어떤 NP-hard 문제는 좋은 근사가 가능하고, 어떤 문제는 근사 자체가 NP-hard라는 것이다.
2. 병렬/분산 알고리즘 — "혼자 못 하면 같이 한다"
근사 알고리즘이 "어려운 문제를 조금 타협해서 푸는" 방법이었다면, 이번에는 다른 차원의 어려움을 다룬다. 데이터가 수십 TB, 수백 PB라면? 아무리 빠른 알고리즘이라도 한 대 컴퓨터로는 한계가 있다. 2004년 구글이 발표한 MapReduce 논문(Jeffrey Dean, Sanjay Ghemawat)은 이 문제를 해결하는 패러다임을 제시했고, 이후 빅데이터 산업 전체의 기반이 됐다.
MapReduce의 핵심 아이디어는 놀랍도록 단순하다. 함수형 프로그래밍의 map과 reduce를 분산 환경으로 확장한 것이다. Map 단계에서는 각 워커 노드가 자기가 담당하는 데이터 조각에서 (key, value) 쌍들을 독립적으로 생성한다. Shuffle/Sort 단계에서는 같은 key를 가진 쌍들이 같은 Reducer로 모인다. Reduce 단계에서는 각 Reducer가 자기에게 모인 값들을 집계한다. 워드 카운트 예시가 가장 직관적이다: 10TB짜리 텍스트 파일에서 단어 빈도를 세야 한다면, 파일을 1000개 조각으로 나눠 각 Map 워커가 ("단어", 1) 쌍을 생성하고, 같은 단어들이 같은 Reducer로 모여서 합산된다.
[노트 기록] MapReduce 실행 흐름: 입력 데이터 분할 → Map(각 청크에서 독립 실행) → Shuffle(key 기준 정렬 및 분배) → Reduce(동일 key의 values 집계) → 출력
여기서 알고리즘 설계 관점에서 핵심적인 제약이 있다. Map 단계는 반드시 독립적이어야 한다. 두 Map 태스크가 서로의 결과를 참조하면 안 된다. 이 제약이 분산 알고리즘 설계를 어렵게 만드는 주범이다. 예를 들어 PageRank를 MapReduce로 구현하려면 반복(iteration) 구조가 필요한데, 매 반복마다 전체 MapReduce 잡을 돌려야 한다. 디스크 I/O 오버헤드가 어마어마하다. 이 문제를 해결하기 위해 등장한 게 Apache Spark다.
Spark의 핵심 추상화는 RDD(Resilient Distributed Dataset) 다. RDD는 여러 노드에 걸쳐 분산된 불변(immutable) 데이터셋이다. Spark의 혁신은 두 가지다: ① 중간 결과를 디스크가 아닌 메모리(RAM)에 캐시한다, ② 지연 평가(Lazy Evaluation) 를 통해 실제 실행 전에 최적의 실행 계획을 수립한다. Spark는 연산들을 DAG(Directed Acyclic Graph)로 표현하고, 실제 결과가 필요할 때(action 호출 시) 최적화된 실행 계획을 만들어 실행한다. 이 덕분에 MapReduce보다 반복 연산이 10-100배 빠르다.
분산 알고리즘 설계에서 또 다른 근본적인 제약은 CAP 정리(Brewer, 2000) 다: 분산 시스템은 Consistency(일관성), Availability(가용성), Partition Tolerance(네트워크 분단 허용) 세 가지를 동시에 만족할 수 없다. 네트워크 분단은 현실에서 피할 수 없으므로, 실제로는 CP(일관성 우선, ex. HBase) vs AP(가용성 우선, ex. Cassandra) 중 선택의 문제가 된다. 근사 알고리즘에서 "최적 대신 근사"를 택했듯, 분산 시스템에서는 "완벽한 일관성 대신 최종적 일관성(Eventual Consistency)"을 택하는 경우가 많다.
3. 온라인 알고리즘 — "미래를 모르는 채로 결정한다"
지금까지 다룬 알고리즘들은 모두 오프라인(Offline) 알고리즘이었다. 입력 전체를 미리 알고 있다고 가정한다. 하지만 현실의 많은 문제는 다르다. 주식 매매, 실시간 광고 입찰, 서버 캐시 교체, 온라인 스케줄링 — 이 모든 것은 미래 정보를 모르는 채로 매 순간 돌이킬 수 없는 결정을 내려야 한다. 이런 알고리즘을 온라인 알고리즘(Online Algorithm) 이라고 한다.
온라인 알고리즘의 성능을 평가하는 기준이 경쟁비(Competitive Ratio) 다. 최악의 입력 시퀀스에서 온라인 알고리즘의 비용과 전지전능한 오프라인 최적해의 비용 비율의 상한이다. 수식으로 쓰면 c-경쟁적 알고리즘이란: 모든 입력 시퀀스 σ에 대해 ALG(σ) ≤ c · OPT(σ) + b (b는 상수)를 만족한다는 뜻이다. c = 1이면 완벽하지만 대부분의 온라인 문제에서 불가능하다.
[노트 기록] 경쟁비(Competitive Ratio) c = max over all inputs σ of [ALG(σ) / OPT(σ)] — "최악의 경우에 최적 대비 얼마나 나쁜가"의 상한
스키 대여 문제(Ski Rental Problem) 가 온라인 알고리즘의 진수를 보여준다. 스키 리조트에 왔는데, 렌탈 비용은 하루 1달러, 구매 비용은 B달러다. 앞으로 며칠이나 스키를 탈지 모른다. 언제 사야 할까? 항상 빌리면: 운 좋게 하루만 타면 최적(1달러), 하지만 B일 이상 타면 최적의 B배를 쓴다. 항상 사면: 하루만 타면 B배를 낭비한다. 최적 전략은 B-1일 동안 빌리다가 B일째 되는 날 사는 것이다. 이 전략의 경쟁비를 스스로 계산해보자: 최대 몇 일을 탔을 때 최적 대비 비율이 가장 나빠지는가? 정답은 경쟁비 2 - 1/B (≈ 2)다. 이것이 결정론적 알고리즘의 최선임이 증명돼 있다.
페이징 문제(Paging Problem) 는 OS의 메모리 관리와 직결된다. CPU 캐시에 k개 페이지만 저장 가능한데, 요청 시퀀스가 들어온다. 캐시에 없으면 디스크에서 불러와야 한다(page fault). LRU(Least Recently Used)는 k-경쟁적임이 증명돼 있다: 최악의 경우 최적해보다 k배 더 많은 page fault가 발생한다. 놀랍게도 이것이 결정론적 알고리즘의 이론적 하한이기도 하다. 반면 랜덤화 알고리즘은 H_k(조화급수) ≈ ln(k)-경쟁적까지 가능하다. 즉 무작위성을 활용하면 경쟁비가 크게 개선될 수 있다.
온라인 알고리즘은 실무에서 실시간 입찰(RTB, Real-Time Bidding) 시스템의 핵심이다. 광고주는 웹페이지 로딩 100ms 안에 특정 사용자에게 광고를 보여줄 것인지 입찰 여부를 결정해야 한다. 예산은 한정돼 있고, 앞으로 어떤 사용자가 올지 모른다. 2단계에서 배운 이분 매칭을 떠올리면, 이건 "온라인 이분 매칭" 문제다: 광고주(왼쪽)와 사용자(오른쪽)를 연결하는데 사용자가 온라인으로 하나씩 도착한다. RANKING 알고리즘은 이 문제에서 (1 - 1/e) ≈ 0.632-경쟁적임이 증명돼 있고, 이것이 이 문제의 이론적 상한이다. Google이 이 알고리즘을 실제 광고 시스템에 쓰고 있다.
심화: 세 분야의 교차점
이제 세 개념이 어떻게 연결되는지 보자. 대규모 추천 시스템을 설계한다고 하면: 협업 필터링의 핵심인 행렬 분해(Matrix Factorization)는 NP-hard가 아니지만, 최적의 추천 다양성 보장(Diversity-Aware Recommendation)은 NP-hard에 가깝다 → 근사 알고리즘 필요. 수억 명의 사용자 데이터를 처리하려면 → 분산 알고리즘 필요. 사용자의 실시간 클릭을 보면서 모델을 업데이트하려면 → 온라인 알고리즘 필요. 실무의 시스템들은 항상 이 세 가지를 동시에 고려한다.
프로젝트 — 스스로 풀어보기 (약 40분)
지금부터는 설명 없다. 네가 직접 생각해야 한다. 각 문제는 코드를 작성하거나, 수식을 유도하거나, 설계 문서를 작성하는 형태다. 정답은 없다. 얼마나 논리적으로 접근했는지가 핵심이다.
문제 1. 그리디 집합 커버 구현 및 근사비 실험 (약 12분)
다음 상황을 구현하라. 전국 100개 도시에 기지국을 설치해야 한다. 각 기지국 후보 위치는 특정 도시들을 커버할 수 있다. 최소 기지국 수로 모든 도시를 커버하고 싶다.
(a) 랜덤하게 50개의 후보 기지국을 생성하라. 각 기지국은 5~15개의 도시를 무작위로 커버한다. 그리디 집합 커버 알고리즘을 구현하고, 몇 개의 기지국이 선택됐는지 출력하라.
import random
def generate_instance(n_cities=100, n_stations=50):
# 각 기지국이 커버하는 도시 집합을 반환하라
# 힌트: random.sample 사용
pass
def greedy_set_cover(universe, sets):
# 그리디 집합 커버 알고리즘을 구현하라
# universe: 전체 도시 집합
# sets: 기지국별 커버 도시 목록 (리스트의 리스트)
# 반환: 선택된 기지국 인덱스 목록
pass
(b) 같은 인스턴스에서 무작위로 기지국을 선택하는 알고리즘(랜덤 알고리즘)과 그리디 알고리즘을 100번 반복 실험해서 평균 기지국 수를 비교하라. 그리디가 얼마나 좋은가?
(c) 이론적으로 그리디의 근사비는 H_n(조화급수) ≈ ln(n)이다. 네 실험 결과에서 최적해를 구할 수 없으므로, 대신 랜덤 대비 그리디의 비율을 구하라. 이게 근사비 분석의 현실적 의미와 어떻게 연결되는가?
문제 2. 미니 MapReduce 엔진 설계 (약 15분)
Python으로 단순화된 MapReduce 프레임워크를 구현하라. 실제 분산 환경은 아니지만, 로직은 동일하다.
from collections import defaultdict
from multiprocessing import Pool
import json
def mapreduce(data_chunks, map_fn, reduce_fn):
"""
data_chunks: 데이터를 여러 청크로 나눈 리스트
map_fn: 각 (chunk_item) -> [(key, value), ...] 형태의 함수
reduce_fn: (key, [values]) -> result 형태의 함수
반환: {key: result} 딕셔너리
"""
# 1. Map Phase: 각 청크에 map_fn 적용 (멀티프로세싱 사용)
# 2. Shuffle Phase: key 기준으로 그룹화
# 3. Reduce Phase: 각 key-group에 reduce_fn 적용
pass
# 테스트 케이스 1: 단어 빈도 카운트
text_data = [
"the quick brown fox jumps over the lazy dog",
"the dog barked at the fox",
"quick brown foxes are rare",
# ... 더 많은 데이터
]
def word_count_map(line):
# 구현하라
pass
def word_count_reduce(key, values):
# 구현하라
pass
# 테스트 케이스 2: 역 인덱스 (검색 엔진의 핵심)
documents = {
"doc1": "python is great for data science",
"doc2": "java is great for enterprise",
"doc3": "python java both have great libraries",
}
def inverted_index_map(doc_id_and_text):
# (단어, doc_id) 쌍을 출력하라
pass
def inverted_index_reduce(word, doc_ids):
# 해당 단어가 등장하는 문서 집합을 반환하라
pass
(a) 위 프레임워크를 완성하고 두 테스트 케이스를 통과시켜라.
(b) data_chunks의 개수(즉 병렬도)를 1, 2, 4, 8로 바꿔가며 처리 시간을 측정하라. 이론적으로 병렬도를 두 배로 늘리면 시간이 반으로 줄어야 한다. 실제로 그렇게 되는가? 왜 안 된다면 무엇이 병목인가?
(c) 이 프레임워크에서 워커 하나가 중간에 죽으면 어떻게 되는가? MapReduce의 실제 구현(Hadoop)은 이 문제를 어떻게 해결하는지 설계 아이디어를 서술하라(코드 불필요, 아이디어만).
문제 3. 온라인 스케줄링과 경쟁비 계산 (약 13분)
온라인 작업 스케줄링 문제다. m개의 동일한 서버가 있고, 작업들이 하나씩 도착한다. 각 작업은 처리 시간 p_i를 가지며, 도착 즉시 어느 서버에 배정할지 결정해야 한다(나중에 변경 불가). 목표는 모든 작업이 끝나는 시간(makespan)을 최소화하는 것이다.
(a) "List Scheduling" 알고리즘을 구현하라: 새 작업이 올 때마다 현재 가장 부하가 적은 서버에 배정한다.
import heapq
def list_scheduling(job_times, m_servers):
"""
job_times: 작업 처리 시간 리스트 (순서대로 도착)
m_servers: 서버 수
반환: makespan (전체 완료 시간)
"""
pass
# 실험: m=3 서버, 다양한 작업 시퀀스
jobs_case1 = [3, 3, 3, 3, 3, 3] # 균일한 작업
jobs_case2 = [10, 1, 1, 1, 1, 1] # 큰 작업이 먼저
jobs_case3 = [1, 1, 1, 1, 1, 10] # 큰 작업이 마지막
(b) 각 케이스에서 최적해(오프라인, 즉 작업 순서를 미리 알고 최적 배정)를 손으로 계산하라. List Scheduling의 경쟁비(ALG/OPT)를 각 케이스에서 구하라.
(c) List Scheduling의 이론적 경쟁비는 (4/3 - 1/(3m)) 임이 증명돼 있다. m=3일 때 이론값은 얼마인가? 네 실험 결과와 비교하라.
(d) "큰 작업을 먼저 배정(LPT, Longest Processing Time First)"은 오프라인 알고리즘이다. 왜 온라인 환경에서는 LPT를 직접 쓸 수 없는가? 그럼에도 온라인 환경에서 LPT의 정신을 어떻게 근사할 수 있을지 아이디어를 서술하라.
종합 설계 문제 (선택, +α): RTB 시스템 스케치
광고 플랫폼을 설계한다고 가정하자. 사용자가 웹페이지를 로딩할 때마다 100ms 안에 어떤 광고를 보여줄지 결정해야 한다. 광고주 A, B, C가 있고 각각 일일 예산이 있다. 각 사용자가 어떤 광고주에게 얼마나 가치 있는지는 머신러닝 모델이 예측한다.
이 시스템을 설계할 때 ① 근사 알고리즘, ② 분산 처리, ③ 온라인 알고리즘 세 개념이 각각 어떤 역할을 하는지 1페이지 설계 문서로 작성하라. 코드는 불필요하고, 각 개념이 왜 필요한지 논리적 이유와 함께 서술하라.
평가 기준
| 항목 | 배점 |
|---|---|
| 근사비 분석 (문제 1c, 3b, 3c) | 40점 |
| 분산 처리 구현 성능 (문제 2a, 2b) | 40점 |
| 설계 논리 서술 (문제 2c, 3d, 종합) | 20점 |
알고리즘을 외우지 말고, "왜 이게 동작하는가"를 수식 하나라도 써가며 설명할 수 있어야 진짜 이해한 것이다. 문제를 풀면서 막히는 부분이 있으면 그 막히는 지점 자체가 가장 중요한 학습 포인트다. 그냥 넘어가지 말고 왜 막히는지 먼저 언어로 서술해보자.