동적 계획법(DP)

미어캣의 개발일지·2024년 10월 9일

📚 피보나치

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

📕 재귀

처음 문제를 접했을때 당연히 재귀를 쓰면 풀 수 있을거라고 생각해 코드를 구현하였다.

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

def solution(n):
    return fibonacci(n) % 1234567

결과는...?

분명히 논리적으로는 틀린게 없었고 일부긴 하나 몇개의 테스트 케이스는 통과하였다.

그럼 뭐가 문제였을까

실패 메세지를 보면 런타임 에러, 시간 초과 에러가 발생하였다.

이유는 너무나 많은 재귀호출이 되었기 때문이다.

최악의 경우 fibonacci 수열의 트리 구조로 확장하여 총 호출 횟수는 약 2^n

fibonacci(n) 함수의 시간 복잡도는 O(2^n)

대부분의 프로그래밍 언어에는 재귀 호출의 횟수는 제한되어있다.

재귀호출은 함수 호출이 발생할 때마다 함수의 데이터가 콜 스택에 쌓이게된다.

이 콜 스택은 제한된 메모리 공간을 가지고 있기때문에 깊은 재귀 호출이 계속되면 용량을 초과하게 되며 스택 오버플러우 발생하며 런타임 에러가 일어난다.

파이썬은 기본 재귀 한도는 대략 1000번이다.

재귀로 풀기에는 어렵다. 그러면 이를 어떤 방식으로 해결해야할까

📕 동적 계획법(DP)

기존의 재귀로 접근했을때는 중복된 계산이 매우 많이 발생하였다.

f(5)=(f(3)+f(2))+(f(2)+f(1))+f(1)+f(1)

이미 계산했던 f(2)와 f(1)이 여러번 반복해서 호출된다.

이 중복된 계산을 줄이기 위해서는

한 번 계산한 결과는 저장하고 그 결과를 재사용 하는 방법이면 되지 않을까

이 방법이 동적 계획법 (DP)이다.

작은 하위 문제부터 차근차근 해결해가면서 그 결과를 테이블에 저장하고, 상위 문제를 해결할 때 그 값을 참조하는 방식

반복문을 사용하여 작은 문제부터 차근 차근 풀어보자

1. f(0)은 0 f(1)은 1 이므로 f(2)부터 n까지 계산을 한다.

for 문의 range(n)는 0 부터 n-1값 까지 반복하므로 n+1

for i in range(2, n+1)

2. n-2 값과 n-1 값을 저장할 변수가 필요하다.

f(2) 부터 시작시 n-2는 f(0), n-1 는 f(1) 이다.

num = 0
cur = 1

3. 계산 후 값을 저장한다.

cur, num = cur+num, cur

새로운 피보나치 값을 계산하고, 그 값을 업데이트
cur + num은 현재 f(n-1)과 f(n-2) 값을 더한 것, cur에 저장
이전의 cur 값 (즉, f(n-1))을 num에 저장

4. 반복문이 끝난 후 1234567 로 나눈 값 반환

return cur % 1234567

📖 전체 코드

def solution(n):
    num = 0;
    cur = 1;
    
    for i in range(2, n+1):
        cur, num = cur+num, cur
    
    return cur % 1234567

📖 동적 계획법의 장점과 단점

장점:

시간 복잡도 최적화: 중복된 계산을 방지하여 시간 복잡도를 크게 줄임

재귀 호출보다 메모리 절약: 반복을 통한 해결 방식에서는 스택 메모리 문제를 피할 수 있다.

단점:

메모리 사용량: 메모이제이션을 사용하거나 테이블을 만들 때 추가적인 메모리 공간이 필요

문제 구조: 모든 문제에 DP를 적용할 수 있는 것은 아니며, 중복되는 하위 문제가 있는 경우에만 유용

📖 동적 계획법의 대표적인 문제들

피보나치 수열:
DP의 가장 기본적인 문제로, 재귀적 방식보다 효율적으로 계산할 수 있다.

최소 비용 경로 문제:
2D 배열에서 시작점에서 도착점까지의 최소 비용 경로를 찾는 문제.

배낭 문제(Knapsack Problem):
물건의 무게와 가치를 고려해 가방에 넣을 수 있는 최대 가치를 구하는 문제.

최장 공통 부분 수열(LCS):
두 문자열에서 공통된 부분 문자열 중 가장 긴 길이를 찾는 문제.

동전 거스름돈 문제:
주어진 동전으로 특정 금액을 만들 수 있는 최소 동전 수를 구하는 문제.