Algorithm Paradigms

분류: Layer 10 - 자료구조 & 알고리즘

Algorithm Paradigms (알고리즘 패러다임)

1. 한 줄 정의

문제를 푸는 전략의 분류 체계 — Dynamic Programming(최적 부분 구조 반복 저장), Greedy(매 단계 최선 선택), Divide & Conquer(분할 후 합산)은 각기 다른 접근 방식으로 알고리즘 설계의 근간을 이룬다.

2. 왜 중요한가

알고리즘 패러다임을 모르면 “어떻게 풀어야 하지?”라는 질문에서 막힌다. 반면 패러다임을 알면 문제 유형을 보자마자 접근법이 떠오른다.

프론트엔드 브릿지: React의 useMemo/React.memo가 DP의 Memoization 패턴 그대로다 — 같은 입력에 대해 이전에 계산한 결과를 재사용하여 불필요한 재계산을 막는다. Webpack의 code splitting은 Divide & Conquer 패턴이다 — 전체 번들을 작은 청크로 분할하여 필요한 부분만 병렬로 로드한다. 알고리즘 패러다임은 언어와 레이어를 초월한 범용 설계 원리다.

실무 연결 포인트:

비용 최적화 로직 (배포 스케줄, 리소스 할당) → DP
빠른 근사 해 (쿠폰 할인, 작업 스케줄링) → Greedy
정렬, 검색, 배치 처리 → Divide & Conquer
검색 엔진, 추천 시스템 → 유사도 메트릭 + 역색인
Elasticsearch 쿼리 스코어링 → BM25 이해 필요

기술 면접에서도 “이 문제를 왜 DP로 풀었나요?”라는 질문에 명확히 답할 수 있어야 한다.

2.5. 패러다임이 등장한 이유 — Brute Force의 한계

알고리즘 패러다임 이전, 모든 최적화 문제는 전수 탐색(Brute Force) 으로 풀렸다. n개 아이템에서 최적 조합을 찾으려면 2^n개 부분집합을 모두 시도해야 했고, n개 작업의 순서를 정하려면 n! 개 순열을 비교해야 했다. 단순 재귀 fib(40)이 약 800ms 걸리는 이유다(본문 9장 직접 확인 참조) — n=50이면 약 1조 회 호출로 분 단위로 폭발한다. 실시간 의사결정에 사용할 수 없는 복잡도였다.

전환점은 1953년 RAND Corporation의 Richard Bellman이었다. 그는 다단계 의사결정(sequential decision) 문제를 풀면서 “최적 정책은 첫 결정이 어떻든 그 이후 결정들이 결과 상태에서 다시 최적이어야 한다”는 최적성 원리(Principle of Optimality) 를 정식화하고, 이를 기반으로 Dynamic Programming 을 발표했다 (출처: Wikipedia — Richard E. Bellman, Bellman 1954 — Theory of Dynamic Programming (AMS)). 이후 60~70년대에 Greedy(Kruskal·Huffman 등)와 D&C(FFT·Merge Sort)가 같은 흐름에서 정리되며, 각 패러다임이 brute force의 어떤 한계를 풀었는지가 다음과 같이 구분된다:

DP: 중복 부분 문제를 발견하면 재귀 호출 트리 O(2^n) 노드를 고유 하위 문제 O(n)~O(n²)개로 압축. 예: fib(40) 약 10억 회 → 40 회 (~800ms → ~0.1ms, 본문 9장 실측).
Greedy: 탐욕 선택 성질이 성립하는 문제에 한해 정렬 O(n log n) + 1패스 O(n)으로 전역 최적 보장. 단 0/1 Knapsack은 NP-hard라 Greedy가 최적해를 놓친다(3-2 반례 참조).
D&C: 독립 하위 문제로 쪼개 멀티코어·Lambda 팬아웃으로 병렬화. 같은 O(n log n)이라도 Merge Sort가 대용량에서 Quick Sort보다 선호되는 이유.
Backtracking: Pruning으로 2^n 탐색 공간 중 제약 위반 가지를 조기 차단. 예: 4-Queens는 4^4=256가지 대신 약 8~10회 호출로 해결.

이 토픽이 사라지면 무엇이 깨지는가: 비용 최적화·스케줄링·검색 랭킹이 brute force로 회귀해 NP-hard 문제는 실시간 처리가 불가능해진다. Kubernetes 스케줄러는 노드 배치마다 분 단위, Elasticsearch 검색은 쿼리마다 초 단위로 느려진다 — 이것이 “지수 탐색을 다항/선형으로 전환”한 패러다임 등장의 본질이다.

3. 핵심 개념

3-1. Dynamic Programming (동적 프로그래밍)

비유로 이해하기

“이미 계산한 건 다시 계산하지 않는다.”

계단을 오르는 방법을 메모장에 기록해두고, 같은 계단 수에 대한 질문이 오면 메모장을 꺼내서 바로 답하는 것.

핵심 두 가지 조건

DP가 적용 가능하려면 두 조건을 만족해야 한다:

중복 부분 문제 (Overlapping Subproblems): 같은 하위 문제가 반복해서 등장한다.
최적 부분 구조 (Optimal Substructure): 전체 문제의 최적해가 하위 문제의 최적해로 구성된다.

피보나치 수열이 대표적인 예시다. fib(5)를 계산하려면 fib(4) + fib(3)이 필요한데, fib(3)은 fib(4) 계산 중에도, fib(3) 직접 계산 중에도 또 등장한다. 이 중복을 제거하면 극적으로 빨라진다.

왜 DP는 “이렇게” 동작하는가 — 재귀 트리로 이해하기

DP의 본질은 재귀 호출 트리에서 중복 노드를 제거하는 것이다. 순수 재귀로 fib(5)를 계산하면 다음과 같은 호출 트리가 생긴다:

                fib(5)
              /        \
          fib(4)        fib(3)      ← fib(3) 중복!
         /     \       /     \
     fib(3)  fib(2)  fib(2) fib(1)  ← fib(2) 중복!
    /    \
 fib(2) fib(1)

이 트리의 노드 수는 **O(2^n)**이다. 즉 n=40이면 약 10억 번의 연산이 필요하다. 하지만 실제로 고유한 하위 문제는 fib(0) ~ fib(5)까지 단 6개뿐이다. DP는 이 6개만 한 번씩 계산하고 나머지는 캐시에서 꺼내므로 O(n)으로 줄어든다.

이것이 DP가 “지수 시간을 다항 시간으로 바꾸는 마법”의 원리다. 중복이 많을수록 효과가 극적이고, 중복이 없으면 DP를 쓸 이유가 없다(그때는 D&C가 적합하다).

📖 더 보기: Educative — Memoization vs. Tabulation — 두 DP 접근법의 성능 차이를 시각적으로 비교 (입문)

Top-Down: Memoization (메모이제이션)

재귀로 내려가면서, 이미 계산한 결과를 캐시(memo)에 저장하는 방식.

// Top-Down: Memoization
function fibonacci(n, memo = {}) {
  // 기저 사례
  if (n <= 1) return n;

  // 캐시 확인: 이미 계산한 적 있으면 바로 반환
  if (memo[n] !== undefined) return memo[n];

  // 처음 계산하는 경우: 결과를 memo에 저장
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(10)); // 55
console.log(fibonacci(50)); // 12586269025 (재귀만으로는 수십 초 걸릴 계산)

예상 출력:

55
12586269025

Top-Down의 특징:

직관적 — 재귀 구조가 문제 정의와 일치한다
필요한 하위 문제만 풀린다 (lazy evaluation)
스택 오버플로우 위험이 있다 (재귀 깊이 한계)

Bottom-Up: Tabulation (타뷸레이션)

가장 작은 문제부터 순서대로 계산해 테이블(배열)을 채우는 방식.

// Bottom-Up: Tabulation
function fibonacciTabulation(n) {
  if (n <= 1) return n;

  // dp[i] = i번째 피보나치 수
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;

  // 아래에서 위로 채운다
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fibonacciTabulation(10)); // 55
console.log(fibonacciTabulation(50)); // 12586269025

예상 출력:

55
12586269025

Bottom-Up의 특징:

반복문 기반이라 스택 오버플로우 없음
보통 더 빠르다 (함수 호출 오버헤드 없음)
모든 하위 문제를 계산해야 한다

Top-Down vs Bottom-Up: 어떤 상황에서 뭘 선택하나

실무에서 어떤 DP 방식을 선택할지는 다음 기준으로 판단한다:

기준	Top-Down (Memoization)	Bottom-Up (Tabulation)
구현 난이도	재귀가 자연스러운 문제에서 쉬움	점화식을 명확히 정의해야 함
성능	함수 호출 오버헤드 있음	배열 접근만으로 더 빠름
메모리 제어	캐시를 해시맵으로 관리 (메모리 예측 어려움)	배열 크기를 사전에 할당 (메모리 예측 용이)
불필요한 계산	필요한 하위 문제만 풀림 (lazy)	모든 하위 문제를 풀어야 함
스택 안전성	JavaScript에서 n > 10,000이면 위험	스택 사용 안 함 → 안전
공간 최적화	어려움	이전 행만 유지하는 등 최적화 가능

실무 권장: JavaScript/TypeScript 환경에서는 n이 커질 수 있다면 Bottom-Up을 기본으로 사용하고, 문제 구조가 재귀적이고 n이 작을 때만 Top-Down을 사용한다. Tabulation이 일반적으로 성능이 더 좋은데, 재귀 오버헤드가 없고 CPU 캐시 적중률(cache locality)도 높기 때문이다.

📖 더 보기: Baeldung — Tabulation vs. Memoization — 두 방식의 이론적 배경과 실용적 선택 기준 (중급)

계단 오르기 문제 (실전 DP)

한 번에 1계단 또는 2계단을 오를 수 있을 때, n번째 계단에 오르는 방법의 수.

function climbStairs(n) {
  if (n <= 2) return n;

  // dp[i] = i번째 계단에 오르는 방법의 수
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1; // 1계단: 한 가지
  dp[2] = 2; // 2계단: (1+1), (2) 두 가지

  for (let i = 3; i <= n; i++) {
    // i번째 계단에 오려면:
    // - (i-1)번째에서 1계단 오르거나
    // - (i-2)번째에서 2계단 오르거나
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(climbStairs(5)); // 8
console.log(climbStairs(10)); // 89

예상 출력:

8
89

Nest.js/AWS 실무 연결: DP가 실제 백엔드 시스템에서 쓰이는 상황

시나리오 1 — AWS 비용 최적화 (0/1 Knapsack): 월 예산 내에서 최대 처리량을 달성하는 EC2/Lambda 조합을 찾는 문제는 0/1 Knapsack 문제다. Greedy(가성비 순 선택)로 풀면 최적해를 보장하지 못하고, DP로 풀어야 한다.

시나리오 2 — 배포 파이프라인 캐시 전략: CI/CD에서 어떤 모듈의 빌드 캐시를 유지할지 결정하는 것도 DP 패턴이다. 이전 빌드 결과를 dp[module_hash] 형태로 저장해두고, 변경된 파일의 해시가 같으면 재빌드를 건너뛴다.

시나리오 3 — Nest.js 재시도 로직 최적화: 외부 API 호출 실패 시 재시도 횟수와 지연(backoff)을 결정하는 것도 DP 관점이다. 각 시도의 성공 확률과 비용을 고려해 최적 재시도 전략을 구성한다.

// Nest.js에서 메모이제이션 패턴 활용 — 중복 DB 쿼리 제거
@Injectable()
export class PermissionService {
  private memo = new Map<string, boolean>(); // Top-Down DP의 cache

  async hasPermission(userId: string, resource: string): Promise<boolean> {
    const key = `${userId}:${resource}`;

    // 이미 계산한 결과는 재사용 (Memoization)
    if (this.memo.has(key)) return this.memo.get(key)!;

    // 처음 계산: DB에서 조회 후 저장
    const result = await this.db.checkPermission(userId, resource);
    this.memo.set(key, result);
    return result;
  }
}
// 요청 하나에 같은 권한 체크가 5번 발생해도 DB 쿼리는 1번

📖 더 보기: GeeksforGeeks — Tabulation vs Memoization — Top-Down과 Bottom-Up 비교를 코드로 설명 (입문)

LCS (Longest Common Subsequence, 최장 공통 부분 수열)

두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제. Git diff, 표절 감지 등에 활용된다.

function lcs(str1, str2) {
  const m = str1.length;
  const n = str2.length;

  // 2D dp 테이블: dp[i][j] = str1[0..i-1], str2[0..j-1]의 LCS 길이
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        // 같은 문자: 대각선 값 + 1
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // 다른 문자: 위 또는 왼쪽 중 큰 값
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n]; // LCS의 길이
}

console.log(lcs("ABCBDAB", "BDCAB")); // 4 ("BCAB" 또는 "BDAB")
console.log(lcs("AGGTAB", "GXTXAYB")); // 4 ("GTAB")

예상 출력:

4
4

3-2. Greedy (그리디 알고리즘)

비유로 이해하기

“눈앞의 가장 좋아 보이는 것을 무조건 집는다.”

편의점에서 잔돈을 돌려줄 때 항상 “가장 큰 동전부터” 준다. 870원 거스름돈이면 500원 → 100원×3 → 50원×1 → 10원×2. 이 방법이 동전 개수를 최소화한다 (단, 동전 종류가 표준적일 때만).

핵심 원리

매 단계에서 현재 기준으로 최선인 선택을 하고, 절대 되돌아가지 않는다. 지역 최적(local optimum)의 연속이 전체 최적(global optimum)이 되는지는 문제에 따라 다르다.

Greedy가 올바른 해를 보장하는 조건:

탐욕 선택 성질 (Greedy Choice Property): 지역 최적 선택이 전체 최적해의 일부다.
최적 부분 구조: DP와 동일하게 필요.

왜 Greedy는 “되돌아가지 않아도” 되는가

Greedy가 DP보다 빠른 이유는 되돌아보지 않기 때문이다. DP는 모든 하위 문제를 테이블에 저장하고 비교하지만, Greedy는 현재 단계의 최선만 선택하고 전진한다. 이 때문에 시간 복잡도가 보통 O(n log n)(정렬) + O(n)(선택) 정도로, DP의 O(n^2)이나 O(n × W)보다 훨씬 빠르다.

하지만 이것은 양날의 검이다. Greedy가 정답을 보장하려면, “지금 최선의 선택이 나중에도 후회되지 않아야” 한다. 수학적으로 이를 탐욕 선택 성질이라 한다. 이 성질이 성립하지 않는 문제(예: 0/1 Knapsack)에 Greedy를 적용하면 최적해를 놓친다.

실무에서의 판단법: 문제를 받으면 먼저 Greedy로 풀 수 있는지 반례를 3개 정도 직접 만들어본다. 반례가 없으면 Greedy를 사용하고, 하나라도 발견되면 DP로 전환한다. 대규모 시스템에서는 Greedy의 근사해가 충분히 실용적인 경우가 많아(예: Kubernetes 스케줄러), 반드시 최적해가 아니어도 되는 상황에서는 Greedy가 더 나은 선택이다.

📖 더 보기: GetSdeReady — Greedy vs Dynamic Programming: Right DSA Approach — 실제 문제 유형별 DP/Greedy 선택 가이드 (중급)

동전 거스름돈 (Greedy가 통하는 경우)

function makeChange(amount, coins) {
  // 동전을 큰 것부터 정렬
  const sortedCoins = [...coins].sort((a, b) => b - a);
  const result = [];

  for (const coin of sortedCoins) {
    // 현재 금액보다 작거나 같은 동전을 최대한 사용
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }

  return { coins: result, count: result.length };
}

// 한국 동전: 500, 100, 50, 10 (Greedy가 항상 최적)
const result = makeChange(870, [500, 100, 50, 10]);
console.log(result);
// { coins: [500, 100, 100, 100, 50, 10, 10], count: 7 }

예상 출력:

{ coins: [ 500, 100, 100, 100, 50, 10, 10 ], count: 7 }

Nest.js/AWS 실무 연결: Greedy가 실제 인프라 결정에서 쓰이는 상황

Kubernetes 파드 스케줄링: Kubernetes의 기본 스케줄러는 Greedy 전략을 사용한다. 가장 여유 있는 노드(현재 CPU/메모리 사용률이 낮은 노드)에 우선 배치한다. 완벽한 최적해는 NP-hard 문제라 Greedy 근사로 충분히 실용적이다.

로드밸런서 알고리즘: AWS ALB의 Least Outstanding Requests 알고리즘은 현재 처리 중인 요청이 가장 적은 인스턴스에 새 요청을 보내는 Greedy 전략이다. 매 요청마다 “지금 가장 여유 있는 서버”를 선택한다.

배치 작업 스케줄링 (Activity Selection): 데이터 마이그레이션 작업들이 겹칠 수 없을 때(같은 DB 테이블 Lock 사용), 종료 시간 기준 Greedy로 최대한 많은 작업을 배치할 수 있다.

// Nest.js에서 Greedy로 작업 스케줄링
@Injectable()
export class MigrationScheduler {
  scheduleNonOverlapping(
    tasks: Array<{ name: string; start: number; end: number }>,
  ) {
    // Greedy: 종료 시간 기준 정렬 → 빨리 끝나는 것부터 선택
    const sorted = [...tasks].sort((a, b) => a.end - b.end);
    const selected: typeof tasks = [];
    let lastEnd = -Infinity;

    for (const task of sorted) {
      if (task.start >= lastEnd) {
        selected.push(task);
        lastEnd = task.end;
      }
    }
    return selected; // 겹치지 않는 최대 작업 목록
  }
}

📖 더 보기: Educative — Greedy vs Dynamic Programming — 실제 문제를 보고 DP/Greedy 중 무엇을 써야 할지 판단하는 기준 (중급)

Greedy가 실패하는 경우

동전이 [1, 3, 4]이고 잔돈이 6원이라면:

Greedy: 4 + 1 + 1 = 3개
최적: 3 + 3 = 2개

이런 경우는 DP가 필요하다.

// Greedy가 최적이 아닌 반례 확인
const wrong = makeChange(6, [4, 3, 1]);
console.log(wrong); // { coins: [4, 1, 1], count: 3 } <- 최적은 [3, 3], 2개!

예상 출력:

{ coins: [ 4, 1, 1 ], count: 3 }

더 위험한 반례 — 0/1 Knapsack (NP-hard)

가방 용량 50lb, 아이템 3개:

Item	weight	value	density (value/weight)
1	10lb	$60	6.0 (최고)
2	20lb	$100	5.0
3	30lb	$120	4.0

Greedy (density 내림차순): Item 1 + Item 2 = 30lb 사용 → 가방에 20lb 남았지만 Item 3은 30lb라 못 넣음 → 합 $160, 20lb 낭비. DP 최적: Item 1을 일부러 건너뛰고 Item 2 + Item 3 (20+30=50lb perfect fit) → 합 $220 — Greedy 대비 +37.5% (출처: GfG — Difference between 0/1 and Fractional Knapsack, Wikipedia — Knapsack problem).

핵심: 분수형 Knapsack(아이템을 쪼갤 수 있음)은 같은 density 정렬 Greedy로 O(n log n)에 최적해를 보장한다. 0/1 Knapsack은 NP-hard이고 DP가 필요한 이유는 “쪼갤 수 없다”는 한 줄 차이다 — 입력 스키마(아이템이 atomic인지 divisible인지)를 보고 즉시 식별해야 한다.

Silent failure 경고: Greedy 구현이 균등한 density 분포 테스트에서는 통과하다가 skewed 입력(위처럼 큰 아이템 1개 + 작은 아이템 다수)에서만 5~37% suboptimal 결과를 낸다. 다음 진단으로 운영 배포 전에 잡는다:

# skewed 입력 + brute force baseline 비교
node -e "
const items = [{w:10,v:60},{w:20,v:100},{w:30,v:120}];
const cap = 50;
const g = greedyKnapsack(items, cap);   // Greedy 결과
const d = dpKnapsack(items, cap);       // DP 결과 (baseline)
const loss = ((d - g) / d * 100).toFixed(1);
console.log({greedy:g, dp:d, loss_pct: loss});
"
# 예상 출력: { greedy: 160, dp: 220, loss_pct: '27.3' }
# loss_pct > 0  →  DP 전환 필수.  다음 단계: 본문 3-3-2의 knapsack01 1D DP 코드로 교체.

📖 더 보기: Wikipedia — Knapsack problem (NP-hardness 절) — 분할 가능/불가능에 따른 복잡도 분기 (중급)

활동 선택 문제 (Activity Selection)

겹치지 않게 최대한 많은 회의를 배정하는 문제. Greedy가 최적해를 보장하는 대표 예시.

function activitySelection(activities) {
  // 종료 시간 기준으로 정렬 (핵심!)
  const sorted = [...activities].sort((a, b) => a.end - b.end);

  const selected = [sorted[0]]; // 첫 번째 활동 선택
  let lastEnd = sorted[0].end;

  for (let i = 1; i < sorted.length; i++) {
    // 이전 활동이 끝난 후 시작하는 활동만 선택
    if (sorted[i].start >= lastEnd) {
      selected.push(sorted[i]);
      lastEnd = sorted[i].end;
    }
  }

  return selected;
}

const activities = [
  { name: "A", start: 1, end: 4 },
  { name: "B", start: 3, end: 5 },
  { name: "C", start: 0, end: 6 },
  { name: "D", start: 5, end: 7 },
  { name: "E", start: 3, end: 9 },
  { name: "F", start: 6, end: 10 },
];

console.log(activitySelection(activities));
// [ {name: "A", ...}, {name: "B", ...}, {name: "D", ...}, {name: "F", ...} ]

예상 출력:

[
  { name: 'A', start: 1, end: 4 },
  { name: 'B', start: 3, end: 5 },
  { name: 'D', start: 5, end: 7 },
  { name: 'F', start: 6, end: 10 }
]

3-3. Divide and Conquer (분할 정복)

비유로 이해하기

“큰 문제를 반으로 쪼개고, 각각 풀고, 합친다.”

전화번호부에서 이름을 찾을 때 처음부터 보지 않는다. 가운데를 펴서 기준을 잡고, 앞 절반이나 뒤 절반으로 범위를 좁히는 것이 이진 탐색이다.

핵심 3단계

Divide (분할): 문제를 더 작은 동일한 형태의 하위 문제로 나눈다.
Conquer (정복): 하위 문제를 재귀적으로 푼다. 충분히 작으면 직접 푼다.
Combine (합산): 하위 문제의 해를 합쳐 전체 문제의 해를 만든다.

DP와의 차이점: D&C는 하위 문제들이 서로 겹치지 않는다(independent). 겹치면 DP가 더 효율적이다.

왜 D&C는 “겹치지 않는 문제”에서 효율적인가

D&C의 효율성은 **병렬성(parallelism)**에서 나온다. 하위 문제들이 서로 독립적이므로 동시에 풀 수 있다. Merge Sort에서 왼쪽 절반과 오른쪽 절반은 서로 영향을 주지 않으므로, 멀티코어 CPU나 분산 시스템에서 진정한 병렬 처리가 가능하다.

이것이 D&C가 대용량 데이터 처리의 핵심 패턴인 이유다. MapReduce, AWS Lambda의 팬아웃 패턴, 데이터베이스 파티셔닝 모두 D&C 원리의 확장이다. 문제를 쪼개고(Divide), 각 Worker가 독립적으로 처리하고(Conquer), 결과를 합치는(Combine) 3단계를 따른다.

반면 DP는 하위 문제들이 서로 의존하므로 병렬화가 어렵다. dp[i]를 계산하려면 dp[i-1]이 먼저 계산되어야 하기 때문이다. 이것이 같은 O(n log n)이라도 Merge Sort(D&C)가 대용량 환경에서 Quick Sort보다 선호되는 이유 중 하나다.

Merge Sort (병합 정렬)

function mergeSort(arr) {
  // 기저 사례: 원소가 1개이면 이미 정렬됨
  if (arr.length <= 1) return arr;

  // Divide: 배열을 반으로 나눔
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Conquer: 각각 재귀적으로 정렬
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Combine: 정렬된 두 배열을 합침
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  // 두 배열을 비교하며 작은 것부터 결과에 넣음
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // 남은 원소들 추가
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

예상 출력:

[3, 9, 10, 27, 38, 43, 82]

Merge Sort의 시간 복잡도가 항상 **O(n log n)**인 이유:

분할: 매 단계에서 배열을 절반으로 → log n 깊이
합산: 각 깊이에서 총 n개의 원소를 비교 → n 작업
결과: n × log n

Binary Search (이진 탐색)

function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sortedArr[mid] === target) {
      return mid; // 찾음: 인덱스 반환
    } else if (sortedArr[mid] < target) {
      left = mid + 1; // 오른쪽 절반으로
    } else {
      right = mid - 1; // 왼쪽 절반으로
    }
  }

  return -1; // 없음
}

const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sorted, 7)); // 3 (인덱스)
console.log(binarySearch(sorted, 10)); // -1 (없음)

예상 출력:

3
-1

Nest.js/AWS 실무 연결: D&C가 실제 백엔드 아키텍처에 어떻게 적용되나

AWS Map-Reduce 패턴: 대용량 데이터를 처리할 때 D&C를 적용한다. S3의 10GB 데이터를 처리할 때 Lambda를 여러 개 띄워 청크로 나눠 처리(Divide+Conquer) 후 결과를 합산(Combine)하는 것이 D&C 패턴이다.

병렬 API 호출: Nest.js에서 여러 외부 서비스를 동시에 호출하고 결과를 합치는 패턴도 D&C다.

// Nest.js에서 D&C 패턴 — 대량 데이터 병렬 처리
@Injectable()
export class ReportService {
  async generateMonthlyReport(userIds: string[]): Promise<Report[]> {
    // Divide: 1000명 단위로 청크 분할
    const chunkSize = 1000;
    const chunks: string[][] = [];
    for (let i = 0; i < userIds.length; i += chunkSize) {
      chunks.push(userIds.slice(i, i + chunkSize));
    }

    // Conquer: 각 청크를 병렬로 처리 (Promise.all = D&C의 병렬 정복)
    const results = await Promise.all(
      chunks.map((chunk) => this.processChunk(chunk)),
    );

    // Combine: 결과 병합
    return results.flat();
  }

  private async processChunk(userIds: string[]): Promise<Report[]> {
    // 각 청크 독립적으로 처리 (D&C의 하위 문제)
    return this.db.getReports({ userIds });
  }
}
// 10만 유저를 100개의 청크로 나눠 병렬 처리 → 순차 처리 대비 ~100배 속도

AWS Step Functions 병렬 실행: Step Functions의 Parallel 상태는 D&C의 Conquer 단계를 클라우드 수준에서 구현한 것이다. 각 브랜치가 독립적 하위 문제를 처리하고, 모든 브랜치 완료 후 다음 상태로 진행(Combine)한다.

📖 더 보기: Medium — Algorithm Design Paradigms: Divide and Conquer — D&C의 3단계(Divide/Conquer/Combine)를 여러 알고리즘으로 설명 (입문)

Master Theorem (마스터 정리) 개요

D&C 알고리즘의 시간 복잡도는 점화식 T(n) = aT(n/b) + f(n) 으로 표현된다 (a ≥ 1, b > 1, f(n) > 0 점근 양수):

a: 하위 문제의 개수
b: 각 하위 문제의 크기 축소 비율
f(n): 분할/합산 비용

알고리즘	점화식	결과
Merge Sort	T(n) = 2T(n/2) + n	O(n log n)
Binary Search	T(n) = T(n/2) + 1	O(log n)
Naive Matrix Multiply	T(n) = 8T(n/2) + n²	O(n³)

핵심 판단: f(n)과 n^(log_b a)를 비교해 어느 쪽이 지배적인지 결정한다. CLRS(Cormen·Leiserson·Rivest·Stein)가 정리한 3 case는 다음과 같다:

Case 1 — leaves-dominated: f(n) = O(n^(log_b a − ε)) (어떤 ε>0)이면 → T(n) = Θ(n^(log_b a)). 하위 호출 수가 지배. 예: T(n) = 4T(n/2) + n → log_2 4 = 2, n^2 > n → Θ(n²).
Case 2 — balanced: f(n) = Θ(n^(log_b a) · log^k n) (k ≥ 0)이면 → T(n) = Θ(n^(log_b a) · log^(k+1) n). 두 비용이 동급. 예: Merge Sort — log_2 2 = 1, n^1 = f(n) → Θ(n log n).
Case 3 — root-dominated: f(n) = Ω(n^(log_b a + ε))이고 regularity 조건(어떤 c<1에 대해 a·f(n/b) ≤ c·f(n))을 만족하면 → T(n) = Θ(f(n)). 분할/합산 비용이 지배. 예: T(n) = 2T(n/2) + n² → log_2 2 = 1, n² > n → Θ(n²).

📖 출처: Wikipedia — Master theorem (analysis of algorithms) — CLRS 표기 기반 3 case 정의 + regularity 조건 (중급).

판단 절차: ① log_b a 계산 → ② n^(log_b a)와 f(n) 점근 비교 → ③ 어느 case인지 매칭. 어느 case에도 안 맞으면 (예: f(n)이 log를 포함한 비표준 형태) Master Theorem은 적용 불가하므로 Akra–Bazzi 일반화 정리나 직접 트리 합으로 폴백한다.

3-3-0. Backtracking (백트래킹)

비유로 이해하기

“미로를 탈출하려고 한 방향으로 가다가 막히면 왔던 길로 되돌아와 다른 방향을 시도한다.”

백트래킹은 가능한 모든 선택지를 탐색하되, 조건을 위반하면 즉시 되돌아가는 전략이다. Brute Force보다 효율적인 이유는 “가망 없는 경로(dead end)“를 조기에 포기(Pruning)하기 때문이다.

핵심 원리

백트래킹 3단계 패턴:
1. 선택 (Choose): 현재 단계에서 가능한 선택을 한다
2. 탐색 (Explore): 재귀적으로 다음 단계를 탐색한다
3. 철회 (Unchoose): 탐색이 끝나면 선택을 되돌린다 (핵심!)

DFS vs Backtracking 차이:
- DFS: 모든 노드를 방문한다 (visited 체크)
- Backtracking: 제약 조건을 위반하면 즉시 탐색 중단 (Pruning)
               → 유효하지 않은 상태 공간을 가지치기하여 효율 향상

왜 백트래킹이 “되돌아가야” 하는가: 백트래킹은 상태를 직접 수정했다가 되돌리는 방식으로 동작한다. 선택을 추가한 후 재귀 탐색, 탐색 완료 후 선택 제거 — 이 과정을 통해 하나의 배열/보드를 재사용하며 모든 가능성을 탐색한다. 선택을 되돌리지 않으면 이전 상태가 오염되어 올바른 탐색이 불가능해진다.

📖 더 보기: FreeCodeCamp — Backtracking Algorithms Explained — N-Queens 문제를 통해 백트래킹의 핵심 아이디어를 직관적으로 설명 (입문)

코드 예시: 순열(Permutation) 생성

// 배열의 모든 순열 생성 — 백트래킹의 기본 패턴
// 시간: O(n! × n), 공간: O(n) — 재귀 깊이
function permutations(nums) {
  const result = [];

  function backtrack(current, remaining) {
    // 기저 사례: 선택할 것이 없으면 완성된 순열 저장
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      // 1. 선택 (Choose)
      current.push(remaining[i]);
      const nextRemaining = [
        ...remaining.slice(0, i),
        ...remaining.slice(i + 1),
      ];

      // 2. 탐색 (Explore)
      backtrack(current, nextRemaining);

      // 3. 철회 (Unchoose)
      current.pop(); // 반드시 되돌려야 함!
    }
  }

  backtrack([], nums);
  return result;
}

console.log(permutations([1, 2, 3]));

예상 출력:

[
  [1, 2, 3], [1, 3, 2],
  [2, 1, 3], [2, 3, 1],
  [3, 1, 2], [3, 2, 1]
]

코드 예시: N-Queens 문제 (Pruning의 위력)

체스판 N×N에 N개의 퀸을 서로 공격하지 않도록 배치하는 경우의 수.

// N-Queens: Backtracking + Pruning
// 시간: O(N!), 공간: O(N)
function solveNQueens(n) {
  const solutions = [];
  const cols = new Set(); // 이미 사용된 열
  const diag1 = new Set(); // 우하향 대각선 (row - col)
  const diag2 = new Set(); // 우상향 대각선 (row + col)

  function backtrack(row, board) {
    if (row === n) {
      solutions.push(
        board.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1)),
      );
      return;
    }

    for (let col = 0; col < n; col++) {
      // Pruning: 충돌하면 즉시 건너뜀
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
        continue;
      }

      // 1. 선택
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      board.push(col);

      // 2. 탐색
      backtrack(row + 1, board);

      // 3. 철회
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
      board.pop();
    }
  }

  backtrack(0, []);
  return solutions.length; // 해의 개수
}

console.log(solveNQueens(4)); // 2  (4×4 보드에서 2가지 배치)
console.log(solveNQueens(8)); // 92 (8×8 보드에서 92가지 배치)

예상 출력:

2
92

Pruning 효과: 4-Queens에서 Brute Force는 4^4 = 256가지를 모두 탐색하지만, 백트래킹은 약 8~10회 호출로 해결한다. 조건 위반을 조기에 감지해서 해당 경로 전체를 건너뛰기 때문이다.

NestJS/AWS 실무 연결: 백트래킹이 실제 어디서 쓰이나

API 권한 조합 탐색: 여러 권한 중 주어진 자원에 접근 가능한 권한 조합을 찾는 문제. 전체 조합(2^n)을 탐색하지 않고, 조건 위반 시 조기 종료한다.

Terraform 의존성 그래프 검증: 순환 참조가 없는 유효한 리소스 배포 순서를 찾을 때, 백트래킹으로 DAG 탐색을 최적화한다.

// NestJS에서 백트래킹 패턴 — 권한 조합 탐색
@Injectable()
export class PermissionCombinationService {
  // n개의 권한 중 조건을 만족하는 최소 조합 찾기
  findMinPermissions(
    permissions: string[],
    requiredActions: Set<string>,
    coveredActions: Set<string> = new Set(),
    index = 0,
    current: string[] = [],
    result: string[][] = [],
  ): string[][] {
    // 기저 사례: 모든 액션이 커버됨
    if ([...requiredActions].every((a) => coveredActions.has(a))) {
      result.push([...current]);
      return result;
    }

    for (let i = index; i < permissions.length; i++) {
      const perm = permissions[i];
      const newCovered = new Set([...coveredActions, perm]);

      current.push(perm);
      this.findMinPermissions(
        permissions,
        requiredActions,
        newCovered,
        i + 1,
        current,
        result,
      );
      current.pop(); // 철회
    }
    return result;
  }
}

📖 더 보기: GeeksforGeeks — N Queen Problem using Backtracking — N-Queens 백트래킹 풀이를 단계별로 설명. Pruning 효과 시각화 포함 (입문~중급)

3-3-1. 패러다임 선택 실전 가이드 (심화)

비유로 이해하기

“요리사가 오늘의 재료로 무슨 요리를 할지 결정하는 방법”

DP: 냉장고에 있는 재료를 모두 파악하고, 가장 비용 효율이 좋은 요리법을 계산한다. 모든 조합을 고려하지만 이미 계산한 건 메모해서 재사용한다.
Greedy: 지금 가장 맛있어 보이는 재료부터 쓴다. 빠르지만 나중에 더 좋은 조합을 놓칠 수 있다.
D&C: 요리를 파트별로 나눠서 각 파트를 독립적으로 준비하고 마지막에 합친다.

패러다임 판단 플로우차트 (실전)

문제를 받으면 다음 순서로 판단한다:

Step 1: 하위 문제가 반복 등장하는가?
         YES → DP 후보
         NO  → D&C 후보

Step 2 (DP 후보일 때): Greedy로도 풀 수 있는가?
         YES (탐욕 선택 성질 성립) → Greedy가 더 빠름, Greedy 사용
         NO                       → DP 사용

Step 3 (D&C 후보일 때): 하위 문제가 서로 독립적인가?
         YES → D&C (병렬 처리 가능)
         NO  → DP (하위 문제가 서로 의존)

Step 4: 최적해가 필요 없고, 근사해로 충분한가?
         YES → Greedy (속도 우선)
         NO  → DP 또는 D&C

Greedy가 최적해를 보장하는 문제의 특징

실무에서 Greedy를 안전하게 쓸 수 있는 문제 유형:

문제 유형	Greedy 적용 가능 이유
활동 선택 (Activity Selection)	종료 시간 기준 정렬 후 선택 → 탐욕 선택 성질 성립
Huffman 인코딩	최소 빈도 문자 먼저 합치기 → 최적 접두사 코드 보장
Kruskal’s MST	가중치 오름차순 엣지 선택 → 최소 스패닝 트리 보장
동전 교환 (표준 동전 체계)	큰 동전부터 선택 → 한국/미국 동전에서 최적
Dijkstra 최단 경로	최소 거리 노드 선택 → 비가중치 양수 그래프에서 최적

A* 알고리즘: Greedy + DP의 현실적 결합

현대 알고리즘은 종종 두 패러다임을 결합한다. A* 탐색은 Greedy의 휴리스틱(현재 최선 선택)과 DP의 정확한 거리 추적을 조합한다.

// A* 핵심 아이디어: f(n) = g(n) + h(n)
// g(n): 시작 노드에서 n까지의 실제 비용 (DP 방식으로 정확 추적)
// h(n): n에서 목표까지의 예상 비용 (Greedy 방식 휴리스틱)

function aStar(start, goal, graph, heuristic) {
  const openSet = new Map(); // 탐색 후보
  const gScore = new Map(); // 시작 → 현재까지 실제 비용 (DP)
  const fScore = new Map(); // g + h 합산 (Greedy 우선순위)

  gScore.set(start, 0);
  fScore.set(start, heuristic(start, goal));
  openSet.set(start, fScore.get(start));

  while (openSet.size > 0) {
    // f값이 가장 낮은 노드 선택 (Greedy 선택)
    const current = [...openSet.entries()].reduce((a, b) =>
      a[1] < b[1] ? a : b,
    )[0];

    if (current === goal) return gScore.get(goal); // 최적해!

    openSet.delete(current);

    for (const [neighbor, weight] of graph[current] || []) {
      const tentativeG = (gScore.get(current) || Infinity) + weight;

      if (tentativeG < (gScore.get(neighbor) || Infinity)) {
        // 더 좋은 경로 발견 → DP처럼 갱신
        gScore.set(neighbor, tentativeG);
        fScore.set(neighbor, tentativeG + heuristic(neighbor, goal));
        openSet.set(neighbor, fScore.get(neighbor));
      }
    }
  }

  return Infinity; // 경로 없음
}

예상 출력 (맨해튼 거리 휴리스틱 사용 시): A*는 Dijkstra(순수 DP)보다 평균 2~3배 적은 노드를 탐색하면서 최적해를 보장한다.

Nest.js/AWS 실무: 패러다임 선택이 성능을 결정하는 사례

사례 1 — API Rate Limiting 전략 (Greedy)

// Greedy: 현재 시점 기준 최선 선택
// 토큰 버킷 알고리즘 = Greedy 패턴
@Injectable()
export class RateLimiterService {
  private tokens = new Map<string, { count: number; resetAt: number }>();

  isAllowed(clientId: string, maxRequests = 100): boolean {
    const now = Date.now();
    const bucket = this.tokens.get(clientId);

    if (!bucket || now > bucket.resetAt) {
      // 새 버킷 생성 (리셋)
      this.tokens.set(clientId, { count: 1, resetAt: now + 60_000 });
      return true; // Greedy: 지금 허용할 수 있으면 허용
    }

    if (bucket.count < maxRequests) {
      bucket.count++;
      return true; // Greedy: 현재 카운트 기준으로만 판단
    }

    return false; // 한도 초과
  }
}

사례 2 — 배치 처리 비용 최적화 (DP)

// DP: 0/1 Knapsack 패턴 — Greedy로 풀면 최적해 보장 안 됨
@Injectable()
export class CostOptimizer {
  // 예산 내에서 최대 처리량을 달성하는 Lambda 조합 찾기
  findOptimalConfig(
    budget: number,
    configs: Array<{ name: string; cost: number; throughput: number }>,
  ): { total: number; selected: string[] } {
    const n = configs.length;
    // dp[i][b] = configs[0..i]에서 예산 b 이하로 달성 가능한 최대 처리량
    const dp: number[][] = Array.from({ length: n + 1 }, () =>
      new Array(budget + 1).fill(0),
    );

    for (let i = 1; i <= n; i++) {
      const { cost, throughput } = configs[i - 1];
      for (let b = 0; b <= budget; b++) {
        dp[i][b] = dp[i - 1][b]; // 현재 config 제외
        if (b >= cost) {
          dp[i][b] = Math.max(dp[i][b], dp[i - 1][b - cost] + throughput);
        }
      }
    }

    // 역추적으로 선택된 config 찾기
    const selected: string[] = [];
    let b = budget;
    for (let i = n; i >= 1; i--) {
      if (dp[i][b] !== dp[i - 1][b]) {
        selected.push(configs[i - 1].name);
        b -= configs[i - 1].cost;
      }
    }

    return { total: dp[n][budget], selected };
  }
}

// 사용 예시
const configs = [
  { name: "Lambda-128MB", cost: 10, throughput: 100 },
  { name: "Lambda-256MB", cost: 18, throughput: 210 }, // 가성비 최고지만 Greedy로 안 잡힐 수 있음
  { name: "Lambda-512MB", cost: 30, throughput: 360 },
  { name: "EC2-t3.small", cost: 25, throughput: 250 },
];

// Greedy (가성비 순 = throughput/cost): [Lambda-256MB, Lambda-128MB] → 처리량 310
// DP 최적: [Lambda-256MB, EC2-t3.small] 또는 [Lambda-512MB, Lambda-128MB] 등 → 더 나은 조합 가능

3-3-2. 인터뷰/코딩 테스트 패턴 심화

“문제 유형을 보고 바로 패턴을 매칭하는 것이 숙련된 엔지니어의 차이”

인터뷰에서 DP/Greedy/D&C 문제가 나왔을 때 “어떤 알고리즘을 쓸지 생각하는 과정”이 채점된다. 코드를 아는 것과 언제 쓰는지 아는 것은 다르다.

DP 인터뷰 핵심 패턴 5가지

패턴 1: 1D DP — “지금 결정이 이전 결정에 의존”

// 대표 문제: "계단 오르기" — 한 번에 1칸 또는 2칸 오를 수 있을 때 n번째 칸까지 방법 수
// 시간: O(n), 공간: O(1) (롤링 배열 최적화)
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev2 = 1,
    prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2; // dp[i] = dp[i-1] + dp[i-2]
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// climbStairs(5) → 8 (1+1+1+1+1, 2+1+1+1, 1+2+1+1, ..., 2+2+1, 1+2+2, 2+1+2)
console.log(climbStairs(5)); // 8

예상 출력:

공간 최적화 포인트: dp 배열 전체를 저장하면 O(n) 공간이지만, 이전 두 값만 있으면 되므로 O(1)로 줄일 수 있다. 면접에서 이 최적화를 언급하면 좋은 인상을 준다.

패턴 2: 2D DP — “두 시퀀스 비교”

// 대표 문제: 최장 공통 부분 수열 (LCS)
// 시간: O(m×n), 공간: O(m×n) → 행 2개만 유지하면 O(n)으로 최적화 가능
function lcs(s1: string, s2: string): number {
  const m = s1.length,
    n = s2.length;
  // 공간 최적화: 이전 행과 현재 행만 유지
  let prev = new Array(n + 1).fill(0);
  let curr = new Array(n + 1).fill(0);

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    [prev, curr] = [curr, prev]; // 스왑 (배열 재사용)
    curr.fill(0);
  }
  return prev[n];
}

console.log(lcs("ABCBDAB", "BDCAB")); // 4 (BCAB 또는 BDAB)

예상 출력:

패턴 3: 배낭 문제(Knapsack) — “포함/제외 선택”

0/1 Knapsack은 각 아이템을 한 번만 쓸 수 있다. 외부 루프: 아이템, 내부 루프: 용량 역순이 핵심이다.

// 시간: O(n×W), 공간: O(W) — 1D DP로 최적화
function knapsack01(
  weights: number[],
  values: number[],
  capacity: number,
): number {
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 역순으로 순회해야 같은 아이템을 중복 사용하지 않는다
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// 예: 배낭 용량 10, 아이템 (무게, 가치)
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
console.log(knapsack01(weights, values, 10)); // 13 (무게2+3+5, 가치3+4+6)

예상 출력:

역순 순회 이유: 정순이면 dp[w - weights[i]]가 이미 현재 아이템을 포함한 값이라 중복 사용된다. 역순이면 이전 아이템까지의 최적값을 그대로 참조한다.

Greedy 인터뷰 핵심 패턴: Two Pointer + 정렬 조합

Greedy와 Two Pointer를 함께 쓰는 문제가 인터뷰에 자주 등장한다.

// 대표 문제: "Interval Merge" — 겹치는 구간 병합
// 시간: O(n log n), 공간: O(n)
function mergeIntervals(intervals: [number, number][]): [number, number][] {
  if (!intervals.length) return [];

  // Greedy 핵심: 시작 시간 기준 정렬
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: [number, number][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    // 현재 구간 시작이 이전 구간 끝보다 작거나 같으면 겹침
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]); // 끝점 확장
    } else {
      merged.push(intervals[i]); // 새 구간 추가
    }
  }
  return merged;
}

const intervals: [number, number][] = [
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18],
];
console.log(JSON.stringify(mergeIntervals(intervals)));
// [[1,6],[8,10],[15,18]]

예상 출력:

[[1,6],[8,10],[15,18]]

실무 연결: 배치 처리 스케줄링, AWS CloudWatch 알림 구간 병합, 회의실 예약 중복 감지에 직접 적용된다.

시간/공간 복잡도 심화 분석

DP 공간 복잡도 최적화 패턴:

패턴	원래 공간	최적화 후	방법
1D DP (Fibonacci류)	O(n)	O(1)	이전 2개 값만 유지
2D DP (LCS, Edit Distance)	O(m×n)	O(min(m,n))	이전 행만 유지
0/1 Knapsack	O(n×W)	O(W)	1D dp + 역순 순회
Subset Sum	O(n×sum)	O(sum)	1D dp + 역순 순회

공간 최적화 적용 경계 조건 (언제 필수인가):

n × W > 10,000,000 (1천만) → 메모리 ~80MB 초과 → 최적화 필수
  예: n=1000, W=100,000 → O(n×W) = 1억 항목 → ~800MB → OOM

n × W < 1,000,000 (1백만) → ~8MB 이하 → 가독성 우선 (2D dp 유지)

Lambda 128MB 제한 환경: n × W > 1,000,000이면 공간 최적화 고려
  실측: LCS(m=5000, n=5000) → 2D는 200MB, 1D 최적화 → 40KB

DP vs 재귀 복잡도 비교 실측:

// Fibonacci: 재귀 vs Memoization vs Bottom-Up 비교
// 재귀: O(2^n) 시간, O(n) 공간 (콜스택)
// Memo:  O(n) 시간,   O(n) 공간 (memo 배열 + 콜스택)
// Bottom-Up: O(n) 시간, O(1) 공간

function fibNaive(n: number): number {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2); // 2^n 중복 계산
}

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

function fibOptimal(n: number): number {
  if (n <= 1) return n;
  let [a, b] = [0, 1];
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b; // O(n) 시간, O(1) 공간
}

console.time("naive fib(35)");
fibNaive(35);
console.timeEnd("naive fib(35)"); // ~80ms

console.time("memo fib(35)");
fibMemo(35);
console.timeEnd("memo fib(35)"); // ~0.01ms

console.time("optimal fib(35)");
fibOptimal(35);
console.timeEnd("optimal fib(35)"); // ~0.005ms

예상 출력:

naive fib(35): ~80ms
memo fib(35): ~0.01ms
optimal fib(35): ~0.005ms

Nest.js 실무 적용: 배치 작업 최적 분배 (Greedy + 인터뷰 패턴)

// 실무 시나리오: N개의 작업을 K개의 Lambda Worker에 배분하되
// 가장 오래 걸리는 Worker의 시간을 최소화
// → "이진 탐색 + Greedy 검증" 패턴 (Binary Search on Answer)

@Injectable()
export class LambdaSchedulerService {
  // 시간: O(n log(sum)) — 이진 탐색 × 선형 검증
  // 공간: O(1)
  findOptimalDistribution(tasks: number[], workers: number): number {
    let left = Math.max(...tasks); // 최소: 가장 큰 단일 작업
    let right = tasks.reduce((a, b) => a + b, 0); // 최대: 혼자 다 처리

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.canDistribute(tasks, workers, mid)) {
        right = mid; // 더 줄일 수 있다
      } else {
        left = mid + 1;
      }
    }
    return left;
  }

  private canDistribute(
    tasks: number[],
    workers: number,
    maxLoad: number,
  ): boolean {
    let workersNeeded = 1;
    let currentLoad = 0;
    for (const task of tasks) {
      if (currentLoad + task > maxLoad) {
        workersNeeded++;
        currentLoad = task;
        if (workersNeeded > workers) return false;
      } else {
        currentLoad += task;
      }
    }
    return true;
  }
}

// 예: 처리 시간 [3, 2, 3, 1, 2, 3, 6], Lambda 3개
// 결과: 6 (각 Lambda가 최대 6초 이내로 처리)

3-4. 유사도 메트릭 (Similarity Metrics)

Jaccard Similarity (자카드 유사도)

집합 기반의 유사도. “두 집합이 얼마나 겹치는가”

Jaccard(A, B) = |A ∩ B| / |A ∪ B|

function jaccardSimilarity(setA, setB) {
  const intersection = new Set([...setA].filter((x) => setB.has(x)));
  const union = new Set([...setA, ...setB]);
  return intersection.size / union.size;
}

// 사용자 태그 기반 유사도
const user1Tags = new Set(["javascript", "nodejs", "aws"]);
const user2Tags = new Set(["javascript", "python", "aws", "ml"]);

const similarity = jaccardSimilarity(user1Tags, user2Tags);
console.log(`자카드 유사도: ${similarity.toFixed(3)}`); // 0.400 (2/5)

예상 출력:

자카드 유사도: 0.400

용도: 문서 중복 감지, 추천 시스템(공통 아이템 기반), 집합 비교

Cosine Similarity (코사인 유사도)

벡터 기반. “두 벡터가 가리키는 방향이 얼마나 같은가” (크기는 무관)

function cosineSimilarity(vecA, vecB) {
  const dotProduct = vecA.reduce((sum, a, i) => sum + a * vecB[i], 0);
  const magA = Math.sqrt(vecA.reduce((sum, a) => sum + a * a, 0));
  const magB = Math.sqrt(vecB.reduce((sum, b) => sum + b * b, 0));
  return dotProduct / (magA * magB);
}

// TF 벡터: [javascript, python, aws, nodejs, ml] 빈도
const doc1 = [3, 0, 2, 1, 0]; // JS 문서
const doc2 = [1, 2, 1, 0, 3]; // ML 문서
const doc3 = [2, 0, 3, 2, 0]; // 인프라 문서

console.log(`doc1 vs doc2: ${cosineSimilarity(doc1, doc2).toFixed(3)}`); // 낮음
console.log(`doc1 vs doc3: ${cosineSimilarity(doc1, doc3).toFixed(3)}`); // 높음

예상 출력:

doc1 vs doc2: 0.299
doc1 vs doc3: 0.967

용도: 문서 검색, 의미 기반 추천, NLP 임베딩 벡터 비교

Edit Distance / Levenshtein Distance (편집 거리)

두 문자열을 같게 만드는 데 필요한 최소 연산 수(삽입, 삭제, 교체).

function editDistance(s1, s2) {
  const m = s1.length,
    n = s2.length;
  // dp[i][j]: s1[0..i-1]을 s2[0..j-1]로 바꾸는 최소 연산 수
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // 같으면 그대로
      } else {
        dp[i][j] =
          1 +
          Math.min(
            dp[i - 1][j], // 삭제
            dp[i][j - 1], // 삽입
            dp[i - 1][j - 1], // 교체
          );
      }
    }
  }

  return dp[m][n];
}

console.log(editDistance("kitten", "sitting")); // 3
console.log(editDistance("sunday", "saturday")); // 3
console.log(editDistance("hello", "hello")); // 0

예상 출력:

3
3
0

용도: 맞춤법 교정, 퍼지 검색, 자동완성, 유사 레코드 감지

유사도 메트릭 비교표

메트릭	기반	값 범위	주요 사용처
Jaccard	집합 교집합/합집합	0 ~ 1	태그 유사도, 문서 중복
Cosine	벡터 각도	-1 ~ 1	텍스트 검색, 추천
Edit Distance	문자 편집 횟수	0 ~ max	맞춤법 교정, 퍼지 검색

3-5. 심화: 검색 알고리즘 기초 (선택 학습)

이 섹션은 Elasticsearch 등 검색 엔진을 깊이 다룰 때 참고하는 심화 내용입니다. 검색 엔진 내부 구조는 별도 토픽으로 심화 학습 예정입니다.

핵심 개념 요약 (5줄): 역색인(Inverted Index)은 “단어 → 문서 목록” 매핑으로 전체 스캔 없이 빠른 검색을 가능하게 한다. TF-IDF는 단어의 문서 내 빈도(TF)와 전체 문서 희소성(IDF)을 곱해 중요도를 점수화한다. BM25는 TF-IDF를 개선하여 긴 문서 편향을 보정하고 단어 반복 증가에 체감 감소를 적용한다. Dense Index(임베딩 벡터)는 의미 기반 검색을, Sparse Index(역색인)는 키워드 정확도를 제공하며 하이브리드 검색에서 함께 쓰인다. Elasticsearch에서 GET /index/_explain/{id}로 실제 BM25 점수 계산 과정을 확인할 수 있다.

Inverted Index (역색인)

구조: “단어 → 문서 ID 목록(Posting List)” 매핑. 전체 스캔 O(n) 대신 O(1) 조회 + Posting List 교집합 O(k)로 검색.

텍스트: doc1="hello world", doc2="hello elasticsearch", doc3="world peace"

Inverted Index:
  "hello"         → [doc1, doc2]
  "world"         → [doc1, doc3]
  "elasticsearch" → [doc2]
  "peace"         → [doc3]

쿼리 "hello AND world" → [doc1, doc2] ∩ [doc1, doc3] = [doc1]

TF-IDF 점수화:

TF(Term Frequency): 문서 내 단어 빈도 (많이 나올수록 높음)
IDF(Inverse Document Frequency): 전체 문서에서 희소할수록 높음 (log(N/df))
Score = TF × IDF → 흔한 단어(“the”, “is”)는 낮은 IDF로 자동 억제

BM25 (Elasticsearch 기본 랭킹):

TF-IDF 개선: 단어 반복 증가 시 체감 감소(k1 파라미터), 문서 길이 정규화(b 파라미터)
기본값: k1=1.2, b=0.75 — 튜닝 시 GET /index/_explain/doc-id로 BM25 점수 분해 확인

경계 조건: Inverted Index는 키워드 정확도에 강하지만 의미 기반 검색에 약함. “강아지”와 “개”는 다른 토큰 → Dense Index(임베딩 벡터 기반)와 하이브리드로 보완.

4. 실무에서 어떻게 쓰이나

백엔드/인프라 실무 사례

DP 활용:

AWS Lambda 함수의 콜드스타트 최소화 위한 배포 스케줄 최적화
CI/CD 파이프라인에서 변경된 모듈만 빌드하는 의존성 캐시 전략
가격 최적화 API: “예산 내 최대 성능의 인스턴스 조합”

Greedy 활용:

Kubernetes 파드 스케줄러: 가장 여유 있는 노드에 우선 배치
로드밸런서의 Least Connections 알고리즘
배치 작업 우선순위 큐: 마감 임박한 작업부터 처리

Divide & Conquer 활용:

대용량 데이터 병렬 처리: 청크로 나누어 Worker Pool 처리 후 합산
Database 파티셔닝: 데이터 범위 분할 후 병렬 쿼리

검색 엔진 기초 활용:

Elasticsearch 쿼리 튜닝: BM25 파라미터 조정으로 검색 품질 향상
로그 분석: 역색인으로 수백만 로그에서 패턴 즉시 검색
추천 기능: 사용자 행동 벡터 코사인 유사도로 유사 사용자 찾기
퍼지 검색: Edit Distance로 오타 허용 검색 구현

5. 내 업무와의 연결고리

BackOps 엔지니어로서 직접 연결되는 시나리오:

시나리오 1: 비용 최적화 API (DP)

요구사항: 월 예산 내에서 최대 처리량을 달성하는 AWS 인스턴스 조합
문제 유형: 0/1 Knapsack → DP 필수
이유: Greedy는 최적해 보장 안 됨

시나리오 2: 작업 스케줄링 (Greedy)

요구사항: 데이터 마이그레이션 작업들을 겹치지 않게 최대한 많이 처리
문제 유형: Activity Selection → Greedy (종료 시간 기준 정렬)
이유: 종료 시간 기준 Greedy가 전역 최적 보장

시나리오 3: Elasticsearch 튜닝

요구사항: 내부 검색 시스템의 검색 정확도 개선
접근: BM25 k1/b 파라미터 조정, Dense/Sparse 하이브리드 검색
관련: Inverted Index 구조 이해 필수

시나리오 4: 중복 레코드 감지 (Edit Distance)

요구사항: 고객 DB에서 유사한 이름/주소 중복 감지
접근: Levenshtein Distance로 유사도 임계값(threshold) 설정
이유: 정확한 매칭은 오타/약자 처리 불가

6. 비슷한 개념과 비교

DP vs Greedy vs D&C vs Backtracking 비교

항목	Dynamic Programming	Greedy	Divide & Conquer	Backtracking
하위 문제 겹침	있음 (핵심)	있을 수 있음	없음	없음
되돌아가기	가능 (테이블 참조)	불가	불가	핵심 (철회 단계)
최적해 보장	항상	조건부	항상 (재귀 정확할 때)	가능한 모든 해
속도	보통 (메모 오버헤드)	빠름	보통~빠름	느림 (지수 복잡도)
대표 문제	Knapsack, LCS	동전 문제, Huffman	Merge Sort, FFT	N-Queens, 순열, 부분집합
구현 복잡도	높음	낮음	중간	중간 (재귀 패턴)
시간 복잡도	O(n²)~O(n×W)	O(n log n)	O(n log n)	O(2^n) ~ O(n!)

언제 무엇을 선택하나

문제를 받으면 다음 순서로 판단:

1. 하위 문제가 겹치는가?
   - YES → DP 고려
   - NO  → D&C 고려

2. 최적해가 반드시 필요한가?
   - YES + 겹침 → DP
   - YES + 안겹침 → D&C
   - 근사해 허용 + 단순함 원함 → Greedy 시도

3. Greedy 적용 전 검증:
   - "탐욕 선택 성질이 성립하는가?" 반례를 직접 찾아보기
   - 반례가 없으면 Greedy, 있으면 DP

6.5. 트러블슈팅

증상 1: DP 구현했는데 시간 초과 또는 스택 오버플로우

증상: 재귀 DP(Memoization)로 구현했는데 입력이 크면 Maximum call stack size exceeded 오류 또는 TLE(Time Limit Exceeded).

원인:

JavaScript 재귀 깊이 한계 (~10,000 ~ 15,000 수준)
n = 100,000 같은 큰 입력에서 Top-Down 재귀는 스택 터짐
memo 체크 전에 무거운 연산을 하고 있거나, memo 키가 객체/배열이라 해시 충돌

해결 방법:

// 문제: 큰 n에서 재귀 스택 오버플로우
function fibRecursive(n, memo = {}) {
  // ← n이 크면 위험
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return (memo[n] = fibRecursive(n - 1, memo) + fibRecursive(n - 2, memo));
}

// 해결: Bottom-Up으로 전환 (반복문 → 스택 사용 안 함)
function fibIterative(n) {
  if (n <= 1) return n;
  let prev = 0,
    curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

증상 2: Greedy로 구현했는데 일부 케이스에서 틀린 답이 나옴

증상: 대부분의 테스트는 통과하는데 엣지 케이스에서 최적해보다 작은 값(최소화 문제면 더 큰 값)이 반환됨. 운영에 배포된 뒤 정산·비용 리포트에서 5~30% 손실로 드러나는 패턴(silent failure).

원인:

해당 문제에 “탐욕 선택 성질”이 성립하지 않는 경우 (0/1 Knapsack, 비표준 동전 체계, Job Scheduling with Deadlines 일부 변형)
정렬 기준이 잘못 설정됨 (예: Activity Selection에서 시작 시간 기준 vs 종료 시간 기준)
균등 분포 input에서는 통과하다가 skewed 분포에서만 suboptimal — unit test가 입력 분포를 커버하지 못함

해결 방법 — 4단계 진단·회복 절차:

# 1단계: brute force baseline과 결과 차이 측정
node -e "
const items = [{w:10,v:60},{w:20,v:100},{w:30,v:120}]; // skewed sample
const cap = 50;
const g = greedyKnapsack(items, cap);
const dp = dpKnapsack(items, cap);
console.log({greedy: g, dp_optimal: dp, gap_pct: ((dp-g)/dp*100).toFixed(1)});
"
# 예상 출력: { greedy: 160, dp_optimal: 220, gap_pct: '27.3' }
# gap_pct > 0  →  탐욕 선택 성질이 깨진 것.  Greedy 폐기 후보.

# 2단계: 반례를 unit test로 박제해 회귀 차단
cat >> test/knapsack.spec.ts <<'EOF'
it('skewed 분포에서 Greedy ≠ DP일 때 알람', () => {
  const items = [{w:10,v:60},{w:20,v:100},{w:30,v:120}];
  expect(dpKnapsack(items, 50)).toBe(220);
});
EOF

# 3단계: 본체 알고리즘 교체 — Greedy O(n log n) → DP O(n×W)
#   본문 3-3-2 패턴 3 (knapsack01 1D DP 코드) 그대로 이식.
#   W가 매우 크면 (W > 10^7) Branch-and-Bound 또는 FPTAS 검토.

# 4단계: 운영 회귀 모니터링 (Datadog/CloudWatch)
#   metric: greedy_vs_dp_gap_pct
#   alarm:  p99 > 1% 5분 지속 시 페이지

판단 기준: 탐욕 선택을 한 뒤 “남은 부분 문제”가 원래 문제와 같은 구조를 유지함을 증명할 수 있어야 Greedy 적용. 증명이 안 되면 DP가 안전 (출처: GfG — Greedy Knapsack vs 0/1 Knapsack).

증상 3: Elasticsearch 검색 결과 순서가 예상과 다름

증상: 분명히 관련성 높은 문서가 뒤에 오고, 관련성 낮은 문서가 상위에 랭크됨.

원인:

BM25의 b 파라미터가 너무 높아 짧은 문서가 불리하게 됨
IDF가 왜곡됨: 샤드별로 문서 수가 달라 IDF 계산 오차 발생
검색어의 동의어/약어가 역색인에 없어서 매칭 누락

해결 방법:

# 1. _explain API로 BM25 점수 분석
GET /my-index/_explain/doc-id
{
  "query": { "match": { "content": "검색어" } }
}

# 예상 출력:
# {
#   "_explanation": {
#     "value": 0.6931,
#     "description": "weight(content:검색어 in 0)",
#     "details": [
#       { "description": "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5))", "value": 0.6931 },
#       { "description": "tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl))", "value": 1.0 }
#     ]
#   }
# }

# 2. 샤드 IDF 문제: search_type=dfs_query_then_fetch 사용
GET /my-index/_search?search_type=dfs_query_then_fetch

# 3. 동의어 필터 추가: index settings의 analyzer에 synonym_filter 설정

증상 5: DP 점화식을 세웠는데 dp 테이블 초기화가 잘못되어 틀린 결과

증상: DP 구현 로직은 맞는 것 같은데, 경계 케이스나 특정 입력에서만 틀린 답이 나온다.

원인:

dp 배열 초기화 값이 틀린 경우 (0으로 초기화해야 할 곳에 다른 값)
기저 사례(base case) 누락 — dp[0], dp[1] 등 초기값 설정 오류
인덱스 오프셋 실수 — 문자열 인덱스는 0-based인데 dp 배열을 1-based로 설계

해결 방법:

// 잘못된 예: LCS 구현에서 인덱스 혼동
function lcsBad(s1, s2) {
  const dp = Array.from(
    { length: s1.length },
    () => new Array(s2.length).fill(0), // ← 크기가 1 작아서 경계 초과
  );
  // dp[i][j]에서 i=s1.length, j=s2.length 접근 시 undefined
}

// 올바른 예: (m+1) × (n+1) 크기로 초기화
function lcsCorrect(s1, s2) {
  const m = s1.length,
    n = s2.length;
  // 빈 문자열 기저 사례를 위해 한 칸씩 더 크게
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // i-1, j-1로 s1/s2 접근
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

디버깅 팁: dp 테이블을 콘솔에 출력해서 손으로 계산한 결과와 비교한다. 소규모 입력(길이 3~4)으로 먼저 검증하고 크기를 늘린다.

증상 6: Greedy로 구현했는데 정렬 기준이 잘못되어 틀린 결과

증상: Activity Selection이나 Job Scheduling 문제에서 Greedy를 적용했는데 최적보다 적은 활동이 선택된다.

원인: 정렬 기준 오류가 가장 흔하다. Activity Selection은 종료 시간 기준으로 정렬해야 하는데 시작 시간으로 정렬하거나, Job Scheduling에서 마감 기한과 처리 시간을 혼동한다.

해결 방법:

// 잘못된 정렬 기준 — 시작 시간 기준
const wrongSort = activities.sort((a, b) => a.start - b.start);
// → 시작이 빠른 활동을 우선하면 긴 활동이 먼저 잡혀 뒤 활동을 모두 막을 수 있음

// 올바른 정렬 기준 — 종료 시간 기준
const correctSort = activities.sort((a, b) => a.end - b.end);
// → 빨리 끝나는 활동을 먼저 선택해야 뒤에 더 많은 활동이 들어올 수 있음

// 반례로 검증:
const test = [
  { name: "A", start: 0, end: 10 }, // 시작 시간 기준 우선
  { name: "B", start: 1, end: 3 },
  { name: "C", start: 4, end: 6 },
];
// 시작 시간 기준: A 선택 → B,C 모두 차단 (1개 선택)
// 종료 시간 기준: B → C 선택 (2개 선택) ← 최적

증상 7: Merge Sort 구현이 작동하지만 원본 배열을 변경하지 않아 혼란

증상: mergeSort(arr) 호출 후 arr이 변경되지 않고 반환값만 정렬됨. 또는 반대로 원본도 같이 변경되어 사이드 이펙트 발생.

원인:

arr.slice()는 새 배열을 반환하므로 원본 보존 (불변성)
인플레이스(in-place) vs 아웃오브플레이스(out-of-place) 구현 혼동

해결 방법:

// 명시적으로 새 배열 반환 (함수형 스타일)
const sorted = mergeSort([...originalArr]); // 원본 유지

// 또는 인플레이스 Quick Sort 사용
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

증상 7: 백트래킹 구현에서 철회(Unchoose) 누락으로 잘못된 결과

증상: 백트래킹으로 순열/조합을 구하는 코드가 일부 결과를 중복으로 반환하거나, 결과 배열이 모두 같은 내용을 가리킨다.

원인 1 — 철회 누락: current.push()로 선택했는데 재귀 후 current.pop()을 하지 않으면 이전 선택이 다음 탐색에도 영향을 준다.

원인 2 — 얕은 복사 누락: result.push(current)로 배열 참조를 저장하면, 이후 current가 변경될 때 결과도 같이 바뀐다.

// 잘못된 예: pop() 누락 + 얕은 복사
function badBacktrack(nums) {
  const result = [];
  function bt(idx, current) {
    if (idx === nums.length) {
      result.push(current); // ❌ 참조 저장! 나중에 current가 변하면 result도 변함
      return;
    }
    current.push(nums[idx]);
    bt(idx + 1, current);
    // ❌ current.pop() 없음! 다음 재귀에서 이전 선택이 남아있음
  }
  bt(0, []);
  return result;
}

// 올바른 예: pop() + 스프레드 복사
function goodBacktrack(nums) {
  const result = [];
  function bt(idx, current) {
    if (idx === nums.length) {
      result.push([...current]); // ✅ 스프레드로 현재 상태의 복사본 저장
      return;
    }
    current.push(nums[idx]); // 1. 선택
    bt(idx + 1, current); // 2. 탐색
    current.pop(); // 3. 철회 ← 반드시 필요!
  }
  bt(0, []);
  return result;
}

console.log(goodBacktrack([1, 2]));
// 예상 출력: [[1, 2]]   (인덱스 순 한 방향 탐색)

디버깅 팁: 백트래킹 버그의 90%는 ① pop() 누락, ② result.push(current) 참조 오류, ③ 인덱스 시작점 혼동 세 가지 중 하나다. 코드 작성 직후 이 세 가지를 체크리스트로 확인한다.

7. 체크리스트

Dynamic Programming

중복 부분 문제가 있는지 확인했는가?
최적 부분 구조가 성립하는지 확인했는가?
Top-Down과 Bottom-Up 중 적합한 것을 선택했는가?
dp 배열의 인덱스와 의미를 명확히 정의했는가?
기저 사례(base case)를 올바르게 초기화했는가?
시간 복잡도가 O(n²) 이상이면 최적화를 검토했는가?

Greedy

탐욕 선택 성질이 이 문제에 성립하는지 반례를 찾아봤는가?
정렬 기준이 올바른가? (예: 종료 시간 vs 시작 시간)
반례가 발견되면 DP로 전환할 준비가 됐는가?

Divide & Conquer

하위 문제들이 서로 겹치지 않는가? (겹치면 DP)
합산(Combine) 단계의 복잡도를 계산했는가?
Master Theorem으로 전체 복잡도를 추산했는가?

Backtracking

“선택 → 탐색 → 철회” 3단계 패턴을 이해하고 구현할 수 있는가?
Pruning(가지치기) 조건을 정확히 설정했는가? (조건 위반 시 즉시 return)
상태를 공유하는 경우 철회(Unchoose) 단계에서 반드시 원상복구하는가?
순열(Permutation) 문제와 조합(Combination) 문제의 코드 차이를 안다
백트래킹 vs DFS의 차이를 설명할 수 있는가?

유사도 메트릭

문자열 비교인지 집합 비교인지 벡터 비교인지 판단했는가?
순서가 중요하면 Edit Distance, 순서 무관이면 Jaccard/Cosine
의미적 유사도가 필요하면 임베딩 벡터 + Cosine

검색 엔진

Inverted Index가 어떻게 구성되는지 설명할 수 있는가?
TF-IDF에서 IDF가 왜 필요한지 설명할 수 있는가?
BM25가 TF-IDF보다 나은 두 가지 이유를 말할 수 있는가?
Dense vs Sparse 검색 중 어느 것이 적합한지 판단할 수 있는가?

8. 핵심 키워드

키워드	한 줄 설명
Overlapping Subproblems	같은 하위 문제가 반복 등장 → DP 적용 조건
Optimal Substructure	전체 최적해가 하위 최적해 조합 → DP/Greedy 조건
Memoization	Top-Down DP. 재귀 + 캐시
Tabulation	Bottom-Up DP. 반복문 + 테이블
Greedy Choice Property	탐욕 선택이 전체 최적에 기여 → Greedy 유효 조건
Backtracking	선택 → 탐색 → 철회 패턴. Pruning으로 탐색 공간 축소
Pruning	백트래킹에서 조건 위반 시 해당 경로 전체를 조기 포기
Master Theorem	T(n) = aT(n/b) + f(n) 형태의 점화식을 O() 로 변환
Inverted Index	단어 → 문서 목록 매핑. 검색 엔진 핵심 자료구조
TF-IDF	단어 빈도 × 역문서 빈도. 검색 관련성 점수
BM25	TF-IDF 개선판. Elasticsearch 기본 스코어링
Jaccard Similarity	집합 교집합/합집합 비율
Cosine Similarity	두 벡터의 방향 유사도 (각도 기반)
Edit Distance	두 문자열 변환 최소 비용 (Levenshtein)
Dense Index	임베딩 벡터 기반 의미 검색
Sparse Index	키워드 역색인 기반 정확 검색

8.5. 추천 리소스

Dynamic Programming

GeeksforGeeks - Tabulation vs Memoization (입문)
- Top-Down/Bottom-Up 차이를 코드와 함께 명확히 설명. 처음 시작할 때 읽기 좋음.
AlgoMap - Dynamic Programming: Memoization & Tabulation (입문~중급)
- 단계별 학습 경로 제공. 실전 문제와 연결되어 학습 흐름이 좋음.

Greedy & 비교

Educative - Greedy vs Dynamic Programming (중급)
- 두 패러다임의 차이를 여러 문제 예시로 비교. 언제 무엇을 쓸지 판단 기준 제시.

검색 엔진

Elastic 공식 블로그 - Practical BM25 (중급)
- Elasticsearch 개발사가 직접 쓴 BM25 설명. k1, b 파라미터 실무 튜닝 포함.
Medium - Understanding Elasticsearch: Inverted Index, TF-IDF (입문)
- 역색인 → TF-IDF → Elasticsearch 연결 흐름을 그림과 함께 설명.

추가 심화 리소스

Baeldung — Tabulation vs. Memoization (중급)
- Top-Down/Bottom-Up의 이론적 배경과 성능 차이를 수학적으로 비교. 어떤 상황에서 뭘 선택할지 명확한 기준 제시.
Programming.Guide — Dynamic Programming vs Memoization vs Tabulation (입문~중급)
- 세 개념의 미묘한 차이를 정리. “DP는 기법이고, Memoization/Tabulation은 구현 방식”이라는 핵심 구분.
Medium — Algorithm Design Paradigms: Divide and Conquer (입문)
- D&C의 3단계를 여러 알고리즘(Merge Sort, Binary Search, Karatsuba 곱셈)으로 시각적 설명.

📚 추천 리소스 (추가)

📖 Greedy vs Dynamic Programming — GeeksforGeeks — DP와 Greedy의 핵심 차이를 비교표와 예제 코드로 설명. 어느 쪽을 선택해야 할지 판단 기준 제시 (입문)
📖 Greedy vs DP — GetSdeReady — 실제 문제 유형별로 DP/Greedy 선택 가이드. 반례 탐색 방법론 포함 (중급)
📖 Algorithm Design Paradigms — OpenStax — 대학 교재 수준의 패러다임 비교. Greedy/D&C/DP를 이론과 예제로 정리 (입문)
📖 Comparison: Greedy, D&C, DP — GeeksforGeeks — 3가지 패러다임을 표 형태로 한눈에 비교. 면접 직전 복습용 (입문)
📖 Dynamic Programming — AlgoMap — Memoization과 Tabulation을 단계별로 배우는 학습 경로. 실전 문제와 연결 (입문~중급)
📖 Backtracking Algorithms — FreeCodeCamp — N-Queens로 백트래킹 핵심 아이디어(선택/탐색/철회)를 직관적으로 설명 (입문)
📖 N-Queen Problem — GeeksforGeeks — 백트래킹 Pruning 효과와 N-Queens 단계별 풀이. 인터뷰 단골 문제 (입문~중급)

9. 직접 확인해보기

DP 성능 차이 체감

// 재귀(지수 복잡도) vs DP(선형 복잡도) 속도 비교
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

function fibDP(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return (memo[n] = fibDP(n - 1, memo) + fibDP(n - 2, memo));
}

// 속도 테스트
console.time("naive fib(40)");
console.log(fibNaive(40));
console.timeEnd("naive fib(40)");

console.time("dp fib(40)");
console.log(fibDP(40));
console.timeEnd("dp fib(40)");

예상 출력:

102334155
naive fib(40): ~800ms  ← 약 2^40 연산
102334155
dp fib(40): ~0.1ms    ← 40번 연산

Greedy 반례 확인

function greedyCoin(amount, coins) {
  const sorted = [...coins].sort((a, b) => b - a);
  const result = [];
  for (const coin of sorted) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return result;
}

// Greedy가 실패하는 케이스
console.log("Greedy [4,3,1] → 6:", greedyCoin(6, [4, 3, 1])); // [4,1,1] = 3개
// 최적은 [3,3] = 2개

예상 출력:

Greedy [4,3,1] → 6: [ 4, 1, 1 ]

Elasticsearch BM25 점수 확인 (실제 명령어)

# Elasticsearch 실행 중일 때 특정 문서의 스코어 계산 과정 확인
curl -X GET "localhost:9200/my-index/_explain/1?pretty" \
  -H "Content-Type: application/json" \
  -d '{ "query": { "match": { "content": "nodejs" } } }'

예상 출력 (요약):

{
  "_explanation": {
    "value": 0.6931471,
    "description": "weight(content:nodejs in 0) [PerFieldSimilarity], result of:",
    "details": [
      { "description": "idf, computed as ...", "value": 0.6931471 },
      { "description": "tf, computed as ...", "value": 1.0 }
    ]
  }
}

Edit Distance 맞춤법 교정 시뮬레이션

function editDistance(s1, s2) {
  const m = s1.length,
    n = s2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
  );
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] =
        s1[i - 1] === s2[j - 1]
          ? dp[i - 1][j - 1]
          : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
  return dp[m][n];
}

const typo = "elasticserch";
const dictionary = [
  "elasticsearch",
  "elastic",
  "elastic search",
  "elasticache",
];
const suggestions = dictionary
  .map((word) => ({ word, distance: editDistance(typo, word) }))
  .sort((a, b) => a.distance - b.distance);

console.log(`"${typo}" 교정 후보:`);
suggestions.forEach(({ word, distance }) =>
  console.log(`  ${word} (편집거리: ${distance})`),
);

예상 출력:

"elasticserch" 교정 후보:
  elasticsearch (편집거리: 2)
  elastic search (편집거리: 3)
  elasticache (편집거리: 4)
  elastic (편집거리: 5)

백트래킹 직접 확인 — 부분집합(Subset) 생성

// 모든 부분집합 생성 — 백트래킹의 조합 패턴
function subsets(nums) {
  const result = [];

  function backtrack(start, current) {
    // 매 단계의 현재 상태를 결과에 추가 (부분집합은 빈 집합 포함)
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]); // 1. 선택
      backtrack(i + 1, current); // 2. 탐색 (i+1로 중복 방지)
      current.pop(); // 3. 철회
    }
  }

  backtrack(0, []);
  return result;
}

console.log(subsets([1, 2, 3]));

예상 출력:

[
  [],       ← 빈 집합
  [1],
  [1, 2],
  [1, 2, 3],
  [1, 3],
  [2],
  [2, 3],
  [3]
]

순열 (n=3): 6개 = 3! 결과, 부분집합 (n=3): 8개 = 2^3 결과 — 시간복잡도가 지수적임을 직접 확인할 수 있다.

10. 한 줄 요약

DP는 “기억하며 최적화”, Greedy는 “지금 최선만 보고 전진”, D&C는 “쪼개고 풀고 합친다”, Backtracking은 “선택하고 탐색하고 되돌린다” — 네 패러다임을 구분할 수 있으면 어떤 알고리즘 문제든 첫 접근법을 잡을 수 있다. 검색 엔진에서는 이 모두가 실제로 쓰인다 (BM25 = TF-IDF 최적화, 역색인 = 해시맵 D&C 변형).