알고리즘과 자료 구조 - 다이나믹 프로그래밍 DP

인생노잼시기·2021년 9월 15일

🌲알고리즘과 자료구조 [스위프트]

목록 보기

15/16

다이나믹 프로그래밍 DP

중복되는 연산을 줄이는 방법

언제 사용하나?
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(6))

반복문을 이용한 bottom up 방식

스택 크기가 한정되어 있을 수 있기 때문에 탑다운보다 보텀업 권장

탑다운: 큰 문제를 해결하기 위해 작은 문제를 호출
보텀업: 작은 문제부터 차근차근 답을 도출

피보나치 수열 소스 코드

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫번째 피보나치 수와 두 번째 피보나치 수는 1
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])