이것이 코딩 테스트다 - Chapter8 다이나믹 프로그래밍 정리

"다이나믹 프로그래밍"이란

한번에 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

 

즉, 중복 계산하는 비효율적인 방법이 아닌, 한번만 계산하는 효율적인 알고리즘이 되겠다.

 

여기서 그러면 비효율적인 방법에 대한 대표적인 예시로 "피보나치 수열의 재귀함수" 방식을 보겠다.

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

여기서 fibo(4)를 구한다고 보면

fibo(4) = [fibo(3) + fibo(2)]

           = [ [fibo(2) + fibo(1)] + [fibo(1) + fibo(0)] ]

           = [ [ [fibo(1) + fibo(0)] + fibo(1)] + [fibo(1) + fibo(0)] ]

 

즉, 같은연산이 중복된 모습을 볼 수 있다. 이렇게 되면 같은값을 여러번 계산하므로 비효율적이며 시간이 많이 소모된다.

 

이를 해결하고자 나온 개념이 바로 "다이나믹 프로그래밍" 기법이다. "동적 계획법" 이라고 불리기도 한다.

 

다이나믹 프로그래밍을 사용하려면 두가지 조건이 만족되어야 한다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

-> 점화식으로 작성이 가능하다는 점이다.

 

 

다이나믹 프로그래밍에는 크게 2가지 방식이 있다.

 

1. Top down

재귀함수를 활용하여 큰 문제를 해결하기 위해 작은문제를 호출한다.

다만, "메모이제이션" 기법을 활용하여 중복연산은 하지 않는다.

 

여기서 "메모이제이션"은 계산한 값을 리스트에 메모함으로서 중복된 연산을 하지 않고 바로 값에 접근하는 방식이다.

 

위의 비효율적인 피보나치 수열을 Top down의 메모이제이션 기법을 활용하면 이렇게 된다.

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]

간단하게, 계산한 값을 저장할 리스트를 만든다.

계산하기 전에 미리 계산된 값이 있는지 확인만 넣으면 끝이다.

 

 

2. Bottom up

반복문을 활용하여 점화식을 통해 작은문제부터 해결하여 큰문제를 해결한다.

다이나믹 프로그래밍에 주로 사용되는 방식이다. 왜냐하면 점화식이 곧 반복문의 식이 되기 때문이다.

 

이때, 이번에는 "DP테이블"을 사용하게 된다. 사용목적은 메모이제이션과 동일하다.

 

위의 피보나치 수열을 이번엔 Bottom up 방식으로 점화식을 통해 풀어보겠다.

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]

초기 값을 지정한 다음, 반복문을 통해 계속하여 다음값을 계산 후 DP테이블에 저장하는 식이다.

 

 

이렇게 다이나믹 프로그래밍을 통해 효율적인 계산이 가능해진다.

문제를 읽었을 때 완전 탐색 알고리즘이 안되거나 시간이 오래걸리는 경우에

다이나믹 프로그래밍을 확인해보면 되겠다.

 

 

 

다음으로 몇가지 예시문제를 보겠다.

 

정수 X를 입력받아, X를 네가지 연산을 조합하여 1로 만드는 최소회수를 구하자.

1) 5로 나누어 떨어지는 경우 5로 나눈다.

2) 3으로 나누어 떨어지는 경우 3으로 나눈다.

3) 2로 나누어 떨어지는 경우 2로 나눈다.

4) 1을 뺀다.

ex) 26 : 25 -> 5 -> 1 (3번)

 

이러한 문제는 Bottom up 방식이 수월하다.

작은값을 통해 큰값, 즉 1,2... 계산을 통해 X까지 구하는 식이다.

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

계산된 값을 저장하기 위한 DP테이블을 생성하여

먼저 이전값+1로 저장한 다음, 각각 2,3,5로 나뉘는지 여부에 따라 최소값으로 수정을 해주면 되겠다.

 

 

 

 

정수 N을 입력받아 N개의 데이터를 입력받는다. 이때, 데이터에서 인접한 값에는 접근을 할 수 없을 때, 데이터의 합산의 최대값을 구하자.

ex) N = 4, [1, 3, 1, 5] -> 8

 

이문제의 경우 규칙을 잘 찾아 점화식을 세우는게 목표이다. 이를 이렇게 접근하면 되겠다.

1번째 까지의 최대합 Sum[0] = Data[0]

2번째 까지의 최대합 Sum[1]= max(Data[0], Data[1])

3번째 까지의 최대합 Sum[2] = max(Sum[0] + Data[2], Sum[1])

 

이를 통해 i번째 까지의 최대합 Sum[i]의 점화식을 나타낼 수 있다.

Sum[i] = max(sum[i-2] + data[i], sum[i-1])

N = int(input())
data = list(map(int, input().split()))

sum = [0]*100
sum[0] = data[0]
sum[1] = max(data[0], data[1])
for i in range(2, N) :
  sum[i] = max(sum[i-2]+data[i], sum[i-1])

print(sum[N-1])

이러한 점화식 문제의 특징은 i-2 이전 내용은 볼 필요가 없다는 점이다. 이러한 점을 활용하여 큰값을 효율적으로 구할 수 있게 된다.

 

 

 

 

 

바닥의 세로 길이는 2로 고정되어 있다. 이때, 가로의 길이 N을 입력받아 세가지 형태의 타일로 덮을 수 있는 경우의 수를 구하자.

1) 가로 1, 세로 2

2) 가로 2, 세로 1

3) 가로 2, 세로 2

 

이제 이문제의 점화식을 구하자. 이때, 이러한 문제의 특성은 특정범위 이전의 내용은 볼 필요가 없다는 점이 중요하다.

가로 1까지의 경우의 수 d[0] = 1   : 가로1

가로 2까지의 경우의 수 d[1] = 2   : 가로1 * 2 or 가로2

가로 3까지의 경우의 수 d[2] = d[1] + 2*d[0]

 

이를 통해 i-2 이전범위는 볼 필요가 없다는 점을 알 수 있으며, 점화식으로 나타낼 수 있다.

d[i] = d[i-1] + 2*d[i-2]

N = int(input())
d = [0]*1000
result = 1

d[0] = 1
d[1] = 3
for i in range(2, N) :
  d[i] = d[i-1] + 2*d[i-2]

print(d[N-1])

 

 

 

 

화폐의 종류인 정수 N과 합산값인 M을 입력받는다. 그리고 N가지의 화폐값을 입력받았을 때, M값을 구하기 위한 최소한의 화폐개수를 구하자. (다만, 구할 수 없는 값의 경우 -1을 출력한다.)

 

이 문제는 그리디 파트에서 봤던 문제와 유사하지만 전혀다른 문제이다.

그리디 파트의 경우 큰 특징이 하나 있었다. 바로 큰 화폐가 작은화폐의 배수였다는 점이다.

 

지금 이러한 문제의 경우 화폐간의 배수관계가 아니므로 다이나믹 프로그래밍을 통해 풀어야 한다.

 

이 문제 역시 Bottom up 방식을 통해 작은 화폐단위부터 차례로 M값까지 회수를 구한 후, 그다음 화폐부터 min 함수를 통해 값을 조절하는 식으로 접근하면 되겠다.

 

다시말해 구하는 회수 d[j] 는 현재 비교대상 화폐단위인 money[i]를 통해

d[j] = min(d[j], d[j-money[i] + 1) 를 통해 값을 수정해 나가면 되겠다.

N, M = map(int, input().split())
money = []
for i in range(N) :
  money.append(int(input()))

money.sort()

d = [10001]*(M+1)
d[0] = 0

#현재 금액 - 화폐단위 값+1로 수정한다 이때, min 함수를 활용하여 이전값이 없는경우 10001 유지가 된다.
for i in range(N) :
  for j in range(money[i], M+1) :
    d[j] = min(d[j], d[j-money[i]]+1)

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

 

이렇게 다이나믹 프로그래밍에 대해 알아보았다.

 

여기서 제일 중요한 관점은

초기값을 구한다 (i=0, i=1)

점화식 관계를 구한다 d[i] = d[i-1] + d[i-2]

점화식에서 사용되는 특정범위를 찾는다. (i-2)

이렇게 되겠다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/다이나믹%20프로그래밍

CodingTestStudy/FreeDeveloper_Cote