17. dynamic programming [9 2주차]

17. Dynamic Programming [9-2주차]

2024년 1월 14일 일요일

오전 1:46

<Dynamic Programming>

재귀로 구현했을 때 느린 것을 Dynamic Programming을 이용하면 훨씬 빠르게 구현할 수 있다.

 

1.     재귀 코드를 먼저 찾고

2.     저장해야 할 재활용되는 값들을 찾은 후

3.     그 값들을 어떤 순서로 계산할지를 정한다.

 

 

<Fibonacci Number>

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

 

피보나치 수열을 재귀적으로 구현하면 매우 느리다. Dynamic Programming을 이용하면 훨씬 빠르게 구현할 수 있다.

 

 

<피보나치 수열 재귀적 구현>

int F(int n)

{

if (n < 2) return 1;

return F(n-1) + F(n-2);

}

 

시간복잡도는 O(F_n) 이다.

 

 

<동적계획법을 이용한 구현>

int FF[1000];

 

inf F(int n) {

FF[0] = FF[1] = 1;

for (i=2; i<=n; i++)

FF[i] = FF[i-1] + FF[i-2];

return FF[n];

}

 

 

이전의 값들을 배열에 저장하고, 값을 매번 새로 구하는 대신 이전에 구한 값들을 이용한다. 중복으로 재귀 호출을 할 필요가 없다.

 

재귀 호출 코드가 계산되는 순서를 이해하여, 작은 값부터 계산하는 구조로 바꾸어서 구현하였다.

 

 

<Memoization 을 통한 구현>

int FF[1000] = {1, 1, -1, -1, -1, …};

 

int F(int n) {

if (FF[n] == -1)

FF[n] = F(n-1) + F(n-1);

return FF[n];

 

 

계산 순서를 명시적으로 정하지 않은 코드. 위의 순서를 정한 코드보다 살짝 느리다.

 

 

<Select Working Days>

날짜별로 일해서 벌 수 있는 돈이 주어진다. 돈을 가장 많이 벌도록 일할 날짜를 정하자.

단, 이틀 연속으로 일할 수 없다.

 

 

<Dynamic Programming을 통한 Select Working Days 해결>

O : 해당 날짜에 일을 했을 때, 그날까지 벌 수 있는 최대의 돈

X : 해당 날짜에 일을 안 했을 때, 그날까지 벌 수 있는 최대의 돈

 

O에서의 답은 전날 일을 안 했어야 하므로 어제의 X로부터 답을 구함.

X에서의 답은 어제의 O, X의 답을 비교해서 큰 것으로 구함

 

전체 경우를 오늘 일하는 경우와 오늘 일하지 않는 경우로 나눈다. 두 경우 중 돈의 총합이 더 큰 것이 전체 문제의 답일 것이다. 전체 문제의 답을 구하기 어렵더라도, case를 나누면 문제를 풀기 훨씬 쉬울 수 있다.

 

Dynamic Programming 코드는 해당 내용을 미리 알아두지 않으면 이해하기 힘들다.

Dynamic programming에서는 case를 나눠서 여러 개를 계산할 때가 많다.

또한 지금 계산하려는 것이 무엇인지를 정확히 알아야 한다.

 

 

<Dynamic Programming을 사용하기 위한 조건>

특정 작은 문제의 답이 전체 문제에 영향을 받으면 안 된다. 전체 문제에 따라 작은 문제의 답이 달라진다면, 그 작은 문제의 답을 재활용할 수 없기 때문이다.

 

 

<Path Counting>

 

연못을 피해 H에서 S로 가는 길의 개수는?

H에서 가까운 지점부터 답을 구한 뒤 저장한다. 그 답을 다음 지점의 답을 구하는 데 사용한다.