< 동적 계획법 >
동적계획법이란 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법을 뜻합니다.
예를 들어 1부터 N까지의 곱을 구하는 코드를 작성해본다고 했을 때, 점화식을 이용해 해결해보려고 합니다.
F(N)을 1부터 N까지의 곱이라고 정의한다면, 다음과 같이 점화식을 세워볼 수 있습니다.
- F(N) = F(N - 1) * N (N > 1) - 점화식
- F(1) = 1 - 초기조건
이러한 점화식을 이용하면, 다음과 같이 답이 구해진다고 생각해볼 수 있습니다.
이를 코드로 구현할 수 있는 방법은 크게 2가지가 있습니다.
첫 번째는 for loop을 이용하는 것입니다.
점화식을 통해 F[i - 1] 값이 구해졌다는 가정 하에서 F[i]값을 쉽게 구할 수 있으며, 초기 조건인 F[1] = 1 은 처음 설정해주면 되므로 다음과 같이 코드 작성이 가능합니다.
F[1] = 1
for i = 2 ... i <= n
F[i] = F[i - 1] * i
print(F[n])
두 번째는 재귀함수를 이용하는 것입니다. 재귀함수를 이용하여 점화식을 표현하기 위해서는, 종료조건으로 초기 조건을 넣어주고, 그렇지 않은 경우에는 점화식을 적어주면 됩니다.
코드는 다음과 같습니다.
function f(n)
if n == 1
return 1
else
return f(n - 1) * n
print(f(n))
이처럼 동적계획법은 점화식을 기반으로 하는 방법이며, for문을 이용하여 해결할 수도 있고 재귀함수를 이용하는 것도 가능합니다.
< 동적 계획법에 대한 이해 >
- 동적 계획법 = 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법
- 동적 계획법은 점화식을 기반으로 하는 방법
by. for 문
by. 재귀함수를 이용함
- 동적 계획법은 항상 점화식을 기반으로 함
(작은 문제들을 이용해 큰 문제를 풀기 위해서 작은 문제와 큰 문제 사이의 관계식이 필요)
< 동적 계획법 적용 >
1부터 N까지의 숫자의 곱을 구하는 코드를, 다음 점화식을 이용해 작성해보았습니다.
- F(N) = F(N - 1) * N (N > 1) - 점화식
- F(1) = 1 - 초기조건
그 코드는 다음과 같습니다.
F 배열은 처음에 전부 0으로 초기화 되어있다고 했을 때, n = 4일 때의 출력 결과는 어떻게 될까요?
F[1] = 1
for i = n ... i >= 2
F[i] = F[i - 1] * i
print(F[n])
< 메모이제이션(Memoization) >
동적계획법으로 해결하기 위한 방법 중에 하나로 재귀함수가 가능하다고 했습니다. 예를 들어 피보나치 수열에서 n번째 원소의 값을 재귀함수를 이용해 구해볼 수 있을 것입니다.
그러나 그 코드로 50번째 피보나치 수를 구하면 어떤 일이 일어나는지 아시나요?
일단 기억을 떠올리기 위해 피보나치 수를 구하는 코드를 다시 한 번 보도록 하겠습니다.
function fibbo(n)
if n <= 2
return 1
else
return fibbo(n - 1) + fibbo(n - 2)
이 코드를 통해 50번째 수를 구해주면, 엄청나게 오랜 시간이 소요되는걸 확인할 수 있습니다. 놀랍게도 1분 이상 걸립니다!!
왜 이런 문제가 생기는걸까요? 50번째 수를 다 탐색하기는 어려우니까, 가볍게 6번째 피보나치 수를 구하는 과정을 분석해보겠습니다.
6번째 수를 구하기 위해서는 5번째 수와 4번째 수를 합쳐야 합니다.
결국, 5번째 수와 4번째 수를 구해야 하는데 5번째 수도 4번째 수와 3번째 수의 합을 알아야 구할 수 있을 겁니다.
이런식으로 구하는 과정을 간략하게 표현하면 다음과 같을겁니다.
자세히 본다면, 우리는 같은 결과를 너무 여러번 구하는 것을 볼 수 있습니다. 6번째 수를 구하기 위하여 4번째 수를 2번, 3번째 수를 3번, ... 구하게 됩니다.
그래도 별로 적은거 아니라고요? 50번째 피보나치 수를 구하기 위해선 fibbo 함수가 총 2,075,316,483회 실행됩니다. 따라서 시간이 엄청 길어질 수 밖에 없는 것이지요.
이런 문제를 해결할 수 있는 방법이 없을까요? 바로 중복을 제거하면 됩니다 !!
위의 그림을 보면, F(4)가 아예 동일한 작업을 반복한다는 것을 알 수 있습니다. 만약, 왼쪽 부분에서 F(4)값을 이미 한번 계산했고 그 결과가 3이라는 것을 알고 있었다면, 오른쪽에서 F(4)를 계산해야 하는 차례가 왔을 때에는 재귀를 추가적으로 진행하지 않고 숫자 3을 바로 반환하면 되지 않을까요?
이를 가능하게 하기 위해 memo라는 배열을 이용해 볼 수 있습니다.
처음에는 전부 -1로 초기화를 해놓습니다.
memo에 해당하는 값이 -1이라면, 그 값을 실제로 계산한 뒤 memo에 저장해둡니다.
이후 memo에 해당 값이 -1이 아니라면, 이미 계산한 적이 있었다는 뜻이므로 memo에 적혀있는 값을 그대로 반환합니다.
이렇게 진행을 하게 되면, 각 n에 해당하는 값을 정확히 한 번씩만 계산해주게 됩니다.
값을 전부 -1로 채워넣고 시작해도 되는 이유는, 피보나치 값이 -1이 될 수가 없다는 것을 미리 알고 있기 때문입니다. 이렇게 초기값은 답이 될 수 없는 값으로 설정하며, 보통 -1로 많이들 설정합니다.
이렇게 memoization을 고려해 코드를 새로 짜면, 다음과 같이 될 것입니다.
memoization 이용시에는 함수 도입부에 -1이 아닌 경우 memo 값을 반환해주는 코드를 작성해주면 됩니다. 그렇지 않은 경우라면 반환해줘야 하는 값을 memo에 저장해준 뒤 해당 값을 반환해주면 됩니다.
function fibbo(n)
if memo[n] != -1 // 이미 n번째 값을 구해본 적이 있다면
return memo[n] // memo에 적혀있는 값을 반환해줍니다.
if n <= 2 // n이 2이하인 경우에는 종료 조건이므로
memo[n] = 1 // 해당하는 숫자를 memo에 넣어줍니다.
else // 종료조건이 아닌 경우에는
memo[n] = fibbo(n - 1) + fibbo(n - 2) // 점화식을 이용하여 답을 구한 뒤
// 해당 값을 memo에 저장해줍니다.
return memo[n] // memo 값을 반환합니다.
이렇게 코드를 바꾸게 되면 기존에 시간복잡도를 갖던 코드가, 이제는 에 올바른 답을 구하게 됩니다. 이는 중복하여 탐색하는 경우가 아예 사라졌기 때문에 가능해진 것입니다.
우리는 이런식으로 값을 기록하고, 그 기록한 값을 참조하는 것을 메모이제이션 (Memoization) 이라고 부릅니다.
< 중복된 피보나치 >
다음 두 함수에 대해 각각 fibbo(7) 호출시 fibbo(5) 와 fibbo(2) 는 몇 번이나 실행 되는지를 골라주세요.
1번 코드에서 fibbo(5), fibbo(2)에 해당하는 답, 2번 코드에서 fibbo(5), fibbo(2)에 해당하는 답 순서대로 골라주세요.
function fibbo(n)
if n <= 2
return 1
else
return fibbo(n - 1) + fibbo(n - 2)
fibbo(5): 2 // fibbo(2): 8
7
6 5
5 4 // 4 3
4 3 // 3 2 // 3 2 // 2 1
3 2 // 2 1 // 2 1 // 1 0 // 2 1 // 1 0 // 0 0
1 2 // 1 0
memo = [-1, -1, -1, ... ]
function fibbo(n)
if memo[n] != -1
return memo[n]
if n <= 2
memo[n] = 1
else
memo[n] = fibbo(n - 1) + fibbo(n - 2)
return memo[n]
이걸 틀림 >> fibbo(5): 2 // fibbo(2): 2
메모이제이션이 적용되었으며, 메모이제이션으로 인해 1번 코드에서 실행되었던 몇몇 fibbo 가 실행되지 않음
fibbo(n)은 2회째 방문부터 fibbo를 추가로 호출하지 않고 memo[n]을 리턴함
문제 1에서 구한 fibbo(5)들과 fibbo(2) 들 중 도달할 수 있는 것들은 몇 개가 있는지 세어보면,
fibbo(5), fibbo(2) 둘다 2회씩만 실행됨
< 파도반 수열 >
다음과 같이 삼각형이 나선 모양으로 놓여져 있다고 합시다. 첫 삼각형의 변의 길이를 1이라 하고, 그 이후에는 삼각형을 나선 에 배치되도록 새로 만들어줍니다. 그렇게 되면 자연스럽게 현재 나선 길이에서 가장 긴 변의 길이가 새로운 삼각형의 한 변의 길이가 되는 것을 볼 수 있습니다.
우리는 이 삼각형의 길이를 파도반 수열이라고 정의하고 있습니다. ()
첫번째 파도반 수열부터 10번째 파도반 수열까지는 다음과 같이 정의됩니다.
P(N) = P(N-2) + P(N-3)
1 1 1 2 2 3 4 5 7 9
파도반 수열도 피보나치 수열과 유사하게 정의되기 때문에, 동일하게 재귀로 풀어주게 된다면 오랜 시간이 소요될 것입니다. 따라서 메모이제이션을 이용하여 파도반 수열 문제를 다음과 같이 해결할 수 있습니다.
memo = [-1, -1, -1, ...]
function padovan(n)
if memo[n] != -1
return memo[n]
if n <= 3
memo[n] = 1
else
memo[n] = padovan(n - 2) + padovan(n - 3)
return memo[n]
다음 코드에서 padovan(10)을 수행하면 padovan(3)과 padovan(2) 는 몇 번이나 실행 되는지 알아 봅시다.
단, padovan(n - 2)가 padovan(n - 3)보다 항상 먼저 수행된다고 가정해도 좋습니다. >> 2 2
< 파도반도 빠르게 구할래 ! >
파도반 수열의 점화식을 알고 있으면, 파도반 수열의 계산도 위에서 학습했던 피보나치 수열과 동일한 방식으로 계산 가능합니다. 그러나 실제로 배웠던 메모이제이션이 잘 작동하는지 확인하고 싶었기 때문에, 다음처럼 중간 과정을 출력하는 코드를 삽입하였습니다.
memo = [-1, -1, -1, ...]
function padovan(n)
if memo[n] != -1
return memo[n]
if n <= 3
memo[n] = 1
else
memo[n] = padovan(n - 2) + padovan(n - 3)
print(memo[n])
return memo[n]
처음에 padovan(10) 을 실행 시키면 어떤 결과가 출력 될까요?
>> padovan 안에 print 가 실행되는 조건을 잘 보아야 함 !!
< Tabulation >
재귀함수 이외에도, 동적계획법 문제를 해결할 수 있는 방법이 하나 더 있습니다.
이는 for문을 이용하는 방법으로, 순서대로 배열에 값을 채워나가는 방식입니다. 이를 Tabulation이라고 부릅니다.
예를 들어 피보나치 수열의 n번째 원소를 구하는 코드는 다음과 같이 작성해 볼 수 있습니다. Tabulation 이용시 배열의 이름은 보통 동적계획법(dynamic programming)의 줄임말인 dp라고 짓는게 일반적입니다.
set dp = [0, 0, 0, ...]
dp[1] = 1
dp[2] = 1
for i = 3 ... i <= n:
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])
Memoization의 경우에는 높은 수에서 낮은 수 (구하려는 n번째 식을 구하기 위해 n - 1, n - 2번째 값을 구하려고 하므로)로 내려가기 때문에 탑다운 방식 (Top-Down Approach) 이라고 부르며,
Tabulation의 경우에는 아래에서 값을 채워 나가기 때문에 바텀업 방식 (Bottom-Up Approach) 라고 부릅니다.
이론적인 시간복잡도는 두 방법이 동일하나, 탑다운 방식은 함수를 재귀적으로 여러번 실행해야 하므로 함수 처리에 추가적인 시간이 약간 더 붙어 실제로는 바텀업 방식이 약간 더 빠릅니다.
어떤 문제를 풀 때 둘 중 어떤 방법을 사용해도 문제는 없지만, 특정 문제의 경우 한 방법으로 푸는 것이 더 쉬운 경우가 존재하므로, 두 방법을 모두 익혀두시는 것이 가장 좋습니다.
< 탑다운과 바텀업 >
동적계획법으로 문제를 해결하는 방법 중
- 메모이제이션은 탑다운 방식
- tabulation은 바텀업 방식
< 이상한 파도반 >
파도반 수열을 바텀업 방식을 통해 구하는 코드이고 파도반 수열이란 다음을 만족하는 수열이다.
점화식 - P(N) = P(N-2) + P(N-3) (N > 3)
초기 조건 - P(1) = 1, P(2) = 1, P(3) = 1
function solution(n)
dp = [0, 0, 0, ...]
dp[1] = 1
dp[2] = 1
(1)dp[3] = 1
for i = 4 ... i <= n
dp[i] = (2)dp[i - 3] + dp[i - 2]
return (3)dp[n]
< 점화식이 여러 작은 문제의 합으로 표현되는 경우 >
다음 문제를 해결해봅시다.
크기의 벽을 , 크기의 타일로 채울려고 합니다
만약 크기의 벽을 채울려고 한다면, 다음과 같은 3가지의 경우가 있습니다.
dp[i]를 크기의 벽을 , 크기의 타일로 채우는 데 가능한 서로 다른 가짓수라고 정의해봅시다. 그렇다면 다음과 같이 DP 배열에 값이 채워져야 합니다. i가 0인 경우에는 타일을 전혀 놓지 않는 경우가 한 가지 있으므로 의미상 1이 됩니다.
수가 적으면 직접 셀 수 있겠지만, N이 10인 경우만 해도 직접 계산하는 것은 불가능할 겁니다.
이 문제에서는 i번째를 끝으로 벽을 전부 타일로 채우는 경우를 생각해보면, 다음과 같이 끝에 세로로 하나를 붙이거나, 끝에 가로로 2개를 붙이는 경우만 존재한다는 것을 어렵지 않게 알 수 있습니다. 세로로 하나 붙이는 경우에는 남은 크기의 벽돌을 채우는 경우의 수와 같아지므로 dp[i - 1]가지가 되며, 가로로 2개를 붙이는 경우에는 남은 크기의 벽돌을 채우는 경우의 수와 같아지므로 dp[i - 2]가지가 됩니다.
즉 우리는 dp[i] = dp[i - 1] + dp[i - 2] 라는 점화식을 세울 수 있게 됩니다. 좀더 엄밀히는 다음을 만족하는 점화식을 얻게 됩니다.
- dp[0] = 1, dp[1] = 1
- dp[i] = dp[i - 1] + dp[i - 2] (i ≥ 2)
따라서 만약 크기의 벽을 , 크기의 타일로 채우려고 할 때 가능한 서로 다른 가짓수는 다음과 같이 점화식을 따라 dp 값을 순서대로 채워넣은 후 10번째 값을 읽어주면 됩니다. 즉, 답은 89가 됩니다.
| DP | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
이런식으로, 특정 시점에서 할 수 있는 선택지를 판단하고, 각 경우가 앞의 값을 어떤 식으로 참조할 수 있는지 설계하는 것이 중요합니다.
< 타일 채우기 >
크기의 벽을 크기의 타일로 채울려고 합니다. 만약 크기의 벽을 채울려고 한다면, 5가지의 경우가 있습니다. 그렇다면, 벽의 크기가 라면, 벽을 채울 수 있는 경우의 수는 몇 개 일까요?
| N = 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 3 | 5 | 11 | 21 | 43 | 85 |
< 음수 피보나치 >
만약 음수에도 피보나치가 있다면 어떨까요? 이고 이므로,
이 성립해 이 됩니다. 마찬가지로, 이 성립해 이 됩니다. 이런 방식으로 음수 피보나치 항을 정의하게 된다면, 은 어떤 값이 나오게 될까요?
| 1 | 0 | -1 | -2 | -3 | -4 | -5 | -6 | -7 | -8 |
| 1 | 0 | 1 | -1 | 2 | -3 | 5 | -8 | 13 | -21 |
'AI HW study > 자료구조·알고리즘' 카테고리의 다른 글
| 08. DP - String Matching, Greedy 알고리즘 (0) | 2023.08.20 |
|---|---|
| 08. DP - 전진하는 DP, 아이템 고르는 문제 (0) | 2023.08.20 |
| 07. 해싱 (0) | 2023.08.20 |
| 06. 트리 - Heap (0) | 2023.08.18 |
| 06. 트리 - 트리, 이진 트리 (0) | 2023.08.18 |
