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

동적 계획법(Dynamic Programming, DP)

---

- 큰 문제를 작은 문제로 나누어서 푸는 방식의 알고리즘.

- 처음 문제를 더 작은 문제로 나누고 결과를 알아내어 저장함. 이것들을 이용해 원래 답을 계산함.

 

성립 조건

---

1. 최적 부분 구조(Optimal Substructure)

- 상위 문제를 하위 문제로 나누어 하위 문제의 답으로 상위 문제 해결 가능.

2. 중복되는 부분 문제(Overlapping Subproblem)

- 문제를 여러 개의 부분 문제로 쪼갤 수 있음.

 

ex) 피보나치 수열: 0 1 1 2 3 5 8 13 21 34 55 89 ...

• F0 = 0
• F1 = 1
• Fn = Fn-1 + Fn-2 (n ≥ 2)

큰 문제는 작은 문제 통해 해결할 수 있음.

 

n번째 피보나치 수 = n - 1번째 피보나치 수 + n - 2번째 피보나치 수

n - 1번째 피보나치 수 = n - 2번째 피보나치 수 + n - 3번째 피보나치 수

n - 2번째 피보나치 수 = n - 3번째 피보나치 수 + n - 4번째 피보나치 수 ...

 

겹치는 부분 문제는 답이 항상 같음. 정답을 캐시에 저장하는 것을 메모이제이션(Memoization).

 

메모제이션 Memoization

---

- 계산 결과를 메모리 공간에 저장함.

- 동일 문제를 호출하면 저장 결과를 그대로 가져옴.

- 캐싱(Caching): 값을 기록

 

피보나치 수를 구하는 함수

int fibonacci(int n) {
    // f(0) = 0, f(1) = 1
    if (n <= 1) {   
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

 

중복된 계산을 반복해서 하게 됨. 시간복잡도 O(2^n).

 

메모이제이션을 통해 모든 문제를 한 번만 품. 중복되는 부분문제 결과 생략.

 

하위 문제의 값을 memo[]에 저장.

int memo[1000];
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        // memo의 값이 0이 아니면 그 값을 그대로 사용
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

 

Top-down 과 Bottom-up

---

Top-down (하향식)

- 하위 문제를 재귀적으로 호출해 이를 해결함으로써 상위 문제 해결

- 하위 문제를 저장하기 위해 메모이제이션 사용

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

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

    // Top-down
    static int fibonacci(int x) {
        if (x <= 1) {
            return x;
        }else {
            if (memo[x] != 0)
                return memo[x];
            
            memo[x] = fibonacci(x - 1) + fibonacci(x - 2);
            return memo[x];
        }
    }
}

Bottom-up (상향식)

- 하위 문제를 해결하면서 나온 값으로 상위 문제 해결

- DP 형태 

- 문제 결과 값 저장용 리스트 = DP 테이블

- 반복문 사용

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

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

    // Bottom-up
    static int fibonacci(int x) {
    	memo[0] = 0;
        memo[1] = memo[2] =1;
        
        for(int i=3; i<x+1; i++) {
            memo[i] = memo[i-1] + memo[i-2];
        }
        return memo[x];
    }
}