[Algorithm]Dynamic Programming알고리즘(Python)

🟠 Dynamic Programming알고리즘

1.DP의 목적

메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도를 개선한다.

--> 메모리를 사용한다 : 배열 혹은 자료구조를 만든다.

--> 중복 연산을 줄인다 : 연산한 결과를 배열에 담는다.

수행시간을 단축시키고자 만든 알고리즘

2.DP문제를 알아보고 구분하는 방법

다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘

1) DFS/BFS로 풀수는 있지만 경우의 수가 너무 많은 문제

2) 경우의 수들에 중복적인 연산이 많은 경우

3.조건

1) 최적 부분 구조(Optimal Substructure) : 큰문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.

2) 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 한다.

ex) 피보나치 수열

EX1) [백준]: 1로 만들기

# 정수 X를 입력 받기
x = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

EX2) [백준]: 개미 전사

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

EX3) [백준]: 효율적인 화폐구성

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])