dp알고리즘 대표 예제 피보나치 함수 풀기 (파이썬)

저번에 dp알고리즘 공부방법에 대해 글을 쓴 적이 있다.

알고리즘 동적 계획법 (DP) 해결하는 방법 찾기, 공부하는 법

그럼 실제로 어떻게 문제에 적용시키고 풀이하는지 대표적이고 간단한 문제인 피보나치 함수 문제를 풀이하겠다.

백준 dp알고리즘 2748번 피보나치 수 2 문제 바로가기 (https://www.acmicpc.net/problem/2748)

사실 이 문제는 문제에 이미 점화식이 주어져있어서 귀납적 추론이나 이미지로 바꾸어 생각하지 않아도 된다. 이미 주어진 점화식을 그대로 사용해서 풀어보자면,

코드

n = int(input())
dp = [j for j in range(n + 1)]
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])

이렇게 풀이할 수 있다. dp라는 리스트를 생성하고 각각의 인덱스를 수열의 항으로 생각하여 반복문을 사용해 그들 사이의 관계를 정의 한다.

위의 원리를 제대로 알려주는 다음문제를 보자.

백준 dp알고리즘 1003번 피보나치 함수 문제 바로가기 (https://www.acmicpc.net/problem/1003)

문제에 이전 피보나치 수를 출력하는 프로그램에 대한 원리가 담겨있다. 다만 이번에는 그 원리에 등장하는 0과 1을 몇번이나 출력하는지에 대한 문제이다.

코드

T = int(input())
for _ in range(T):
    n = int(input())
    if n == 0:
        print(1, 0)
    elif n == 1:
        print(0, 1)
    else:
        dp = [[1 for j in range(n + 1)] for k in range(2)]
        dp[0][1] = 0
        dp[1][0] = 0
        for i in range(3, n + 1):
            dp[0][i] = dp[0][i - 1] + dp[0][i - 2]
        for i in range(2, n + 1):
            dp[1][i] = dp[1][i - 1] + dp[1][i - 2]
        print(dp[0][n], dp[1][n])

나는 0과 1 둘 다 각각 몇번씩 출력되는지 알아야 하기 때문에 각각의 배열에 넣고 싶어 dp리스트에 2차원 배열을 시켰다. 점화식은 신기하게도 다시 피보나치 수열과 같이 도출되었다. 그래서 이후에는 이전 문제를 풀이한것과 같이 코드를 작성하였다.

dp의 기본적인 예제 문제를 풀어보았는데 이후의 문제들은 많이 응용되고 여러가지 방식이 사용되기 떄문에 아이디어를 내기 힘들다. 항들 사이의 관계를 잘 파악하여 구하고자 하는 항에 대한 관계식을 도출해내는 것이 관건이라 생각한다.