이것이코딩테스트다 | Ch08 다이나믹 프로그래밍

Date | 2021.07.17
Review | 다이나믹 프로그래밍 기법을 처음 접해봤는데 너무 간단하면서도 효율적인 것 같아서 좋았다. 다만 활용한 문제들의 난이도는 별로 좋지 않았다 ,, 마지막 화폐 구성하는 예제는 두고두고 봐야할 것 같다 어려받용ㄹ

1️⃣ 다이나믹 프로그래밍

# 다이나믹 프로그래밍 Dynammic Progrmming
# 동적 계획법
## 탑다운 / 보텀업

### 8-01.py ###
### 피보나치 함수 소스코드 ###

# 피보나치 함수 (Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
  if x == 1 or x==2:
    return 1
  return fibo(x-1)+fibo(x-2)

print(fibo(4))

 

탑다운방식 | 큰 문제를 해결하기 위해 작은 문제를 호출
메모이제이션 기법 Memoization
# 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

### 8-02.py ###
### 피보나치 함수 소스코드 - 재귀적 ###

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수 (Fibonacci Function)를 재귀 함수로 구현
## 탑다운다이나믹프로그래밍
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))

### 8-03.py ###
### 호출되는 함수 확인 - 피보나치 함수###

d = [0] * 100

def pibo(x):
  print('f('+str(x)+')',end=' ')
  if x == 1 or x==2:
    return 1
  if d[x] != 0:
    return d[x]
  d[x] = pibo(x-1) + pibo(x-2)
  return d[x]

pibo(6)

 

보텀업방식 | 단순히 반복문을 이용하여 소스코드를 작성하여 작은 문제부터 차근차근 답을 도출
= 다이나믹 프로그래밍의 전형적인 형태

### 8-04.py ###
### 피보나치 수열 - 보텀업 방식###

# 앞서 계산된 결과를 저장히기 위한 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])

 

2️⃣ [실전문제] 1로 만들기

### 8-05.py ###
### [실전] 1로 만들기 ###

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

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

# 다이나믹 프로그래밍 진행 (보텀업)
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])

 

3️⃣ [실전문제] 개미 전사

### 8-06.py ###
### [실전] 개미전사 ###

# 정수 n 입력받기
n = int(input())

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

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

# 다이나믹 프로그래밍 진행 (보텀업)
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])

 

4️⃣ [실전문제] 바닥 공사

### 8-07.py ###
### [실전] 바닥 공사 ###

# n 입력받기
n = int(input())

# dp테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n+1):
  d[i] = (d[i-1] + 2*d[i-2]) % 796796

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

 

5️⃣ [실전문제] 효율적인 화폐 구성 🤯

### 8-08.py ###
### [실전] 효율적인 화폐 구성 ###

# n, m 입력받기
n, m = map(int, input().split())

# n개의 화폐 단위 정보 입력받기
array = []
for i in range(n):
  array.append(int(input()))

# dp 테이블
d = [10001] * (m+1)

# 다이나믹 프로그래밍 - 보텀업
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])