초급 3회차 동적 프로그래밍

동적 프로그래밍의 개념

전체 문제를 여러 개의 부분 문제로 나누어 풀 수 있을 때에 사용하는 문제풀이법이다.

 

예를 들어 팩토리얼을 구한다고 하자.

1! 부터 100!까지를 모두 구하라는 문제가 주어졌다.

 

그런데,

5!을 구하려고 할 때

$1 \times 2 \times 3 \times 4 \times 5$ 와 같이 네 번의 곱셈연산을 수행할 수도 있지만,

이미 4!의 값을 알고 있다면

4!$\times 5$ 와 같이 한 번의 곱셈연산으로 5!를 구할 수 있다.

 

빨간 글씨의 방법처럼 각 팩토리얼을 구하면

1!을 구하기 위해서 0번의 곱셈,

2!을 구하기 위해서 1번의 곱셈,

3!을 구하기 위해서 2번의 곱셈,

...

100!을 구하기 위해서 99번의 곱셈이 필요하다.

총 4950번의 연산이 필요하다.

 

파란 글씨의 방법처럼 각 팩토리얼을 구하려면

1!을 구하기 위해서 0번의 곱셈,

2!을 구하기 위해서 1번의 곱셈,

2!의 값을 가져와서 3만 곱하여 3!을 구하므로 3!을 구하기 위해서 1번의 곱셈,

3!의 값을 가져와서 4만 곱하여 4!을 구하므로 4!을 구하기 위해서 1번의 곱셈,

...

99!의 값을 가져와서 100만 곱하여 100!을 구하므로 100!을 구하기 위해서 1번의 곱셈이 필요하다.

총 99번의 연산만 하면 된다.

 

(k-1)! 을 구하는 것이 k! 을 구하는 것의 부분 문제이기 때문에 이렇게 효율적으로 문제를 해결할 수 있는 것이다.

이런 문제풀이법을 동적 프로그래밍이라고 한다.

 

메모이제이션이란?

위의 팩토리얼 문제에서 동적 프로그래밍을 사용하려면,

(k-1)! 의 값을 구한 뒤 이 결과값을 갖다버리지 않고 잘 기록해두었다가 k!를 구할 때 써야 한다.

 

이처럼, 각 부분 문제의 결과값은 한 번만 쓰이지 않는다. 더 규모가 큰 부분 문제를 풀 때 반복적으로 사용된다.

그 때마다 부분 문제를 또 풀고 또 풀고 계속 풀면 동적프로그래밍을 했다고 볼 수가 없다. 그냥 노가다로 풀 때와 다를 것이 없기 때문이다.

 

따라서 각 부분 문제의 결과값을 한 번만 구해서 잘 기록해놓아야 한다. 그래야 연산 횟수를 크게 줄일 수 있다.

이런 기록 작업을 메모이제이션이라고 부른다.

 

죽었다 깨어나도 나올 수 없는 값

메모이제이션을 할 때에는

모든 부분 문제의 결과값을 저장하기 위한 저장공간을 쭉 마련해두고,

그 공간에 차곡차곡 값을 넣어주면 된다.

 

이 때,

어떤 부분 문제를 이미 풀었고 어떤 부분 문제를 아직 안 풀었는지를

편리하게 판별할 수 있는 방법이 있다.

죽었다 깨어나도 나올 수 없는 값을 이용하는 것이다.

 

모든 부분 문제의 결과값을 저장하기 위한 저장공간을 마련해놓을 때,

연산을 시작하기 전에 그 모든 공간들에 들어있을 초기 값을

이 문제에서 절대로 도출될 수가 없는 값으로 정해두면 된다.

 

예를 들어 위의 팩토리얼 문제의 경우라면

양수끼리만 곱하므로 절대 팩토리얼의 결과값이 음수가 될 수 없다.

 

그럼 int[] dp = new int[101]을 선언해두고

Arrays.fill(dp, -1)을 실행하여 모든 칸에 -1을 넣어둔다.

어떤 양의 정수 k에 대하여 k!의 값을 구하면 즉시 dp[k]에 그 결과값을 넣는다.

그럼, 결과값을 이미 구한 정수 n의 경우에는 dp[n]에 양수가 들어있게 되고, 아직 구하지 않은 정수 n의 경우에는 dp[n]에 음수인 -1이 들어있게 된다.

dp[n]의 내용물이 0보다 큰지만 체크하면 이 공간에 저장된 데이터가 유효한 것인지를 바로 판별할 수 있게 된다.

 

기저조건(Base Case)

재귀적인 함수를 정의할 때 재귀호출을 더이상 하지 않고 종료하도록 하는 기준.

그리고 동적 프로그래밍에서 가장 작은 부분문제 즉 가장 밑바닥의 경우가 기저조건이다.

팩토리얼 문제에서는 1!이 기저조건이다.

최적 부분 구조

전체 문제의 최적해가 부분 문제의 최적해로부터 도출될 때, 최적 부분 구조가 갖추어졌다고 한다.

 

동적 프로그래밍 문제를 풀 때의 접근 방식 3단계

먼저 동적 프로그래밍을 사용할 수 있는지를 확인하기 위해서는

현재 상태, 이전 상태, 다음 상태의 구분이 가능한지, 상태 사이의 전이 양상이 어떠한지를 살핀다.

예를 들어 팩토리얼 문제에서는 현재 상태가 4!이라면 이전은 3!이고 다음은 5!이다.

그 후 다음과 같은 단계를 거쳐 문제를 해결한다.

 

1. 최적해의 구조를 정의해본다.
2. 최적해의 값을 정의하기 위한 관계식(점화식)을 짜본다.
3. 가장 작은 부분문제(Base Case)부터 차근차근 최적해를 구해나가며 결과적으로 전체 문제의 최적해를 구한다.

 

동적 프로그래밍에서의 복잡도

동적 프로그래밍을 위한 점화식을 정의할 때에 고려해야 하는 복잡도는 다음과 같다.

• 공간복잡도: 모든 부분 문제의 개수(메모이제이션을 위한 공간을 부분 문제의 개수만큼 마련해야 하기 때문)
• 시간복잡도: 모든 부분 문제의 개수$\times$하나의 부분 문제를 푸는 데 걸리는 시간(하나의 부분 문제를 푸는 데 필요한 연산(주로 반복문)의 수행 횟수)