DP(Dynamic Programming)

DP의 개념을 알아보면 다음과 같다.

동적 계획법이란?

"복잡한 문제를 작은 문제로 나누고, 그 결과를 저장해서 중복 계산을 피하는 알고리즘 설계 기법"

 

핵심은 이거다

 

• 문제를 잘게 쪼갠다.
• 중복되는 계산은 한 번만 한다.

 

DP는 재귀와 비슷한 개념이지만, 이미 계산한 결과를 메모해 두고 재사용하는 점에서 효율성 면에서 큰 차이가 있다.

 

 

DP를 적용할 수 있는 조건

DP는 아무 문제에나 적용되는 것이 아니다.

 

1. 겹치는 부분 문제 (Overlapping Subproblems)
   큰 문제를 해결하는 과정에서 같은 작은 문제가 반복해서 나타나는 경우

예시: 피보나치 수열

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

만약 fib(5)를 호출하면 호출 트리는 다음과 같다:

          fib(5)
         /      \
     fib(4)    fib(3)
     /    \     /    \
 fib(3) fib(2) fib(2) fib(1)

➡️ 여기서 fib(3)과 fib(2)가 여러 번 중복해서 계산되는 걸 볼 수 있다.
이게 바로 겹치는 부분 문제이다.

 

2. 최적 부분 구조 (Optimal Substructure)
작은 문제들의 최적해를 조합해 큰 문제의 최적해를 구할 수 있는 경우

예시: 최단 경로 문제 (계단 오르기)

• 문제: 각 계단에 점수가 있고, 한 칸 또는 두 칸씩 올라갈 수 있다. 가장 높은 점수를 얻으면서 꼭대기에 도착하려면?

// 각 계단에 해당하는 점수
const stairs = [10, 20, 15, 25, 10, 20];

// dp[i] = i번째 계단까지 올라섰을 때의 최대 점수
const dp = new Array(stairs.length).fill(0);

dp[0] = stairs[0];
dp[1] = stairs[0] + stairs[1];
dp[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

for (let i = 3; i < stairs.length; i++) {
  dp[i] = Math.max(dp[i - 2], dp[i - 3] + stairs[i - 1]) + stairs[i];
}

console.log(dp[stairs.length - 1]); // 최종 최대 점수

여기서 이전 계단까지의 최적 점수를 이용해 현재 계단의 점수를 계산한다.
➡️ 즉, 작은 문제의 최적해를 조합해서 큰 문제의 해를 구하는 구조이다.

이게 바로 최적 부분 구조!

 

 

• 반복되는 계산이 있는가?
  → 겹치는 부분 문제
• 작은 문제를 풀어 결과를 합쳐서 큰 문제를 풀 수 있는가?
  → 최적 부분 구조

두 조건이 모두 만족되면, DP를 적용할 수 있는 문제

 

 

 

DP의 대표적인 방식 두 가지

1. Top-Down (재귀 + 메모이제이션)

• 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출한다
• 계산한 결과는 배열이나 객체에 저장해 두고, 같은 요청이 들어오면 바로 반환한다

2. Bottom-Up (반복문 + 테이블)

• 가장 작은 문제부터 차례대로 해결하면서 큰 문제를 해결한다
• 주로 for문을 사용해 구현하며, 재귀 호출이 없기 때문에 속도가 빠르다.

 

예제: 피보나치수열 (Fibonacci)

피보나치수열은 대표적인 DP 예제로 사용된다.

• 수열: 0, 1, 1, 2, 3, 5, 8, 13,...
• 점화식: f(n) = f(n-1) + f(n-2)

 

Top-Down 방식 (재귀 + 메모이제이션)

메모이제이션

이미 계산한 값을 저장해 두고, 다음에 같은 계산을 반복하지 않도록 하는 기법

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(10)); // 55

장점: 간결하고 이해하기 쉬움
단점: 재귀 호출이 깊어지면 스택 오버플로우 위험

Bottom-Up 방식 (반복문 + 테이블)

function fib(n) {
  if (n <= 1) return n;

  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fib(10)); // 55

장점: 성능이 좋고, 스택 오버플로우 걱정 없음
단점: 약간 더 코드가 길어짐

 

오버플로우 때문에 바텀업 방식을 더 사용하는 게 좋을 것 같다.

---

 

마무리: 언제 DP를 떠올릴까?

• 어떤 문제를 푸는데 비슷한 연산을 여러 번 하고 있다면?
• 이전 결과를 저장해서 다시 쓰면 빠를 것 같다면?

---

 

DP vs 세그먼트 트리 – 무슨 차이일까?

 차이 요약

동적 계획법 (DP)  세그먼트 트리 (Segment Tree)

 

사용 목적	중복된 계산을 줄이기 위한 최적화	구간 쿼리(query)와 업데이트 처리
문제 유형	최댓값, 최솟값, 최단경로, 경로 개수 등	특정 범위의 합, 최댓값/최솟값 등 빠르게 구하기
접근 방식	작은 문제부터 큰 문제로 확장 (Bottom-Up or Top-Down)	트리를 이용한 분할 정복
데이터 변화	대부분 정적(변하지 않음)	동적 데이터 처리에 유리
시간복잡도	보통 O(N) 또는 O(N^2)	쿼리 & 업데이트 O(log N)

 

---

쉽게 이해하기

• DP는 **‘문제 전체를 한 번에 풀고 저장’**해서 빠르게 처리하는 방식.
• 세그먼트 트리는 **‘특정 범위만 빠르게 계산’**하고 싶을 때 사용

---

 예제 비교 – 배열의 구간 합을 구하는 문제

 DP 방식 (누적합, Prefix Sum)

const arr = [1, 2, 3, 4, 5];
const prefixSum = [0];

for (let i = 0; i < arr.length; i++) {
  prefixSum[i + 1] = prefixSum[i] + arr[i];
}

// 구간 [1, 3]의 합: 2 + 3 + 4 = 9
console.log(prefixSum[4] - prefixSum[1]); // 9

 

• 장점: 매우 빠름 (O(1) 쿼리)
• 단점: 배열이 바뀌면 prefixSum을 다시 계산해야 함

 

세그먼트 트리 방식

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(this.n * 4);
    this.build(arr, 1, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, node * 2, start, mid);
      this.build(arr, node * 2 + 1, mid + 1, end);
      this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
    }
  }

  query(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];

    const mid = Math.floor((start + end) / 2);
    return this.query(node * 2, start, mid, l, r)
         + this.query(node * 2 + 1, mid + 1, end, l, r);
  }
}

const arr = [1, 2, 3, 4, 5];
const seg = new SegmentTree(arr);

// 구간 [1, 3]의 합
console.log(seg.query(1, 0, arr.length - 1, 1, 3)); // 9

 

 

• 장점: 데이터가 바뀌어도 O(log N) 시간으로 업데이트 & 쿼리 가능
• 단점: 구현이 복잡하고, 메모리 사용량이 많음

---

정리하자면…

• DP는 한 번에 전체 데이터를 처리해서 빠르게 답을 도출하는 방식이고,
• 세그먼트 트리는 부분 구간만 빠르게 처리하거나 데이터가 자주 바뀌는 상황에 강하다.

결론

데이터가 바뀌지 않음 + 전체적으로 처리 가능	✅ DP
범위 쿼리 + 데이터가 자주 바뀜	✅ 세그먼트 트리
단순한 문제 (피보나치, 최댓값 경로 등)	✅ DP
쿼리 & 업데이트가 반복되는 문제 (ex. 백준 2042)	✅ 세그먼트 트리