다이나믹 프로그래밍

공부용·2025년 4월 8일
알고리즘
post-thumbnail

그 DP가 아니다

동적 계획법 (DP)

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써
최종적으로 복잡한 문제의 답을 구하는 방법

다음과 같은 조건에서 DP를 적용할 수 있다.

  • Optimal substructure (최적 부분 구조)
    -> 큰 문제의 최적해가 작은 문제들의 최적해로부터 만들어짐

  • Overlapping subproblems (중복되는 하위 문제)
    -> 작은 문제들이 여러 경로에서 반복적으로 등장

접근 방식

특히 문제를 보고 dp를 적용할 수 있을지 예측하는 것은 쉽지 않다.

그래서 다음과 같은 규칙을 가지고 dp를 적용할 수 있을 지 가늠해본다.

  1. 부분 문제로 나눌 수 있는가?
    -> 큰 문제를 작은 단위로 쪼갤 수 있을 때

  2. 같은 하위 문제가 반복되는가?
    -> fib(3) 처럼 같은 걸 여러번 구하진 않는지

  3. 부분 문제의 해를 저장하고 재활용할 수 있는가?
    -> 이전 계산을 활용해서 다음 답을 만들 수 있는지

이 단계 까지 거치게 된다면 커다란 문제를 재귀 형식을 작은 문제로 분해할 수 있게 된다.

DP 해결 절차

1단계: 완전 탐색으로 먼저 생각한다.

  • 문제를 재귀적 사고로 단순화하면서 쪼갠다.
  • 선택 / 비선택 / 가지치기를 통해서 문제에 접근해 나가는 것이다.
int lcs(i, j) {
    if (str1[i] == str2[j]) return lcs(i-1, j-1) + 1;
    else return max(lcs(i-1, j), lcs(i, j-1));
}

흔한 재귀 문제인 lcs를 예시로 가져왔다.

lcs(i, j)는 str1[0..i]와 str2[0..j] 사이의 LCS 길이를 의미한다.
완전 탐색은 O(2^n)으로 모든 경우를 재귀 호출을 통해서 구하기 때문에 시간 초과가 나게 된다.

2단계: 중복되는 하위 문제를 찾는다.

  • 재귀 호출 트리 구조에서 같은 호출이 반복되는지 찾는다
  • lcs의 경우 한번 발생한 재귀
    호출과 똑같은 연산이 발생하는 것을 알 수 있다.

3단계: 메모이제이션으로 중복 제거

  • cache[i][j]와 같은 테이블로 결과를 저장한다.
  • 이미 lcs의 경우 cache[i][j]에 이전에 계산한 값이 있다면 배열에서 가져와서 계산을 이어나간다.

예제

전형적인 dp의 예시를 가져왔다. 각 문제에 위에 설명한 나만의 방식을 적용하여 접근해본다.

피보나치 수2

2748번

피보나치 수는 0과 1로 시작하여, 2번째 수부터는 바로 앞 두 피보나치 수의 합이 된다.

1. 완전 탐색으로 접근
가장 먼저 완전탐색 재귀 함수를 생각해보자

// n번 째 피보나치 수를 찾는 함수
long fib(int n) {
	if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

n번째 피보나치 수를 찾는 방법은 (n-1)번째 피보나치 수와 (n-2)번째 피보나치 수를 찾는 것이다.

2. 중복되는 부분 찾기

하지만 이 경우

fib(5) -> fib(4) + fib(3)
fib(4) -> fib(3) + fib(2)
fib(3) -> fib(2) + fib(1)
fib(2) -> 1
fib(1) -> 1

중복 호출되는 함수가 발생하게 된다.
-> fib(n)을 구할 때 fib(n - 1)과 fib(n - 2)는 중복적으로 계속 호출된다
-> 따라서 이 값들을 메모이제이션으로 저장할 수 있다.

3. 메모이제이션 적용

static long fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memo[n] != 0) return memo[n];

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

cache라는 배열을 도입하여 이전 호출된 함수의 결과를 저장하게 한다.

01 타일

1904번

정수 n이 주어졌을 때 길이가 n인 2진 문자열 중에서 1과 00만 사용해서 만들 수 있는 문자열의 개수를 구하라.

1. 완전 탐색으로 접근

  • 길이가 n인 문자열을 만들려고 할 때
  • 만들 수 있는 구선은 "1" 또는 "00"두 가지 뿐이다.

문자열을 만들 때 칸을 채운다고 생각하자.
예를 들어, n = 4 이면 4칸짜리 블록을 채워야한다.

앞에서부터 1칸 혹은 2칸을 차지하며 나아간다면

현재 위치에서
-> 1칸을 채우는 경우 (1)
-> 2칸을 채우는 경우 (00)
이 두 가지 경우를 각각 재귀적으로 시도해본다는 것이다.

countWays(n - 1) -> 바로 앞자리가 1
countWays(n - 2) -> 바로 앞자리가 00

이런 방법이 재귀적으로 이루어 진다.

// n번째 수열의 경우의 수
int countWays(int n) {
    if (n == 0) return 1; // 길이 딱 맞게 끝냄
    if (n < 0) return 0;  // 길이 초과 → 잘못된 경우

    return countWays(n - 1) + countWays(n - 2);
}

2. 중복되는 부분 찾기
피보나치 수열과 같은 재귀 함수가 만들어졌다.
결국 곂치는 부분이 똑같이 생긴다는 것이다.

3. 메모이제이션 적용

static int tile(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        if (memo[n] != 0) return memo[n];

        memo[n] = (tile(n - 1) + tile(n - 2)) % MOD;
        return memo[n];
}

동전

9084

여러 종류의 동전이 주어졌을 때 해당 동전들로 금액 M을 만드는 경우의 수를 구하라.

1. 완전탐색으로 문제 해결
coins = [1, 2, 5], target = 10을 가정한다.
다음과 같은 선택을 계속 할 수 있다.

  • 현재 금액에서 1원을 사용할 것인가?
  • 2원을 사용할 것인가?
  • 5원을 사용할 것인가?
int countWays(int idx, int sum) {
    if (sum > target) return 0;
    if (sum == target) return 1;
    if (idx == coins.length) return 0;

    // 1. 현재 코인을 사용하지 않는 경우
    int without = countWays(idx + 1, sum);

    // 2. 현재 코인을 사용하는 경우 (중복 사용 가능 → idx는 그대로)
    int with = countWays(idx, sum + coins[idx]);

    return with + without;
}

2. 중복되는 부분 찾기
같은 idx와 sum 조합이 여러 번 등장한다.
-> 중복 호출
-> cache[idx][sum]식으로 메모이제이션해서 최적화 한다.

3. 메모이제이션 적용

public static int countWays(int idx, int sum) {
        if (sum > target) return 0;
        if (sum == target) return 1;
        if (idx == n) return 0;

        if (memo[idx][sum] != -1) return memo[idx][sum];

        // 현재 동전을 쓰지 않는 경우 + 쓰는 경우
        memo[idx][sum] = countWays(idx + 1, sum) + countWays(idx, sum + coins[idx]);
        
        return memo[idx][sum];
    }

LCS

9251

두 분자열 str1, str2가 주어졌을 때,두 문자열의 공통으로 존재하는 부분 수열 중 가장 긴 길이를 구한다.

1. 완전탐색 접근

  • str1[i] == str2[j] -> 두 문자를 LCS에 포함시키고, 다음 문자로 이동 (i+1, j+1)
  • 일치하지 않는 경우 하나는 버리고 다음 문자로 이동
    -> max(LCS(i+1, j), LCS(i, j+1))
int lcs(int i, int j) {
    if (i == str1.length || j == str2.length) return 0;

    if (str1.charAt(i) == str2.charAt(j))
        return 1 + lcs(i + 1, j + 1);
    else
        return Math.max(lcs(i + 1, j), lcs(i, j + 1));
}

2. 중복 확인
재귀 호출 트리를 그려보면 같은 lcs(i, j) 호출이 여러 경로로 반복해서 호출된다.

3. 메모이제이션 적용

public static int lcs(int i, int j) {
        if (i == str1.length() || j == str2.length()) return 0;

        if (memo[i][j] != -1) return memo[i][j];

        if (str1.charAt(i) == str2.charAt(j)) {
            memo[i][j] = 1 + lcs(i + 1, j + 1);
        } else {
            memo[i][j] = Math.max(lcs(i + 1, j), lcs(i, j + 1));
        }

        return memo[i][j];
}

행렬 곱셈 순서

11049

1. 완전 탐색
행렬이 4개까지 있다면, 문제를 재귀적으로 분할 할 수 있다.

minCost(1, 4) =  
    min(
        minCost(1,1) + minCost(2,4) + cost(1,1,4),
        minCost(1,2) + minCost(3,4) + cost(1,2,4),
        minCost(1,3) + minCost(4,4) + cost(1,3,4)
    )

이 아이디어를 재귀로 구현한다면

int minCost(i, j) {
    if (i == j) return 0;  // 한 개짜리 행렬은 계산 필요 없음

    int res = INF;
    for (int k = i; k < j; k++) {
        int left = minCost(i, k);         // 왼쪽 부분
        int right = minCost(k+1, j);      // 오른쪽 부분
        int cost = dims[i] * dims[k+1] * dims[j+1];  // i~k와 k+1~j 곱하기 비용

        res = Math.min(res, left + right + cost);
    }
    return res;
}

2. 중복 확인

행렬 곱셈을 진행할 때 쪼개지는 곱셈 순서에 반복 호출되는 함수가 있다.

3. 메모이제이션 적용

int minCost(int i, int j) {
    if (i == j) return 0; // 하나의 행렬은 곱할 필요 없음
    if (dp[i][j] != 0) return dp[i][j];

    dp[i][j] = INF;

    for (int k = i; k < j; k++) {
        int cost = minCost(i, k) + minCost(k + 1, j)
                   + (r[i] * c[k] * c[j]);  // 곱셈 비용 계산
        dp[i][j] = Math.min(dp[i][j], cost);
    }
    return dp[i][j];
}

평범한 배낭 (0/1 knapsack)

12865

n개의 물건과 각 물건 i의 무게 w, 가치 v가 주어지고 가방 용량이 C일 때, 가방에 담을 최대 값을 찾는 문제 (각 문제는 1개만 존재한다.)

1. 완전 탐색

해당 인덱스의 물건을 고려한 경우와
해당 인덱스의 물건을 고려하지 않은 경우 중 작은 값을 골라가면 된다.

static int sol(int index, int freeWeight) {
    int ret = sol(index + 1, freeWeight);
    // 해당 인덱스의 물건을 고려하지 않은 경우와
    // 해당 인덱스의 물건을 고려한 경우 중 작은 값
    if (freeWeight >= items[index].weight) {
        ret = Math.max(ret, sol(index + 1, freeWeight - items[index].weight) + items[index]value);
    }
    return ret;
}

2. 중복되는 부분 찾기
그래프 상으로 나오지 않았지만 값이 커지는 경우에 호출되어가면서 중복되는 함수 호출이 생기게 된다.

3. 메모이제이션 적용

이를 cache[index][freeWeight] 배열로 값들을 저장해 나간다면 다음 그래프와 같이 배열 접근이 가능하다.

static int sol(int index, int freeWeight) {
    if (index == ItemSize) {
        return 0;
    }
    
    if (cache[index][freeWeight] != -1) {
        return cache[index][freeWeight];
    }
    // 해당 인덱스 물건 선택 안함
    int ret = sol(index + 1, freeWeight);
    
    if (freeWeight >= items[index].weight) {
        ret = Math.max(ret, sol(index + 1, freeWeight - items[index].weight) + items[index]value);
    }
    cache[index][freeWeight] = ret;
    
    return ret;
}

결론

DP를 처음 바텀 업 방식으로 풀 때 단순히 이전 값을 저장하는 테크닉으로 생각하고 문제에 적용했다.
그러다 보니 문제를 작은 부분 문제로 나누는 본질을 놓치지 않았나 싶다.

위의 문제를 풀 때 구조가 거의 비슷한 것을 알 수 있다. 이는 DFS(완전탐색)으로 시작해서 곂치는 부분만 메모이제이션으로 최적화하는 방법이었다.

DP 더 이상 무섭지 않다.

레퍼런스

https://medium.com/quick-code/leetcode-casual-to-competitors-guide-to-dfs-memoization-3667cdbabf68

https://stackoverflow.com/questions/54016101/how-to-solve-algorithm-problems-in-both-dfs-and-dp

https://codeforces.com/blog/entry/43256

https://algo.monster/problems/dynamic_programming_intro

https://www.interviewcake.com/concept/java/memoization

profile
공부용
공부 내용을 가볍게 적어놓는 블로그.
이전 포스트

NULL

다음 포스트

intrusive - structures

2개의 댓글

comment-user-thumbnail
김욤쓰
2025년 4월 8일

갓성광님🔥

1개의 답글