[Algorithm] Week 7. 다이나믹 프로그래밍

다이나믹 프로그래밍

중복되는 연산을 줄이자

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있음.

대표적인 방법이 다이나믹 프로그래밍

 

---

ex) 피보나치 수열

재귀함수를 통해 구현한 피보나치 수열

• fibo(x) 함수에서 x가 커지면 수행 시간이 기하급수적으로 늘어남.

시간복잡도: O(2^n)

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

 

==> 이때 사용해야 할 방법? 다이나믹 프로그래밍

 

 

---

다이나믹 프로그래밍 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

메모이제이션(캐싱) 기법을 사용하여 피보나치 수열을 해결해보자.

- 리스트에 저장하여 값을 저장하기

시간복잡도: O(N)

d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

 

---

다이나믹 프로그래밍 작성법

탑다운 방식 (하향식)

큰 문제를 해결하기 위해 작은 문제를 호출함. ex) 재귀 함수 이용

 

 

보텀업 방식 (상향식)

작은 문제부터 차근차근 답을 도출함. ex) 반복문 이용

다이나믹 프로그래밍의 전형적인 형태!!

 

보텀업 방식 예시

d = [0] * 100	# DP 테이블

d[1] = 1
d[2] = 1
n = 99

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

print(d[n])

 

DP 테이블: 보텀업 방식에서 사용되는 결과 저장용 리스트

(메모이제이션 - 탑다운 방식에 국한되어 사용되는 표현임)

 

---

문제 풀이 단계

 

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하기
   : 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인하기
2. 메모이제이션을 통해 코드 개선이 가능한지 확인하기
3. 탑다운 방식보다는 보텀엄 방식으로 구현하는 것을 권장함.
   : 재귀 함수의 스택 크기가 한정되어 있을 수 있음.