DP(Dynamic Programming) 백준 알고리즘 1003번

♣ DP의 정의

https://jy-deeplearning.tistory.com/65

DP(Dynamic Programming, 백준 알고리즘 14501번)

지난 포스팅 참고!

 

♣ 백준 알고리즘 1003번 문제 이해

 

DP와 재귀함수를 비교하기에 좋은 문제인 피보나치 수를 구하는 문제이다. 

C++ 함수로 짠 피보나치 함수로, 재귀함수를 이용하여 n번째 피보나치 수를 구하고 있다. 

이 문제에서 요구하는 것은 n번재 피보나치 수를 구하는 것이 아니라, fibonacci(1)이 호출된 횟수와 fibonacci(0)이 호출된 횟수를 구하는 것이다. 

 

즉 fibonacci(3) = fibonacci(2) + fibonacci(1)이고, 여기서 fibonacci(2)로 들어가면 fibonacci(2) = fibonacci(1) + fibonacci(0)이다. 따라서 

 

fibonacci(3) = fibonacci(1) + fibonacci(0) + fibonacci(1) 인 셈이고, 따라서 fibonacci(0)은 1번, fibonacci(1)은 2번 호출한 셈이 된다. 따라서 답은 1 2 이다.

 

fibonacci(3)을 구할 때 fibonacci(1)은 2번, fibonacci(0)은 1번 호출됨

 

 

 

♣ 재귀함수 사용

재귀함수를 사용하면 쉽게 풀 수 있을 것 같아서 아래와 같이 코드를 작성하였다. 

 

fibo(0)을 호출할 때마다 zeros에 1을 더하고, fibo(1)을 호출할 때마다 ones에 1을 더한다. 

zeros와 ones를 return하여 프린트하면 답을 구할 수 있다. 

 

예제는 다 맞았는데 시간 초과가 떴다. 

위의 코드를 어떻게 더 단순화해야 하나 고민했는데 질문 게시판에 보니 재귀함수 말고 메모이제이션을 사용하라는 말이 있었다. 

 

 

♣ 메모이제이션? DP?

메모이제이션은 ' 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술' 이다. 즉, DP를 의미한다. 

 

재귀함수를 쓰면 피보나치 수열을 여러 번 계산해야 하니 DP를 써서 시간을 줄이라는 이야기였다. 

그런데 dp를 써서 피보나치 수열을 구하면 아래처럼 코드를 짤텐데

 

 

n번째 피보나치 수는 쉽게 구하겠지만 n번째 피보나치 수를 구하기 위해서 0번째 피보나치 수와 1번째 피보나치 수가 몇 번씩 호출되는지 알 수가 없었다. 그래서 dp 리스트에 n번째 피보나치 수가 아니라 해당 피보나치 수를 구할 때 0번째 피보나치 수와 1번째 피보나치 수가 몇 번씩 나오는지를 튜플 형태로 집어넣기로 했다. 

 

예를 들어 n=0 이면 0번째 피보나치 수를 구하는 것이므로 0번째 피보나치 수는 1번, 1번재 피보나치 수는 0번 나온다. 그러면 dp 리스트의 0번째 원소에 (1, 0)을 넣는다. 이런 식으로 0번째 피보나치 수와 1번째 피보나치 수를 늘려가며 저장한다. 

 

dp[0]과 dp[1]은 dp에서 가장 작은 기저 부분에 해당한다. 

n이 2 이상일 때부터 dp 리스트를 채워간다. 위의 dp[i] = dp[i-1]+dp[i-2]처럼 dp[i] = (dp[i-1][0]+dp[i-2][0], dp[i-1][1]+dp[i-2][1]) 를 이용하여 0번째 피보나치 수가 몇 번 나오는지, 1번째 피보나치 수가 몇 번 나오는지 구할 수 있다. 

이렇게 코드를 짜니 시간 초과 없이 통과되었다. 

 

*아직 두 가지 요소를 모두 고려하는 dp 문제는 잘 이해가 안 된다. 조금 더 급이 높은 dp 문제를 풀어보아야 한다.