DP(동적 계획법) 개념 및 문제 접근 방식

0. 개요

- DP(동적 계획법)은 어떤 공식이나 특정 형태가 아닌 방법론에 가까운 개념으로써의 알고리즘이다.

- 그래서 이론적으로 DP를 이해하기는 쉽지만, 문제에 적용하기가 쉽지 않다.

- 필자가 그랬기에, DP 개념과 문제 접근 방식을 이해하기 쉽게 설명해보려 한다. 

 

 

1. DP(동적 계획법)란?

- DP에 대해 검색해보면 다음과 같은 대표적인 표현이 등장한다. 

    → "하나의 큰 문제를 작은 문제로 나누고, 그 작은 문제를 해결하여 큰 문제의 답을 도출해내는 기법"

    → "작은 문제를 해결하는 과정에서 중복되는 연산을 수행하지 않는 기법"

 

- 도대체 이게 무슨 말일까? 

- 피보나치 문제를 예시로 DP의 특징과 문제 접근 방식에 대해 알아보자. 

 

 

2. DP 문제 접근 방식

- 피보나치 문제를 이용하여 DP 문제의 접근 방식에 대해 설명해보려고 한다.

 

a) 첫 번째 규칙 - 큰 문제를 작은 문제로 표현할 수 있다.

- 피보나치는 다음과 같이 표현된다. 

 

f(3) = f(2) + f(1)
f(5) = f(4) + f(3)
f(7) = f(6) + f(5)

 

- 위의 예시를 보면, f(3)이라는 큰 문제를 f(2)와 f(1)이라는 작은 문제로 나누었다.

- f(5)라는 큰 문제를 f(4)와 f(5)라는 작은 문제로 나누었다.

- f(7)이라는 큰 문제를 f(6)과 f(5)라는 작은 문제로 나누었다. 

 

- 이와 같이 하나의 큰 문제를 작은 문제로 표현할 수 있어야 DP를 적용할 수 있다. 

- 즉, 하나의 큰 문제를 해결하기 위해서는 이를 구성하는 작은 문제의 계산 값을 알아야 한다. 

 

 

b) 두 번째 규칙 - 점화식

- 위에서 DP 문제는 큰 문제를 작은 문제로 표현할 수 있다고 설명하였다.

- 이 말은 어떤 문제를 표현할 때 점화식(= 공식)으로 표현할 수 있다는 의미다. 

- 다음 피보나치 점화식처럼 말이다. 

 

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

 

- 피보나치 점화식을 분석해보면, f(n)의 값을 알기 위해서는 f(n - 1)과 f(n - 2)의 값을 알아야 한다.

- 즉, f(n)이라는 큰 문제를 f(n - 1)과 f(n - 2)라는 작은 문제로 나눌 수 있다는 것이다. 

- 이처럼 n이 어떤 값이던 항상 동일하게 점화식으로 표현할 수 있는 것이 DP 문제의 특징이다. 

- 더불어, 이 점화식을 직접 구하는 것이 DP 문제 풀이의 핵심이다. 

 

 

c) 세 번째 규칙 - Memoization (Optional)

- Memoization이란 컴퓨터 프로그램에서 동일한 계산을 반복(= 중복)해서 수행하는 경우 반복되는 동일한 연산의 값을

  메모리에 저장하여 중복 계산을 제거함으로써 프로그램의 속도를 빠르게 하는 기술 또는 방법론을 의미한다.

- 즉,  캐싱(Caching)이다. 

 

- DP에서도 이 방법론이 사용된다. 그러나 이는 선택적으로 사용한다.

- 그 이유는 조금 있다가 알아보고, 아래의 예시를 보자. 

 

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)

 

- 위의 예시에서 f(5)의 값을 구하려고 한다. 

- f(5)는 f(4)과 f(3)으로 나눌 수 있고, f(4)와 f(3) 또한 더 작은 문제로 나눌 수 있다.

- 이 과정을 반복하다 보면 다음과 같이 중복되는 연산을 수행한다. 

 

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)
f(3) = f(2) + f(1)

f(5) = f(3) + f(2) + f(2) + f(1) 
     = f(2) + f(1)+ f(2) + f(2) + f(1)

 

- 이처럼 중복 연산을 수행하는 것은 시간 복잡도나 메모리적 측면에서 비효율적이다.

- 그러므로 중복되는 연산의 값을 저장해놓는 방식을 사용하는데, 이를 memoization이라고 부른다. 

 

 

d) 네 번째 규칙 - 테이블의 사용 

- 앞서 DP는 memoization을 사용한다고 설명하였다.

- 그렇다면 어디에 중복되는 연산의 값을 저장할까? 

- 이 저장 공간을 테이블이라고 표현한다.

 

- 테이블은 특별한 것이 아니다.

- 어떤 형태로든 중복되는 연산의 값을 저장하고 필요할 때 찾아서 사용할 수 있으면 된다.

- 대표적으로 단일 또는 이중 배열, 리스트, 필요에 따라서는 HashMap으로 구현된다. 

 

 

3. Bottom-up & Top-down

a) DP의 풀이 방식

- 모든 DP 문제는 Bottom-up과 Top-down이라는 2가지 방식으로 풀이될 수 있다.

- 이 방식에 대해서 알아보도록 하자. 

 

 

b) Bottom-up 방식

- 어떤 글을 읽고 내용을 설명해야 한다고 해보자.

- 위에서 아래로 순차적으로 글을 읽고 내용을 이해한다.

- 이처럼 Bottom-up 방식은 데이터가 들어오는 순서대로 처리하는 과정을 사용한다.

 

- 대표적인 예시로, 위에서 구현한 피보나치 코드가 Bottom-up 방식이다.

- 즉, 1번째 숫자부터 N번째 숫자까지 차근차근 구하는 방식이다.

- 그러므로 반복문을 사용한 순차적인 DP 풀이를 Bottom-up 방식이라고 한다.

 

 

c) Top-down 방식

- 어떤 글을 읽고 내용을 설명해야 한다고 해보자.

- 주어진 글이 너무 길어서 각 문단의 앞부분만 읽고 전체적인 맥락을 이해한다.

- 이처럼 Top-down 방식은 어떤 패턴을 이용하는 과정을 사용한다. 

 

- 즉, 재귀 함수를 이용하여 답을 찾는 방식이다. 

- 그러므로 Recursion & Memoization을 사용한 DP 풀이를 Top-down 방식이라고 한다.

 

 

4. 코드 구현

- 위에서 DP의 4가지 특징 및 문제 접근 방식에 대해서 알아보았다.

- 이제 DP를 이용하여 피보나치수열의 값을 구하는 코드를 구현해보자.

- 이는 다음과 같이 구현할 수 있다.

 

a) Bottom-up 방식(= 반복문)

- Bottom-up은 순차적으로 계산하여 답을 찾는 방식이다.

- 그러므로 f(1)부터 f(n)까지 계산을 수행한다. 

 

public class Fibo {

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

    public static int fibo(int n) {
        int num1 = 0;
        int num2 = 1;
        int sum = 1;
        
        for(int i = 0; i < n; i++) {
           sum = num1 + num2;
           num1 = num2;
           num2 = sum;
        }
    }
}

 

 

b) Top-down 방식(= Recursion + Memoization)

- Top-down은 패턴을 이용하여 답을 찾는 방식이다.

- f(n)부터 계산을 시작하면서 f(n)을 계산하기 위해 필요한 데이터를 구하는 것이다.

  ex) f(n)을 계산하기 위해서는 f(n -1)과 f(n - 2)를 알아야 한다. 

 

public class Fibo {

    // 1. 중복 연산의 값을 저장할 테이블을 생성한다.(memoization)
    static Integer[] table = new Integer[100];
    
    public static void main(String[] args) throws IOException {
    
        // 2. n의 값을 입력받는다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 3. 피보나치의 기본 값을 설정한다.(memoization)
        table[0] = 0;
        table[1] = 1;

        // 4. 피보나치의 계산 값을 출력한다.
        System.out.println(fibo(n));
    }

    public static int fibo(int n) {

        // 1. memoization 확인
        if(table[n] == null) {
            // 2. 점화식 및 memoization 사용
            table[n] = fibo(n - 1) + fibo(n - 2); 
        }
        return table[n];
    }
}