[Java] 알고리즘 설계 기법: 최적화 문제를 위한 DP

 다이나믹 프로그래밍은 시간 단축을 위한 알고리즘이다. 탑다운 방식과 바텀업 방식이 존재하며, 결국 핵심은 계산한 값을 저장하고 재활용한다는 것이다.

---

동적 계획법(DP)를 구현해 보자.

 

탑다운: 메모이제이션

 

 이름에서 알 수 있듯 큰 문제부터 작은 문제로 해결하는 방식이다.

 

✅ 재귀구조가 직관적이고 구현이 간단하다.

✅ 재귀호출이 깊어질수록 스택 오버플로우 가능성이 있다.

public class Fibonacci {
    static int[] dp;

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        
        if (dp[n] != -1) return dp[n]; // 계산된 값이 있으면 바로 반환

        dp[n] = fibonacci(n - 1) + fibonacci(n - 2); // 계산된 값이 없으면 재귀호출
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        dp = new int[n + 1];
        Arrays.fill(dp, -1); // 초기화 (-1은 계산되지 않은 값)
        System.out.println(fibonacci(n));
    }
}

---

바텀업: 터뷸레이션

 

 이름에서 알 수 있듯 작은 문제부터 큰 문제로 해결하는 방식이다.

 

✅ 스택 오버플로우 위험이 없으며 모든 값에 쉽게 접근할 수 있다.

✅ 반복문을 통해 DP 테이블을 모두 저장해야 하므로, 구현이 복잡할 수 있다.

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        // 하나씩 DP 테이블을 채워나감
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibonacci(n));
    }
}

---

BOJ 2579

https://www.acmicpc.net/problem/2579

백준 2579번 계단 오르기 문제를 두 가지 방식으로 구현해 보자.

 

        ▼ 재귀를 통한 탑다운 방식 ▼        

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Integer[] dp;
    static int[] values;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        dp = new Integer[n + 1];
        values = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            values[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        dp[0] = 0;
        dp[1] = values[1];
        if (n >= 2) {
            dp[2] = values[1] + values[2];
        }

        System.out.println(find(n));
    }

    private static int find(int n) {
        if (dp[n] == null) {
            dp[n] = Math.max(dp[i - 2] + values[i], dp[i - 3] + values[i - 1] + values[i]);
        }
        return dp[n];
    }
}

 

        ▼ 반복문을 통한 바텀업 방식 ▼        

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] values = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            values[i] = Integer.parseInt(br.readLine());
        }
        br.close()

        int[] dp = new int[n + 1];
        
        dp[1] = values[1];
        if (n >= 2) {
            dp[2] = values[1] + values[2];
        }

        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 2] + values[i], dp[i - 3] + values[i - 1] + values[i]);
        }

        System.out.println(dp[n]);
    }
}

---

추가 설명

 

 본 문제에는 세 가지 규칙이 존재한다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 일단 마지막 도착 계단은 반드시 밟아야 하므로, 어떤 방식으로 구현하든 values[n]을 깔고 생각해야 한다. 그렇다면 두 가지 케이스를 생각해 볼 수 있다. (계단은 한 계단씩, 혹은 두 계산씩 오를 수 있기 때문에)

 

▷ 도착 계단의 직전 계단을 밟고 올라왔다.

▷ 도착 계단의 직전 계단을 밟지 않고 올라왔다.

 

 여기서 우리가 추가로 고민해야 할 부분은 직전 계단을 밟고 올라온 경우다. 왜냐하면 연속된 세 개의 계단을 모두 밟아서는 안 된다는 조건이 존재하기 때문이다. 직전 계단을 밟고 왔다고 함은, 도착 계단의 전전 계단은 밟지 않았다는 말이다. (도착 계단이 n이라면, 직전 계단은 n-1, 전전 계단은 n-2)

 

 두 케이스를 식으로 표현하면 이렇다.

 

▷ 도착 계단의 직전 계단을 밟고 올라왔다.

→ 도착 계단(o) + 직전 계단(o) + 전전 계단(x) + 전전전 계단 기준 최대 점수(o) = 도착 계단 기준 최대 점수

→ values[n] + values[n-1] + dp[n-3] = dp[n]

 

▷ 도착 계단의 직전 계단을 밟지 않고 올라왔다.

→ 도착 계단(o) + 직전 계단(x) + 전전 계단 기준 최대 점수(o) = 도착 계단 기준 최대 점수

→values[n] + dp[n-2] = dp[n]

 

 두 케이스 중 더 큰 값이 나오는 경우를 택하면 되므로 Math.max()로 묶어준다.