[Algorithms] 다이나믹 프로그래밍

AllyHyeseongKim·2022년 6월 13일

10870 15624 다이나믹 프로그래밍 백준 알고리즘 코딩테스트 파이썬 피보나치 수열

Algorithms

목록 보기

5/6

Reference

10870번 피보나치 수 5, Baekjoon online judge
15624번 피보나치 수 7, Baekjoon online judge

1. 피보나치 수열

피보나치 수(Fibonacci numbers): 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열.
-Reference. Fibonacci number, Wikipedia

1.1. 피보나치 수열 알고리즘

피보나치 수열을 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

def fibonacci(n: int):
	if n == 0:
    	return 0
    elif n == 1:
    	return 1
    else:
    	return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

>>> 55

1.2. [백준 10870번] 피보나치 수 5

위의 1.1. 피보나치 수열 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def fibonacci(n: int):
	if n == 0:
    	return 0
    elif n == 1:
    	return 1
    else:
    	return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(int(sys.stdin.readline())))

1.3. [백준 15624번] 피보나치 수 7

하지만, 이 문제에서는 $0\leq n\leq 1,000,000$ 이므로 다음과 같은 에러를 띄게되어 1.1. 피보나치 수열 알고리즘을 활용할 수 없다.

RecursionError: maximum recursion depth exceeded in comparison

1.3.1. 분석

파이썬은 기본적으로 1000번까지의 재귀 호출을 허용한다. 따라서, $n \leq 1,000$ 인 피보나치 수열은 재귀 호출을 사용할 수 없다. sys.setrecursionlimit()를 사용하여 재귀의 깊이를 조정할 수 있으나, 이 방법도 메모리 초과 문제로 풀이할 수 없다. 따라서, 이 문제를 해결하기 위해서는 다이나믹 프로그래밍 방법이 필요하다.

2. 다이나믹 프로그래밍

동적 계획법(dynamic programming): 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 해결할 수 있음.
-Reference. Dynamic programming, Wikipedia

Top-down: memoization 방법을 사용함
Bottom-up: Tabulation 방법을 사용함

메모이제이션(memoization): 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 함.
-Reference. Memoization, Wikipedia

1.1. 피보나치 수열 알고리즘과 같이 단순 *재귀 호출로 피보나치 수열**을 연산하는 알고리즘의 시간 복잡도는 $O(2^n)$ 이다.

2.1. Memoization DP (Top-down DP) 알고리즘

이전에 계산한 값을 저장하고 이전에 계산한 값이 있는지 확인
상위 문제부터 확인

Memoization DP (Top-down DP)를 파이썬으로 구현하면 다음과 같다.

def top_down_fibonacci(n: int) -> int:
	if dp_memory[n] == -1:
    	dp_memory[n] = top_down_fibonacci(n-1) + top_down_fibonacci(n-2)
    return dp_memory[n]

dp_memory = [-1] * 100
dp_memory[0] = 0
dp_memory[1] = 1

print(top_down_fibonacci(100))

>>> 354224848179261915075

2.2. Tabulation DP (Bottom-up DP) 알고리즘

하위 문제부터 확인

Tabulation DP (Bottom-up DP)를 파이썬으로 구현하면 다음과 같다.

def bottom_up_fibonacci(n: int) -> int:
    dp_table = [-1] * (n+1)
    dp_table[0] = 0
    dp_table[1] = 1
    for i in range(2, n + 1):
		dp_table[i] = dp_table[i-1] + dp_table[i-2]
    return dp_table

print(bottom_up_fibonacci(1000)[-1])

>>> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

2.3. [백준 15624번] 피보나치 수 7

위의 다이나믹 프로그래밍 알고리즘을 활용하여 문제를 다시 풀어보자.

2.3.1. Memoization DP (Top-down DP) 알고리즘

위의 2.3.1. Memoization DP (Top-down DP) 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def top_down_fibonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    if dp_memory[n] == -1:
        dp_memory[n] = top_down_fibonacci(n-1) % 1000000007 + top_down_fibonacci(n-2) % 1000000007
    return dp_memory[n]

n = int(sys.stdin.readline())
dp_memory = [-1] * (n+1)
dp_memory[0] = 0
dp_memory[1] = 1
print(top_down_fibonacci(n))

하지만, 이 방법도 재귀를 호출하므로 RecursionError가 발생한다. 따라서 이 문제는 Bottom-up 방법을 사용해야한다.

2.3.2. Tabulation DP (Bottom-up DP) 알고리즘

위의 2.3.1. Tabulation DP (Bottom-up DP) 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def bottom_up_fibonacci(n: int) -> int:
    dp_table = [-1] * (n+1)
    dp_table[0] = 0
    dp_table[1] = 1
    for i in range(2, n + 1):
        dp_table[i] = dp_table[i-1] + dp_table[i-2]
    return dp_table

print(bottom_up_fibonacci(int(sys.stdin.readline()))[-1]%1000000007)

하지만, 피보나치 수열을 모두 리스트에 저장하면 메모리 초과가 뜨므로 다음과 같이 풀이해야한다.
이때, 숫자가 커지게되면 연산도 오래걸리므로 시간 초과가 뜰 수 있다. 따라서 수열 계산시 바로바로 $1,000,000,007$ 로 나누어주어야한다.

import sys

def bottom_up_fibonacci(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    fib = []
    fib.append(0)
    fib.append(1)

    for i in range(2, n + 1):
        b = fib.pop()
        a = fib.pop()
        fib.append(b)
        fib.append((a+b)%1000000007)
    return fib.pop()

print(bottom_up_fibonacci(int(sys.stdin.readline())))

AllyHyeseongKim

Backend Developer

이전 포스트

[Algorithms] 우선순위 큐

다음 포스트