[알고리즘, Python] 프로그래머스 고득점 Kit - Dynamic Programming

이미 진행되었던 연산이라면 기록되어 있는 값을 호출

→ 해결한 문제를 반복적으로 해결하는 분할 정복과는 달리, 더욱 효율적

 

ex. 피보나치 수열

피보나치 수열 점화식

 

재귀풀이 ($O(2^n)$)

def fibonacci_recur(n):
	if n >= 2:
    	return fibonacci_recur(n-1) + fibonacci_recur(n-2)
    else:
    	return n

n = int(input("n값을 입력하세요"))
print(fibonacci_recur(n))

 

1. Memoization (Top-down, 하향식)

memoization이란 한번 구한 계산 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

→  재귀함수 이용하여 구현 가능

# 한번 계산된 결과를 메모이제이션 하기 위한 리스트
memo = [0]*100

def fibo(x)
	# F_1 = F_2 = 1
	if x==1 or x==2:
    	return 1
    
    if memo[x] != 0: # 이미 계산한 적 있는 문제이면 그대로 반환
    	return memo[x]
        
    memo[x] = fibo(x-1) + fibo(x-2) # 아직 계산 안 했다면 점화식에 의해 결과 반환
    return memo[x]
    
print(fibo(99))

if memo[x]가 0이면 fibo(x-1)+fibo(x-2)를 하는 식으로 해도 됨

 

2. Tabulation (Bottom-up, 상향식)

tabulation이란 하위 문제부터 하나한 테이블을 채워가므로써 더 큰 문제를 해결하는 기법

→ DP의 전형적인 형태로, 반복문을 이용하여 구현할 수 있음

 

풀이 1

def fib_tab1(n):
	dp_tab = [0]*n+1 # 저장할 리스트
    dp_tab[0], dp_tab[1] = 1, 1
    
    for i in range(2, n+1):
    	dp_tab[i] = dp_tab[i-1] + dp_tab[i-2]
    
    print(dp_tab)
    return dp_tab[n]

fib_tab(10)

"""
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
output: 89
"""

풀이 2

def fib_tab2(n):
	p=[1,1]
    for i in range(2, n+1):
    	p.append(p[-1]+p[-2]) # 마지막 2개 요소의 합을 리스트에 추가
        print(p)
    
    return p[-1]
    
fib_tab2(10)
"""
output: 89
"""

 

⇒ 동적 계획법은 최적성의 원리를 만족할 때 사용 (부분해가 전체 문제의 해를 구하는데 사용되는지)

⇒ 동적 계획법 vs 분할 정복

    동적 계획법: 소문제 종속적(원소들이 종속적) vs 분할 정복: 소문제 독립적(다른 원소들의 영향을 미치지 x)

---

프로그래머스 문제

사칙 연산 (Lv.3)