[python] dp 다이나믹 프로그래밍 알고리즘 (dynamic programming)

✅ DP 란?

• Dynamic Programming (동적 계획법) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

✅ 피보나치 수열

• 이전 두 항의 합을 현재의 항으로 설정하는 특징을 가진 수열
• ex > dp= [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...]
• dp[2] = dp[0] + dp[1]
• dp[3] = dp[1] + dp[2]
• 피보나치 수열의 특징 : a[i] = a[i-1] + a[i-2]

 

▶ 원래 알고있던 재귀를 이용한 피보나치 수열 구하기!

def fibo(x):
    #수열의 첫 번째와 두 번째는 1이므로 1을 return 
    if x==1 or x==2 :
        return 1
    else: #수열의 세 번째 부터는 x-1 번째와 x-2 번째 수열의 합을 통해 구할 수 있음
        return fibo(x-1) + fibo(x-2)

 

▶ 단순 재귀함수로 피보나치 수열을 구현했을 시 문제

• fibo(n)의 함수에서 n값이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나게 됨
• 시간복잡도 
• 밑의 사진 처럼 f(2)를 여러번 수행함
• ❗ 중복되는 부분 문제❗

• DP를 이용해 피보나치 수열 계산하기
• DP를 사용할 수 있는 지 조건을 만족하나 확인해야함!
  • 1. 큰 문제를 작은 문제로 나눌 수 있다.
  • 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

✅ Top-Down (탑다운) vs Bottom-Up (바텀업) 방식

• DP 문제를 푸는 방법은 Top-Down (탑다운) 과 Bottom-Up (바텀업) 두 가지이다.

 

✅ Top-Down (탑다운) 

• 큰 문제를 해결하기 위해 작은 문제를 호출함
• 한 번 계산한 결과를 메모리 공간에 메모한다. (Memoization)
• 하향식 방식 ( 위 ➡ 아래 )
• 재귀함수를 사용
• 점화식을 이해하기 쉽다는 장점
• ❗ 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미하므로 DP != 메모이제이션 

#Top-Down 탑다운 방식으로 재귀함수 구현

memoization=[0]*100

def fibo(x):
    if x==1 or x==2:
        return 1
    #이미 계산한 적 있으면 그대로 반환
    if memoization[x] !=0:
        return memoization[x]
    # 계산한 적 없으면 점화식에 따라 피보나치 결과 반환
    memoization[x]=fibo(x-1) + fibo(x-2)
    return memoization[x]
print(fibo(6))

 

✅ Bottom-Up (바텀업)

• 가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는 방식
• 상향식 방식 ( 아래 ➡ 위 )
• 반복문 사용
• 재귀 호출을 하지 않아서 시간과 메모리 사용량을 줄일 수 있다는 장점 

#Bottom-Up 탑다운 방식으로 구현

d=[0]*100

d[1]=1
d[2]=1
n=6

for i in range(3,n+1):
    d[i]=d[i-1]+d[i-2]
print(d[n])

 

✅ Memoization (메모이제이션) 기법

• DP를 구현하는 방법 중 한 종류
• 한 번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법
• (값을 기록해 놓는다는 점에서 캐싱(caching) 이라고도 함

 

✅ DP 기초문제 : BOJ 1463번

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

https://security-ju.tistory.com/296

[python][백준/BOJ] 1463번 : 1로 만들기