[이코테/python] 다이나믹 프로그래밍 개념 정리 & 문제 풀이 기록 ➕ 백준 dp 문제 풀이

DP

 

DP는 한번 해결한 문제는 다시 계산하지 않도록 한다.

 

메모리 공간이 필요할 때마다 프로그램이 실행되는 도중에 필요한 메모리를 할당하는 것이 자료구조에서의 다이나믹의 의미!

 

피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제

 

점화식은 재귀함수형태로 구현 가능

앞 두개의 항을 더하여 그 다음 항을 만든다.

f(3)을 호출할 때 f(2)와 f(1)을 호출한 결과를 더해서  구할 수 있다.

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

print(fibo(4))


# 재귀함수를 만들 때해는 무한 반복하지 않도록 종료조건을 적어줘야한다! 
# x 가 1 또는 2일 때가 종료 조건이다.

점화식 부분이 재귀식, a1과 a2이 종료조건이 된다.

 

 

f(6)을 호출했을 뿐인데 f(2)가 5번 호출되고 있다. -> 수행 시간 비효율 

따라서 한번 해결한 f(2)에 대해서 이 문제의 답은 이거라고 알려줄 수 있도록 해야 한다

 

.

 

다이나믹 프로그래밍 문제 해결 방법 (하향식)

배열 이름을 cache, table ,dp, d라고 설정하곤 한다.

상향식은 반복문을 해결한다. 

dp를 해결하는 방법 중 하향식으로 접근할 때 메모이제이션 방법을 사용할 수 있다.

 

피보나치 수열 탑다운 메모이제이션 방식 구현 

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

# 피보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)

def fibo(x):

  # 종료 조건 (1 또는 2일 때 1 반환)
  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))

 

피보나치 수열 바텀업 방식 구현

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

 

---

 

지수 시간만큼 걸리던 피보나치 수열 문제의 시간 복잡도를  O(N) 만큼 줄일 수 있다.

---

 

피벗을 5로 설정 후 퀵 정렬을 수행하면 5보다 작은 원소와 5보다 큰 원소로 분리된다.

이렇게 한번 분할이 이루어진 이후 5에 대해서는 이제 처리되지 않는다. 다른 부분 문제에 포함되지 않는다.

---

- 작은 문제를 통해 큰 문제를 해결

- 부분 문제가 중복

 

-> 다이나믹 프로그래밍으로 접근

---

1️⃣실전 문제 1  : 1로 만들기

 

연산의 최솟값을 구하는 문제이다.

단순히 5로 나누기, 3으로 나누기, 1을 빼주는 연산을 반복하는 것이 아니라 입력된 값에 따라서 입력값을 1로 만드는 연산의 최솟값을 구해야하는 문제였다.

 

다이나믹 프로그래밍을 이용해서 

입력값이 1일 때부터 

 

 

초기 코드다.. 어떤 방식으로 풀어야할지 감이 잘 잡히지 않았다.

n = int(input().split())
count =0
def fibo(x):
  while(True):
    if x==1:
      return count 
    elif x % 5 ==0:
      count +=1
      x = x//5
    elif x % 3==0:
      count +=1
      x = x//3
    else:
      count +=1
      x -=1
  
fibo(n)

 

 

최종 코드는 아래와 같다.

 

만약 2로 나누어 떨어지는 경우 1을 뺀 경우의 연산 횟수가 저장된 d[i]와 d[i//2] + 1을 비교하여 더 작은 방법을 선택한다는 아이디어이다.

 # 1을 뺀 경우 연산 횟수
 d[i] = d[i-1]  +1
 
 # 2로 나누어 떨어지는 경우
  if i%2 ==0:
    d[i] = min(d[i],d[i//2]+1)

 

 

전체 코드

x = int(input())

d = [0] * 30001

for i in range(2,x+1):
 
  d[i] = d[i-1]  +1
  if i%2 ==0:
    d[i] = min(d[i],d[i//2]+1)

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

---

2️⃣실전 문제 2 :개미 전사 문제 풀이 과정

🐜🐜

 

아직 문제 풀이를 어떻게 해야할지 바로 떠오르지 않는다. 풀이를 보고 dp 문제에 익숙해지자! 

n = int(input())

array = list(map(int,input().split()))

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

 

 🫱경우의 수 

 

   i-2 i-1 현재

ㅁㅁ ㅁ ㅁ

1 ) i-2번째 식량을 턴다면 : 현재 식량을 털 수 있다.

2) i-1번째 식량을 턴다면 : 현재 식량을 털 수 없다.

 

즉 i-2번째 식량 + 현재 식량 VS i-1 번째 식량 중 더 많은 식량을 털 수 있는 경우를 선택하면 된다.

 

🫱구현 요소

d는 더 많은 식량을 털 수 있는 경우가 저장된 dp 테이블이다. 

인덱스에 따라서 차례대로 현재 인덱스까지 중 가장 식량을 많이 털 수 있는 방법이 선택된다.

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

---

3️⃣실전 문제 3 : 바닥 공사 

* 타일링 문제 

 

구하고자 하는 것 : 가로 * 세로 = N * 2 인 바닥을 채우는 모든 경우의 수 

출력 : 바닥을 채우는 방법을 796796으로 나눈 나머지 

n = int(input())

d = [0] * 1001

d[1]= 1
d[2]=3


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

print(d[n])

 

근데 코드가 이해가 안된다.

 

d[1] 은 1가지 경우

d[2] 은 3가지 경우가 있다.

 

d[3] 은 d[2] + d[1] * 2   = 5가지 경우의 수를 가진다.

 

d[4] 는 d[3] + d[2] * 2  =11가지 의 경우의 수를 가진다. 

 

이해가 안갔던 부분은 2칸이 남았을 때 가로 * 세로 = 1*2 인 타일 2개로도 구성할 수 있는데 왜 이건 고려하지 않을까? 싶었는데 이건 1칸이 남은 경우에서 고려되는 것이었다. 구성되는 타일 형태가 동일하므로 여기서 고려되는 것이었다! 🤗

---

4️⃣실전 문제 4 : 효율적인 화폐 구성 문제 풀어보기

으아..... dp 문제는 어떻게 풀어야할지 혼자서는 아직 감이 안잡힌다. 문제 풀이를 단계별로 정리해보자!!! 

 

예를 들어 N = 3이고 K= 7이라고 생각해보자 ! 여기서 K는 화폐의 단위를 의미한다.

각 화폐의 단위는 2, 3, 5이다.

🫱 경우의 수

금액 i를 만들 수 있는 화폐 개수 ai, 화폐 단위 k라고 할 때

a i-k는 금액 i-k를 만들 수 있는 최소한의 화폐 개수 

 

ai-k 를 만드는 방법이 존재할 경우 : a i = min(ai, ai-k + 1)

- ai-k는 a[i]에 금액 k를 하나 더하면 만들 수 있다.

존재하지 않는 경우 : ai = 10,001

🫱초기 리스트 설정하기 

각 인덱스를 10,001로 설정한다. 

우리 문제에서 금액의 최대값은 10,000이다. 따라서 10,001은 불가능한 금액이다. 즉, 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다.

0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 0인덱스 값으로 0을 설정한다.

 

🫱화폐 단위 확인하기 

현재 연산에서 가장 최소의 값으로 만드는 연산을 선택하면 된다. 

따라서 가장 최소로 만드는 연산은 선택하고 이를 반복해서 수행하면 된다.

 

가장 먼저 첫 번째 화폐단위인 2부터 확인해보자.

2로 만들 수 있는 수부터 dp 테이블을 갱신하기

 

인덱스 2의 경우 1이라는 값을 가지는데 이는 2원 짜리 화폐 하나를 이용하여 2원을 만들 수 있다는 의미이다. 

인덱스 4의 경우 2라는 값을 가지는데 이는 2원 짜리 화폐 2개를 이용하여 2+2 = 4원을 만들 수 있다는 의미이다.

몇 인덱스는 10,001 값을 가지는데, 이는 2원으로 구성할수 없는 금액이기 때문이다.

 

A2 = A0 + 1

A4 = A2 + 1

 

이제 화폐 단위 3을 확인해보자

2와 3으로 만들 수 있는 수부터 dp 테이블을 갱신하기

 

A5 = A2 + 1

인덱스 5는 2라는 값을 가지는데 이는 2원짜리 화폐 1개, 3원짜리 화폐 1개로 2 + 3 = 5원을 만들 수 있다는 의미이다.

 

이제 화폐 단위 5을 확인해보자

2, 3, 5로 만들 수 있는 수부터 dp 테이블을 갱신하기

 

A 7 = A2 + 1로 2라는 값을 가진다. 2원짜리 화폐 하나랑 5원짜리 화폐 1개로 2 + 5 = 7원을 만들 수 있다는 의미이다.

원래 이전 단계에서 A7의 값은 3이었늗네, 이는 2 + 2 + 3 = 7원으로 3개의 화폐를 사용했을 때를 나타낸 것이다.

 

그러나 2 + 5 = 7원을 만들면 화폐를 2개만 사용해도 되므로 갱신된다.

 

결과적으로 7원을 만들기 위한 최소의 화폐 개수는 2개이다.

 

# 입력받기
n,m = int(input().split)
n_list=[]

for _ in range(n):
  n_list.append(int(input().split()))

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

# dp 구현

d[0]= 0
for i in range(n):
  for j in range(n_list[i] , m + 1):
    if d[j - n_list[i]] != 10001:
      d[j] = min( d[j], d[ j - n_list[i] ] +1)

if d[m] == 10001:
  print(-1)
else:
  print(d[m])

 

 

이 로직을 다시 이해해보자 ! ! ! 

 

위에서 알아본 것처럼 화폐 단위 별로 dp 테이블갱신

for i in range(n):
  for j in range(n_list[i] , m + 1):
    if d[j - n_list[i]] != 10001:
      d[j] = min( d[j], d[ j - n_list[i] ] +1)

 

여기서 d[j - n_list[i]] 와 n_list[i]를 더하면 원하는 금액이 된다

따라서 d[j]와 이전 금액에 금액을 더해서 얻은 수 중 작은 것을 택하면 된다.

---

백준의 1,2,3 만들기 문제 풀어보기 

https://www.acmicpc.net/problem/9095

 

test = int(input())

def sum_func(x):
  if x==1:
    return 1
  elif x==2:
    return 2
  elif x==3:
    return 4
  else:
    return sum_func(x-1) + sum_func(x-2) + sum_func(x-3)
  
                             
for _ in range(0,test):
  n = int(input())
  print(sum_func(n))

 

규칙을 찾아내는 것이 중요하다. 그리고 이전 결과를 어떻게 사용할 수 있는지 잘 생각해보자.

규칙을 모를 때에는 한번 n = 1일 때 2일 때를 생각해보며 나열해보자 

n=4인 경우

1, 2, 3을 더해서 나타내려면 경우는 아래 3가지 케이스로 나뉜다. 

 

1 + 3

1에 3을 더하는 경우의 수는 3을 구성하는 경우의 수와 동일하다 

여기서는 1 + 1+ 1 , 1 + 2, 2 + 1 , 3 으로 4가지 경우가 있다.

 

2 + 2 

2에 2을 더하는 경우의 수는 2을 구성하는 경우의 수와 동일하다 

여기서는 1 + 1, 2 로 2가지 경우가 있다.

 

3 + 1

3에 1을 더하는 경우의 수는 1을 구성하는 경우의 수와 동일하다  

여기서는 1로 1가지 경우가 있다.

 

 

이렇게 작성해보니 각 경우마다 규칙을 알 수 있었다.

4를 구성하는 경우의 수는 3을 구성하는 경우의 수 + 2를 구성하는 경우의 수 + 1을 구성하는 경우의 수 로 표현되었다.

5를 구성하는 경우의 수도 4를 구성하는 경우의 수 + 3을 구성하는 경우의 수 + 2를 구성하는 경우의 수로 표현되었다.

 

따라서 x라는 합을 구성하는 경우의 수는 아래와 같이 표현할 수 있다.

sum_func(x-1) + sum_func(x-2) + sum_func(x-3)