DP-Dynamic Programming(동적 계획법)

 

 

 

DP

Dynamic Programming(동적 계획법)이란, 큰 문제를 작은 문제로 나누고, 그 결과를 저장해 두었다가 재사용하는 방법 입니다.

 

 

핵심 키워드는 딱 두 가지입니다.

1. 중복되는 부분 문제 (Overlapping Subproblems)
2. 최적 부분 구조 (Optimal Substructure)

즉,

• 같은 계산을 여러 번 하게 되고
• 작은 문제의 최적해가 큰 문제의 최적해로 이어질 때

DP를 사용할 수 있습니다.

 

---

DP를 써야 하는 문제의 특징

다음과 같은 신호가 보이면 DP를 의심해 보셔야 합니다.

• 최대 / 최소 / 경우의 수
• ~까지의 최적값
• 앞에서부터 누적
• 선택하거나 / 선택하지 않거나
• 이전 상태에 따라 현재 상태가 결정됨

예를 들면:

• 최대 이익
• 최소 비용
• 가능한 경우의 수
• 최장 증가 수열
• 최단 경로

 

 

---

1차원 DP 예제

문제: 계단 오르기

계단이 n칸 있습니다.
한 번에 1칸 또는 2칸씩 오를 수 있을 때,
꼭대기까지 올라가는 방법의 수를 구하세요.

문제 분석

• 마지막 칸에 도달하는 방법은?
  • 바로 이전 칸에서 1칸 올라오거나
  • 두 칸 아래에서 2칸 올라오는 경우

즉,

dp[n] = dp[n-1] + dp[n-2]

DP 정의

• dp[i] = i번째 칸에 도달하는 방법의 수

초기값

• dp[1] = 1
• dp[2] = 2

풀이

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

  const dp: number[] = new Array(n + 1).fill(0);
  dp[1] = 1;
  dp[2] = 2;

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

  return dp[n];
}

핵심 포인트

• dp 배열은 의미가 명확해야 합니다
• 점화식이 자연스럽게 떠올라야 합니다

 

---

다차원 DP 예제

문제: 가장 긴 공통 부분 수열 (LCS)

두 문자열 text1, text2가 주어질 때,
가장 긴 공통 부분 수열의 길이를 구하세요.

예시:

text1 = "abcde"
text2 = "ace"
결과 = 3  // "ace"

문제 분석

• 두 문자를 비교하면서
• 이전 상태들의 결과를 참고해야 함
• 문자열 두 개 → 2차원 DP

DP 정의

• dp[i][j]
  • text1의 i번째까지
  • text2의 j번째까지
  • 고려했을 때의 LCS 길이

점화식

• 문자가 같을 때

dp[i][j] = dp[i-1][j-1] + 1

• 문자가 다를 때

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

TypeScript 풀이

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;

  const dp: number[][] = 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 (text1[i - 1] === text2[j - 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];
}

핵심 포인트

• dp의 의미를 문장으로 설명할 수 있어야 합니다
• 인덱스와 문자열 인덱스 차이에 주의하세요

 

---

DP 접근 사고법

1. dp가 무엇을 의미하는가? (한 문장으로 정의)
2. 현재 상태는 어떤 이전 상태에서 오는가?
3. 초기값은 무엇인가?
4. 배열 크기와 차원은 적절한가?