[알고리즘] Dynamic Programming(동적 계획법)

 

동적 프로그래밍 (DP) 란?

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

큰 문제를 작은 여러 개의 문제로 쪼개서 푸는데, 겹치는 부분이 있으면 한번 풀었던 답을 잘 저장해뒀다가 나중에 다시 계산하지 않고 재활용한다. 

결정을 내리기 전에 작은 문제들을 먼저 해결하고, 그 결과를 바탕으로 최적의 선택을 하기 때문에

상향식 접근 방식 (bottom-up) 접근 방식이라고도 불린다. 

 

DP 기법을 적용시키기 위해

 

1. 중복되는 부분 문제

• 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

2. 최적 부분 구조 

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다.

 

 

Memoization

 

memoization은 동적 프로그래밍 기법 중 하나로, 함수의 실행 결과를 저장하여 이후 같은 입력이 들어올 때 다시 계산하지 않고 

저장된 값을 불러와서 재활용하는 최적화 기법이다. 

메모이제이션은 함수의 결과 값을 저장하는 캐시를 이용하여 동작한다. 

 

 

DP의 예시인 피보나치 수열을 보면,

 f(n) = f(n-1) + f(n-2)

 

 

f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고,

이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다. 

그러나 결과값을 저장해두고 재사용한다면? 다시 계산할 필요가 없기 때문

시간복잡도가 줄어들게 된다. 

 

 

1. DP로 풀 수 있는 문제인지 확인한다.

 

2. 문제의 변수를 파악한다.

•  예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다.
• 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하는것이다.
• 또한, 문자열 간의 차이를 구할 때는 문자열의 길이, Edit 거리 등 2가지 변수를 사용한다. 

 

3. 변수간 관계식 만들기

• 점화식을 만들어 반복/재귀를 통해 해결할 수 있도록 한다. 

4. Memoization (결과를 저장)

 

5. 기저상태 확인

• 기저 문제에 대해 파악 후 미리 배열 등에 저장

 

6. 구현하기

• Bottom-up(Tabulation 방식) - 반복문 사용
• Top-down (Memoization 방식) - 재귀 사용

 

➡️ 동적 프로그래밍으로 푸는 문제는 이 문제의 작은 문제를 구조화 하는 것 부터 시작!

 

 

분할정복 vs 동적 계획법

분할 정복 알고리즘은 문제를 분리된 여러 하위 문제들로 나누고, 그 하위 문제를 재귀적으로 해결한 다음 각각의 해결책을 결합하여 원래 문제를 해결하는 방식

이와 대조적으로 다이나믹 프로그래밍은 하위문제들이 겹칠 때 적용할 수 있다. 

 

나누었을 때 중복이 없으면 -> 분할정복

중복이 많이 나온다면 -> 동적 계획법

 

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

 

백준 1003번 풀이

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

package 백준.DP;

import java.util.Scanner;

public class baekjoon_1003 {
    static int[] count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            count = new int[]{0, 0};
            fibonacci(N);
            System.out.println(count[0] + " " + count[1]);
        }
    }

    public static int fibonacci(int N) {
        if (N == 0) {
            count[0]++;
            return 0;
        } else if (N == 1) {
            count[1]++;
            return 1;
        } else {
            return fibonacci(N - 1) + fibonacci(N - 2);
        }
    }
}

 

count 배열에 바로 저장하는 형식으로 진행했더니 바로 시간초과가 떴다.

 

 

N이 최대 40까지 주어지고, 각 N에 0과 1이 호출된 횟수를 담아야 하므로 2차원 배열이 있어야 한다.

피보나치 함수는 각 N에 대한 0과 1의 값을 2차원 배열에 저장하면서 재귀 호출을 해주어야 한다. 

 

 

dp[0][0] = 1;	// N=0 일 때의 0 호출 횟수
dp[0][1] = 0;	// N=0 일 때의 1 호출 횟수
dp[1][0] = 0;	// N=1 일 때의 0 호출 횟수
dp[1][1] = 1;	// N=1 일 때의 1 호출 횟수

 

값을 미리 저장한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static Integer[][] dp = new Integer[41][2];

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

        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            fibonacci(N);
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

    static Integer[] fibonacci(int N) {
        if (dp[N][0] == null || dp[N][1] == null) {
            dp[N][0] = fibonacci(N - 1)[0] + fibonacci(N - 2)[0];
            dp[N][1] = fibonacci(N - 1)[1] + fibonacci(N - 2)[1];
        }
        return dp[N];
    }
}

 

전체 풀이과정이다.