Fibonacci Number
피보나치 수열은 다음과 같은 방식으로 전개되는 수열입니다.
long fibonacci(int n)
{
return (n < 2) ? n : fibonacci(n-1) + fibonacci(n-2);
}
위와 같이 피보나치 수열의 값을 재귀로 구하게 된다면 시간이 너무 오래걸린다는 문제가 있습니다.
재귀적으로 짠 fibonacci()의 경우 아래와 같은 방식으로 호출이 일어납니다.
아래의 예시는 fibonacci(5)를 구하는 case입니다:
함수 호출을 총 15번하는 것을 볼 수 있습니다. 구하는 n의 값이 작은 경우 그리 크게 상관은 없지만, n이 커지게 된다면 2가지 문제점이 발생할 수 있습니다.
- 재귀호출이 지나치게 많아져서 memory가 부족해 질 수 있다 → stack overflow
- 느리다 → O(2^n)의 시간복잡도를 갖습니다
위 방식의 문제점은 이미 계산한 것을 중복해서 너무 많이 호출한다는 점입니다.
위에 예시를 보면 fib(1)의 경우 총 5번이나 불리고,
fib(2)의 경우는 3번이나 불리는 것을 볼 수 있습니다.
하지만, fib(1)이나 fib(2)의 값을 계산해야할 때마다 처음부터 다시 계산한다는 점이 문제입니다.
그렇다면 fib(1)이나 fib(2)의 값을 한 번 계산하고
그 값을 기록해놓는다면,
나중에 fib(1), fib(2)의 값이 필요할 때 처음부터 계산하지 않고 그냥 가져다 쓸 수 있습니다.
이를 통해 시간을 크게 줄일 수 있습니다.
Solution - Memoization
Memoization은 Dynamic Programming의 한 방법으로 한 번 계산한 값을 반복적으로 계산하지 않도록 기록해두는 것을 말합니다.
+ Memoization과 일반적인 Dynamic Programming이 다른점은 Dynamic Programming의 경우 기록하는 순서가 있다는 점입니다. 일반적으로 작은 범위에서 큰 범위로 계산하거나, 한 쪽 방향으로 계산하는 등, 계산의 순서가 있다는 점에서 차이점이 있습니다.
다음은 fibonacci(5)를 구하는 case에 memoization을 적용한 결과입니다:
코드는 다음과 같습니다:
long fibMemoization(int n, long[] memo)
{
if(memo[n] != 0) return memo[n];
memo[n] = (n==1 || n==2) ? 1 : fibMemoization(n-1, memo) + fibMemoization(n-2, memo);
return memo[n];
}
Selecting Working Days
- Given pay for each of N days
- Select days to work to maximize total pay
- One rule: you cannot work on consecutive days
이를 해결하기 위한 어떤 특정한 규칙을 찾지 못한다면,
모든 경우의 수를 다 확인해봐야 합니다.
하지만 모든 경우의 수를 전부 계산하는 것은 너무 시간이 오래 걸리기 때문에,
Dynamic Programming을 통해,
중복되는 case를 이미 기록되어있는 것을 사용하여 중복 시간을 줄여주면,
모든 경우의 수를 빠르게 탐색할 수 있습니다.
이도 같은 방법으로 풀 수 있습니다.
우선 일을 그날 하지 않았을 때와 했을 때를 구분합니다.
그리고 배열 D를 만듭니다.
D[i][0]은 i번째 날에 일을 안 할 경우 벌 수 있는 최대의 돈입니다.
D[i][1]은 i번째 날에 일을 한 경우 벌 수 있는 최대의 돈입니다.
그렇다면 다음과 같은 코드를 통해 결과를 구할 수 있습니다:
int W(int a[], int n)
{
int D[n+1][2];
D[1][0] = 0;
D[1][1] = a[1];
for(int i=2; i<=n; i++){
D[i][0] = max(D[i-1][0], D[i-1][1]);
D[i][1] = D[i-1] + a[i];
}
return max(D[n][0], D[n][1]);
}
+ D[i][0]의 값은 i번째 날에는 일을 하지 않기 때문에 i번째 날까지 벌 수 있는 최대의 돈은 가능한 i-1번째 날의 값들 중 최대값을 갖습니다.
+ D[i][1]의 값은 연속하는 2일은 일을 할 수 없다는 규칙때문에 (전날에 일을 하지 않았을 때 벌 수 있는 최대의 돈) + (그날 벌 수 있는 돈) 이 i번째 날까지 벌 수 있는 최대값이 됩니다.
Path Counting
다음과 같은 길이 주어진 경우,
가장 왼쪽 위 (A) 에서 출발해서,
가장 오른쪽 아래 (B) 에 도착하는 모든 경우의 수를 구하는 문제를 떠올려봅시다.
각 점을 지나는 가능한 path의 경우의 수는 위에서 내려오는 경우의 수 + 왼쪽에서 오는 경우의 수입니다.
이를 활용해서 계산한다면,
Dynamic하게 계산할 수 있습니다.
Matrix Multiplication
- Multiply a sequence of N matrices M1 * M2 * ... * MN
이런 경우 최소 시간이 걸리는 계산 순서를 찾는 문제를 떠올릴 수 있습니다.
예를 들어,
M1 = 3 by 5, M2 = 5 by 1, M3 = 1 by 6인 행렬이라 하면,
- case1
- M1 * M2 = retM → retM * M3
- Time = 3 * 5 * 1 + 3 * 1 * 6 = 15 + 18 = 33
- retM 만드는 데에 3 * 5 * 1, retM * M3 하는 데에 3 * 1 * 6
- case 2
- M2 * M3 = retM → M1 * retM
- Time = 5 * 1 * 6 + 3 * 5 * 6 = 30 + 90 = 120
이렇게 행렬곱을 수행하는 순서에 따라 값이 연산 시간이 달라질 수 있습니다.
이를 해결하는 특정한 방법을 찾을 수 없다면,
또 모든 경우의 수를 찾아야 하고,
모든 경우의 수를 Naive하게 찾기에는 시간이 너무 오래걸리기 때문에,
Dynamic 하게 풀어내야합니다.
따라서 다음과 같은 함수 D[N][N]을 만듭니다.
- D[i][j] = Mi * Mi+1 * ... * Mj 의 연산 시간 중 최소의 시간을 나타냅니다.
- D[i][i] = 1, Mi 행렬에 대해서만 생각하기 때문에 1로 생각할 수 있습니다.
그렇다면 우리가 구하고자 하는 값은 D[1][N]이 됩니다.
계산의 순서는 어떻게 될까요?
D[i][j]는 어떤 값들을 계산해야할까요?
Mi * Mi+1 * Mi+2 * ... * Mj 의 계산의 최소시간이기 때문에,
Mi * (Mi+1 * Mi+2 * ... * Mj)
(Mi * Mi+1) * (Mi+2 * ... * Mj)
...
등등을 고려해야합니다.
즉, 가장 마지막에 계산하는 곱하기를 기준으로
여러개의 case를 고려해야합니다.
그렇다면,
Mi * (Mi+1 * Mi+2 * ... * Mj) 에서
(Mi+1 * Mi+2 * ... * Mj) 는 어떻게 Dynamic 하게 구할 수 있을까요?
여기에서 힌트가 나옵니다.
즉, 계산의 순서에 대한 힌트가 나옵니다.
작은 범위에서부터 시작해서 큰 범위의 값으로 확장해 나가며 D[][]을 계산합니다.
D[1][1], D[2][2], ... D[i][i] = 1로 초기화 하고,
D[1][2] 는 D[1][1] 과 D[2][2] 를 이용해서 만들 수 있으며,
D[2][3] 은 D[2][2] 와 D[3][3] 을 이용해서 만들 수 있습니다.
D[2][4] 는 D[2][2] * D[3][4] 과 D[2][3] * D[4][4] 를 비교해서 최소 시간을 구할 수 있습니다.
이런 식으로 작은 범위에서부터 시작해서
D[1][N]을 구할 수 있습니다.
시간복잡도는 D[N][N] table을 만드는데 O(N^2)
각각의 D값을 구하는 데에 최대 O(N) → 가장 마지막에 계산 되는 곱하기에 대해 case를 나눠서 고려해야하기 때문에, 예를 들어 D[2][80]의 경우 총 78개의 곱하기가 존재하기 때문에, 78개의 조합을 고려해야합니다.
따라서 최종적인 시간 복잡도는 O(N^3)입니다.
'[학교 수업] > [학교 수업] Data Structure' 카테고리의 다른 글
| [자료구조 및 알고리즘] Dynamic Programming (3) (0) | 2024.11.05 |
|---|---|
| [자료구조 및 알고리즘] Dynamic Programming (2) (0) | 2024.11.01 |
| [자료구조 및 알고리즘] Other things using Divide and Conquer (1) | 2024.10.17 |
| [자료구조 및 알고리즘] Convex Hull (1) | 2024.10.15 |
| [자료구조 및 알고리즘] Closest Pair (1) | 2024.10.11 |
