알고리즘 패러다임, 문제를 보는 첫 기준
DP, Greedy, Divide and Conquer, Backtracking의 선택 기준과 실패 모드를 중심으로 알고리즘 패러다임을 정리한다. 검색 엔진의 유사도 메트릭, 역색인, BM25까지 연결해 실무에서 어떤 관점으로 문제를 분류해야 하는지 다룬다.
Script Companion
오디오와 함께 스크립트 보기
- 01
알고리즘 패러다임은 문제를 처음 봤을 때 어떤 방향으로 풀지 정하는 기준입니다. 패러다임을 모르면 어떻게 풀어야 하지라는 질문에서 멈추지만, 패러다임을 알면 문제 유형을 보고 접근법을 먼저 떠올릴 수 있습니다. 이 문서의 관점은 단순히 코딩 테스트 기법을 외우는 것이 아니라, 비용 최적화, 스케줄링, 정렬과 검색, 검색 엔진 스코어링 같은 실무 문제를 같은 틀로 바라보는 데 있습니다. React의 useMemo와 React.memo는 같은 입력에 대해 이전 계산 결과를 재사용하는 Memoization 패턴이고, Webpack의 code splitting은 전체 번들을 작은 청크로 나누는 Divide and Conquer 패턴으로 볼 수 있습니다.
- 02
Dynamic Programming, 동적 프로그래밍의 핵심은 이미 계산한 것은 다시 계산하지 않는다는 생각입니다. 적용 조건은 두 가지입니다. 같은 하위 문제가 반복해서 등장하는 중복 부분 문제, 그리고 전체 문제의 최적해가 하위 문제의 최적해로 구성되는 최적 부분 구조가 있어야 합니다. 피보나치 수열이 대표적입니다. 순수 재귀로 fib(5)를 계산하면 fib(3) 같은 하위 문제가 여러 번 등장하고, 노드 수는 O(2^n)으로 커집니다. 하지만 실제 고유한 하위 문제는 fib(0)부터 fib(5)까지 단 6개뿐입니다. DP는 이 고유 문제만 한 번씩 계산해 O(n)으로 줄입니다.
- 03
DP에는 Top-Down Memoization과 Bottom-Up Tabulation이 있습니다. Top-Down은 재귀로 내려가며 계산 결과를 캐시에 저장하므로 문제 정의가 재귀적일 때 직관적이고, 필요한 하위 문제만 푸는 lazy evaluation의 장점이 있습니다. 대신 재귀 깊이 한계 때문에 JavaScript에서 n이 10000을 넘으면 스택 안전성이 위험해질 수 있습니다. Bottom-Up은 작은 문제부터 배열을 채우는 방식이라 함수 호출 오버헤드가 없고, 스택 오버플로우가 없으며, 배열 크기를 미리 잡아 메모리를 예측하기 쉽습니다. JavaScript와 TypeScript 환경에서는 n이 커질 수 있다면 Bottom-Up을 기본으로 두고, 구조가 재귀적이고 입력이 작을 때 Top-Down을 선택하는 기준이 문서의 권장입니다.
- 04
DP가 실무와 만나는 지점은 최적 조합을 찾아야 하는 문제입니다. 월 예산 안에서 최대 처리량을 내는 EC2와 Lambda 조합을 찾는 문제는 0/1 Knapsack으로 볼 수 있고, Greedy처럼 가성비 순으로 고르면 최적해를 보장하지 못합니다. CI/CD에서 어떤 모듈의 빌드 캐시를 유지할지 결정하거나, 변경된 파일의 해시가 같으면 재빌드를 건너뛰는 전략도 이전 결과를 재사용한다는 점에서 DP 패턴입니다. 외부 API 호출 실패 시 재시도 횟수와 backoff를 고를 때도 각 시도의 성공 확률과 비용을 고려해 최적 전략을 구성한다는 관점이 들어갑니다. LCS, 최장 공통 부분 수열은 Git diff와 표절 감지에 연결됩니다.
- 05
Greedy 알고리즘은 매 단계에서 지금 가장 좋아 보이는 선택을 하고 되돌아가지 않는 방식입니다. 빠른 이유도 바로 여기에 있습니다. DP가 하위 문제를 저장하고 비교하는 동안 Greedy는 현재 기준의 최선만 선택하고 전진하므로, 보통 정렬 O(n log n)에 선택 O(n)을 더한 정도로 끝납니다. 하지만 지역 최적의 연속이 전체 최적이 되는지는 문제마다 다릅니다. Greedy가 정답을 보장하려면 탐욕 선택 성질, 즉 지금의 최선이 전체 최적해의 일부가 되는 성질이 필요하고, 최적 부분 구조도 필요합니다. 표준 동전 체계의 거스름돈이나 Activity Selection처럼 조건이 맞는 문제에서는 강력하지만, 조건이 없으면 빠르게 틀린 답을 냅니다.
- 06
Greedy의 실패는 조용하게 나타나는 경우가 위험합니다. 동전이 1, 3, 4이고 잔돈이 6이면 Greedy는 4 더하기 1 더하기 1로 3개를 고르지만, 최적은 3 더하기 3으로 2개입니다. 0/1 Knapsack에서는 더 큰 차이가 납니다. 용량 50lb 가방에 10lb 60달러, 20lb 100달러, 30lb 120달러 아이템이 있을 때 density 기준 Greedy는 앞의 두 개를 골라 160달러에 멈추지만, DP 최적해는 20lb와 30lb를 골라 220달러가 됩니다. 분수형 Knapsack은 아이템을 쪼갤 수 있어서 density 정렬 Greedy가 통하지만, 0/1 Knapsack은 아이템이 atomic이라 NP-hard입니다. 입력 스키마에서 divisible인지 atomic인지 보는 것이 선택 기준입니다.
- 07
실무에서 Greedy는 완벽한 최적해보다 충분히 좋은 빠른 결정이 필요한 곳에 쓰입니다. Kubernetes 기본 스케줄러는 가장 여유 있는 노드에 우선 배치하는 Greedy 전략을 사용하고, AWS ALB의 Least Outstanding Requests 알고리즘은 현재 처리 중인 요청이 가장 적은 인스턴스에 새 요청을 보냅니다. 데이터 마이그레이션 작업이 같은 DB 테이블 Lock 때문에 겹칠 수 없다면 종료 시간 기준 Greedy로 최대한 많은 작업을 배치할 수 있습니다. 판단법은 단순합니다. Greedy로 풀 수 있을 것 같으면 반례를 직접 만들어 보고, 하나라도 나오면 DP로 전환합니다. 반대로 최적해가 필수가 아니고 근사해가 실용적이면 Greedy가 더 나은 선택이 될 수 있습니다.
- 08
Divide and Conquer는 큰 문제를 같은 형태의 작은 문제로 나누고, 각각 풀고, 결과를 합치는 패러다임입니다. 핵심 단계는 Divide, Conquer, Combine입니다. DP와의 가장 중요한 차이는 하위 문제가 서로 겹치지 않고 독립적이라는 점입니다. 겹치면 DP가 중복 계산을 제거하는 데 유리하고, 겹치지 않으면 D&C가 병렬성에서 강합니다. Merge Sort에서 왼쪽 절반과 오른쪽 절반은 서로 영향을 주지 않으므로 멀티코어 CPU나 분산 시스템에서 동시에 처리할 수 있습니다. MapReduce, AWS Lambda의 팬아웃 패턴, 데이터베이스 파티셔닝도 쪼개고, 각 Worker가 독립 처리하고, 결과를 합치는 구조를 따릅니다.
- 09
D&C의 시간 복잡도는 Master Theorem으로 읽을 수 있습니다. 점화식 T(n) = aT(n/b) + f(n)에서 a는 하위 문제 개수, b는 크기 축소 비율, f(n)은 분할과 합산 비용입니다. 판단 절차는 log_b a를 계산하고, n^(log_b a)와 f(n)을 비교한 뒤 어느 case인지 맞추는 것입니다. CLRS가 정리한 case에서 하위 호출 수가 지배하면 leaves-dominated, 두 비용이 동급이면 balanced, 분할과 합산 비용이 지배하면 root-dominated입니다. Merge Sort는 T(n) = 2T(n/2) + n이라 balanced가 되고 O(n log n)이 됩니다. 어느 case에도 맞지 않으면 Master Theorem을 적용하지 않고 Akra–Bazzi 일반화 정리나 직접 트리 합으로 폴백해야 합니다.
- 10
Backtracking은 가능한 선택지를 탐색하되 조건을 위반하면 즉시 되돌아가는 전략입니다. Brute Force보다 효율적인 이유는 가망 없는 경로, dead end를 조기에 포기하는 Pruning 때문입니다. 동작 방식은 선택을 추가하고, 재귀 탐색을 진행한 뒤, 탐색이 끝나면 그 선택을 철회하는 흐름입니다. 이 철회가 빠지면 이전 상태가 다음 탐색을 오염시켜 올바른 결과를 만들 수 없습니다. N-Queens에서는 조건 위반을 조기에 감지해 많은 경로를 건너뜁니다. 문서의 예시처럼 4-Queens에서 Brute Force는 4^4인 256가지를 모두 보지만, 백트래킹은 약 8~10회 호출로 해결합니다. API 권한 조합 탐색이나 Terraform 의존성 그래프 검증도 이 관점으로 볼 수 있습니다.
- 11
패러다임 선택은 문제의 신호를 읽는 일입니다. 모든 조합을 고려해야 하고 중복 하위 문제가 보이면 DP를 의심합니다. 지금 선택이 나중에 후회되지 않는다는 탐욕 선택 성질을 증명할 수 있으면 Greedy를 검토합니다. 하위 문제가 서로 독립이고 나눠서 병렬 처리할 수 있으면 Divide and Conquer가 자연스럽습니다. 선택, 탐색, 철회가 반복되고 조건 위반 경로를 버릴 수 있으면 Backtracking입니다. 현대 알고리즘은 섞이기도 합니다. A* 탐색은 Greedy의 휴리스틱과 DP의 정확한 거리 추적을 조합하고, 맨해튼 거리 휴리스틱을 사용할 때 Dijkstra보다 평균 2~3배 적은 노드를 탐색하면서 최적해를 보장한다고 문서는 설명합니다.
- 12
인터뷰와 코딩 테스트에서는 코드를 아는 것보다 언제 쓰는지 설명하는 과정이 중요합니다. DP에서는 1D DP처럼 지금 결정이 이전 결정에 의존하는 패턴, 2D DP처럼 두 시퀀스를 비교하는 패턴, Knapsack처럼 포함과 제외를 고르는 패턴을 먼저 떠올립니다. 0/1 Knapsack에서 1D 배열로 공간을 줄일 때는 내부 루프를 용량 역순으로 돌아야 합니다. 정순으로 돌면 dp[w - weights[i]]가 이미 현재 아이템을 포함한 값이 되어 같은 아이템을 중복 사용하게 됩니다. 공간 최적화도 경계가 있습니다. Fibonacci류는 이전 두 값만 유지해 O(1)로 줄일 수 있고, LCS나 Edit Distance는 이전 행만 유지해 O(min(m,n))으로 줄일 수 있습니다.
- 13
유사도 메트릭과 검색 알고리즘은 알고리즘 패러다임이 실무 데이터로 이어지는 영역입니다. Jaccard Similarity는 집합의 교집합과 합집합 비율로 두 집합이 얼마나 겹치는지 봅니다. Cosine Similarity는 벡터의 크기보다 방향이 얼마나 같은지를 보고, 문서 검색이나 추천, NLP 임베딩 벡터 비교에 쓰입니다. Edit Distance, Levenshtein Distance는 삽입, 삭제, 교체를 통해 두 문자열을 같게 만드는 최소 연산 수이고, 맞춤법 교정, 퍼지 검색, 자동완성, 유사 레코드 감지에 연결됩니다. 검색 엔진 쪽에서는 역색인이 단어에서 문서 ID 목록으로 가는 매핑을 만들어 전체 스캔 대신 빠른 조회와 Posting List 교집합을 가능하게 합니다.
- 14
TF-IDF는 문서 내 단어 빈도인 TF와 전체 문서에서의 희소성인 IDF를 곱해 중요도를 점수화합니다. 흔한 단어는 낮은 IDF로 억제됩니다. BM25는 TF-IDF를 개선해 단어 반복 증가에 체감 감소를 적용하고, 문서 길이 정규화를 더합니다. Elasticsearch 기본 랭킹에서 BM25의 기본값은 k1=1.2, b=0.75이며, GET /index/_explain/doc-id로 점수 분해를 확인할 수 있습니다. 경계도 분명합니다. Inverted Index는 키워드 정확도에 강하지만 의미 기반 검색에는 약합니다. 강아지와 개처럼 다른 토큰으로 들어가면 매칭이 빠질 수 있어서, Dense Index와 Sparse Index를 함께 쓰는 하이브리드 검색으로 보완합니다.
- 15
마지막으로 실패 모드를 기억해야 합니다. 재귀 DP가 큰 입력에서 Maximum call stack size exceeded나 TLE로 실패하면 JavaScript 재귀 깊이 한계, memo 체크 전 무거운 연산, 객체나 배열 memo 키 문제를 의심해야 합니다. Greedy가 대부분의 테스트를 통과하고 일부 엣지 케이스에서만 틀리면 탐욕 선택 성질이 없거나 정렬 기준이 틀렸을 수 있고, skewed 입력을 테스트해야 합니다. Elasticsearch 검색 순서가 예상과 다르면 BM25의 b 파라미터, 샤드별 IDF 왜곡, 동의어와 약어 누락을 확인합니다. 정리하면 DP는 기억하며 최적화하고, Greedy는 지금 최선만 보고 전진하며, D&C는 쪼개고 풀고 합치고, Backtracking은 선택하고 탐색하고 되돌립니다.
같은 레이어