동적 계획법(DP)

Arin·2025년 11월 14일

[Algorithm] 알고리즘 개념 잡기

목록 보기

6/8

피보나치 수열이란?

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

재귀로 구현한 피보나치(비효율적)

def fib(n):
	if n <= 1:
    	return n
    return fib(n-1) + fib(n-2)

문제점: 중복 호출이 많아서 시간 낭비가 크다
해결책: DP 이용하기!

DP를 구현하는 대표적인 두 가지 방식

1. 메모이제이션(Memoization) - 하향식(Top-down) 접근

재귀 함수 기반
한 번 계산한 하위 문제의 결과를 memo라는 저장 공간(보통 딕셔너리나 배열)에 기록
- if memo에 값이 존재 -> 해당 값 반환
- else -> memo에 값을 저장하고 반환
ex) 피보나치 수열을 Memoization 방식으로 구현


def fibonacci_memo(n, memo = {}):   # 피보나치 수열에서 n번째 항까지의 합 구하기
                                    # memo: 계산 결과값을 저장하는 딕셔너리
                                    # n이 10이면 memo[10] = 55   
    if n <= 1: # 첫번째 값은 1
        return n
    if n in memo: # n번째 항까지의 계산 결과가 memo에 있으면 
        return memo[n] # 저장된 값 반환
    
    else: # 결과가 memo에 없으면 재귀함수 호출
    	memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    	return memo[n]
    
print(f"피보나치 수(10) - 메모이제이션 방식 {fibonacci_memo(10)}") # 55

2. 테이블 방식(Tabulation) - 상향식(Bottom-up) 접근

반복문 기반
가장 작은 하위 문제부터 차례대로 해를 구해 DP 테이블(보통 배열)에 기록

def fibonacci_table(n):
    if n <= 1:
        return n
    
    # 테이블 초기화
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1

    # 하위 문제부터 for문으로 테이블 채우기
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

print(f"피보나치 수(10) - 테이블 방식 {fibonacci_memo(10)}") # 55