[알고리즘] Java로 배우는 Dynamic Programming(동적 계획법) - feat.백준(계단 오르기)

Dynamic Programming(동적 계획법)

DP(동적 계획법)는 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용해 효율적으로 값을 구하는 알고리즘 설계 기법이다. 즉, 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 의미한다.

DP 구현 방식은 4가지가 있다.

메모이제이션(memoization) 방법: 모든 작은 문제들을 한 번만 계산해서 DP에 저장하며, 저장한 값을 재사용 하는 방법
타뷸레이션(Tabulation) 방법: 작은 문제부터 순차적으로 계산하며 상위로 올라가는 방법
탑 다운: 큰 문제에서 작은 하위 문제들을 확인해가며 진행하는 방법
바텀 업: = 타뷸레이션

동적 계획법은 분할 정복과 비슷해보이지만 차이점이 있다.

분할 정복의 경우 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 사용되고,
동적 계획법은 분할된 하위 문제가 중복이 일어나는 경우에 사용된다.

아래 백준 문제는 계단을 밟아 올라가는 과정에서 가능한 최댓값을 구하기 위해 이전에 계산 된 결과를 활용(메모이제이션 방법)하여 풀 수 있다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] score = new int[num + 1];
        int[] dp = new int[num + 1];

        for (int i = 1; i <= num; i++) {
            score[i] = sc.nextInt();
        }

        dp[1] = score[1];

        if (num > 1) {
            dp[2] = score[1] + score[2];
        }
        for (int i = 3; i <= num; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i];
        }
        System.out.println(dp[num]);
    }
}

int[] dp = new int[num + 1];  // 최댓값을 저장할 dp 배열 (1번부터 num번까지 사용)

dp[] 배열은 각 계단까지 올라갈 때 얻을 수 있는 최대값을 저장할 배열이다.

dp[i]는 i번째 계단에 도달했을 때의 최댓값을 나타낸다.

dp[1] = score[1];  // 첫 번째 계단은 반드시 밟으므로 dp[1] = score[1]
if (num > 1) {
    dp[2] = score[1] + score[2];  // 두 번째 계단까지 올라가는 최댓값은 첫 번째 계단과 두 번째 계단을 순서대로 밟는 것
}

첫번째 계단은 반드시 밟아야 하므로 dp[1]은 score[1]의 값으로 초기화한다.

두 번째 계단까지 올라가는 경우, 첫 번째 계단과 두 번째 계단을 차례로 밟을 수 있으므로 dp[2] = score[1] + score[2]로 초기화한다. 이 때, 계단의 수가 1일 경우 두 번째 계단은 존재하지 않기 때문에 num > 1 조건문을 통해 예외처리를 했다.

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

세 번째 계단부터 마지막 계단까지 올라가는 최댓값은 두 가지 방법을 고려해야 한다.

i-2번째 계단을 밟고 한 계단 건너 뛰기 : 이 경우 dp[i-2]에 score[i]를 더한 값이 된다.
i-3번째 계단을 밟고, i-1번째 계단과 i번째 계단을 차례로 밟기 : 이 경우는 dp[i-3] + score[i-1] + score[i]가 된다.

1번과 2번 둘 중 더 큰 값을 저장하여 dp[i]에 저장한다.

마지막 계단에 도달했을 때 얻을 수 있는 최댓값은 dp[num]에 저장되어 있으므로 dp[num] 값을 출력한다.

저작자표시 비영리 변경금지

Dynamic Programming(동적 계획법)

티스토리툴바