[이것이 코딩테스트다] 6. DP

해당 강의를 참고하여 공부를 진행했습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

---

DP(Dynamic Programming)

• 탑다운(하향식), 보텀업(상향식)
• 동적: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법
  • 그러나, DP에서 별다른 의미 없이 사용된 단어임

조건

1. 최적 부분 구조: 큰 → 작은 문제, 그러므로 작은 문제를 모아 큰 문제를 해결 가능
2. 중복되는 부분 문제

 

피보나치 수열: 단순 재귀 소스코드

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

print(fibo(4))

그러나, 

f(2)가 여러 번 호출되는 것을 확인할 수 있다.

 

피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드

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))

 

피보나치 수열: 보텀업 다이나믹 프로그래밍 소스코드

d = [0] * 100

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 vs. 분할 정복

• 분할은 피벗을 변경하면 그 기준에 있는 숫자의 변화 x
• 그리디, 구현, 완전 탐색 → 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 DP 고려 가능
• DP는 전형적인 문제 유형만 알면 문제 없음

 

[문제] 개미 전사

n = int(input())
arr = list(map(int, input().split())) # [1, 3, 1, 5]

d = [0] * 100

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

print(d[n-1])

 

[문제] 1로 만들기

x = int(input())

d = [0] * 30001

for i in range(1, x+1):
    d[i] = d[i-1] + 1

    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    elif i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    elif i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])