NovaAdmin: DCWiki 복구: 최신본 이식

2026-01-08T08:38:06Z

DCWiki 복구: 최신본 이식

새 문서

==개요==
문제 하나를 작은 문제 여럿으로 나눠서 푸는 문제 해결 방식을 말한다. 큰 문제를 작은 문제로 나누는 Top-down과 작은 문제를 풀면서 쌓아 큰 문제까지 푸는 Bottom-up이 있다. Dynamic의 뜻과는 아무런 상관이 없다. 고안한 사람이 Dynamic이라는 단어가 멋있어서 붙였다고 한다.
==Memoization==
메모이제이션(메모리제이션이 아니다)은 필요한 값이 이미 구해져 있으면 그걸 쓰고, 구해져 있지 않으면 그걸 구한다는 뜻이다. 이미 구한 값을 또 구하는 쓸데없는 짓을 하지 않는 게 목표다. 다음 예시를 보자.
<source lang="c">
int fibo(int n)
{
if (n<=1) return n;
return fibo(n-1)+fibo(n-2);
}
</source>
n번째 피보나치 수를 구하는 함수다. 그럼 fibo(4)를 호출했을 때 다음과 같은 일이 일어난다.

1. fibo(4)를 호출한다.

2. fibo(3)을 호출한다.

3. fibo(2)를 호출한다.

4. fibo(1)을 호출한다. fibo(1)은 1을 리턴한다.

5. fibo(0)을 호출한다. fibo(0)은 0을 리턴한다.

6. 4와 5에서 구한 값을 더해 fibo(2)를 구한다.

7. fibo(1)을 호출한다. fibo(1)은 1을 리턴한다.

8. 6과 7에서 구한 값을 더해 fibo(3)을 구한다.

9. fibo(2)를 호출한다.

10. fibo(1)을 호출한다. fibo(1)은 1을 리턴한다.

11. fibo(0)을 호출한다. fibo(0)은 0을 리턴한다.

12. 10과 11에서 구한 값을 더해 fibo(2)를 구한다.

13. 8와 12에서 구한 값을 더해 fibo(4)를 구한다.

이미 구해놓은 fibo(2), fibo(1), fibo(0)을 3에서 또다시 구한다. 비효율적이다. 그래서 우리는 어떤 값을 구할 때마다 그 값을 메모해놓고, 그 값이 필요해질 때마다, 그 값을 직접 구할 필요 없이, 그 메모를 가져다 쓰면 되게 해야 한다. 이게 바로 메모이제이션이다. 메모이제이션에 무조건 들어가야 하는 과정이 두 개 있다. 첫 번째는 메모가 있는지 확인하는 것, 두 번째는 메모가 없으면 메모를 쓰는 것.
<source lang="c">
//top-down
int memo[100]; //전역 변수, 자동으로 0으로 초기화.
int fibo(int n)
{
if (n<=1) return n;
if (memo[n]!=0) return memo[n]; //메모 읽기
//아직 메모되지 않은 값(구해지지 않은 값)은 0이다. 0이 아니라면 구해졌다는 뜻이다. 그걸 쓰면 된다.
memo[n]=fibo(n-1)+fibo(n-2); //메모 쓰기
//그 값이 아직 메모되지 않았으므로 메모를 쓴다.
return memo[n]; //메모에 적은 값을 리턴한다.
}
</source>
이렇게 하면 피보나치 수를 구하는 데 드는 시간을 비약적으로 줄일 수 있다. 단, 변수를 저장할 메모리 공간을 따로 할당해줘야 한다. 이 함수에서 fibo(4)를 호출하면 이렇게 된다.

1. fibo(4)를 호출한다.

2. fibo(3)을 호출한다.

3. fibo(2)를 호출한다.

4. fibo(1)을 호출한다. fibo(1)은 1을 리턴한다.

5. fibo(0)을 호출한다. fibo(0)은 0을 리턴한다.

6. fibo(2)가 4와 5에서 구한 값을 더하여 memo[2]에 쓰고 memo[2]를 리턴한다.

7. fibo(1)을 호출한다. fibo(1)은 1을 리턴한다.

8. fibo(3)이 6과 7에서 구한 값을 더하여 memo[3]에 쓰고 memo[3]을 리턴한다.

9. fibo(2)를 호출한다. memo[2]가 이미 구해졌으므로 fibo(2)는 호출되자마자 memo[2]를 리턴한다.

10. 8과 9에서 구한 값으로 fibo(4)를 구한다.

n이 커질수록 메모이제이션이 빛을 발한다. 지금까지 한 건 top-down 방식이었다. top-down은 큰 문제를 작은 문제로 쪼개는 것이다. 그러니까, fibo(4)를 구하는 문제를 fibo(3)과 fibo(2)로 구하는 문제로 쪼개고, fibo(3)을 구하는 문제를 fibo(2)와 fibo(1)을 구하는 문제로 쪼개고.. 이런 식이다. Bottom-up은 작은 문제를 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 풀 수 있다... 이걸 반복하면 n번째 피보나치 수를 구하는 문제를 풀 수 있게 된다. 구현은 다음과 같다.
<source lang="c">
//bottom-up
int nums[10000]={0,1,}; // 첫 번째, 두 번째 피보나치 수를 구하는 작은 문제에서 시작.
for (int i=2; i<input; i++)
nums[i]=nums[i-2]+nums[i-1]; // 다음 문제 풀기.
</source>
이 소스 코드는 1만 번째 피보나치 수까지 구할 수 있다(오버플로우는 무시). 더 큰 피보나치 수가 필요할 때마다 배열의 크기를 늘리는 게 불편하다면 이렇게 할 수 있다.
<source lang="c">
int nums[3]={0,0,1};
for (int i=2; i<input; i++)
{
nums[0]=nums[1]; //한 칸 밀기
nums[1]=nums[2]; //한 칸 밀기
nums[2]=nums[0]+nums[1]; //다음 문제 풀기
}
</source>

다이나믹 프로그래밍 - 편집 역사

NovaAdmin: DCWiki 복구: 최신본 이식