알고리즘 스터디 21일차

드디어 왔다 극악무도한 동적 계획법 녀석!

 

목차

1. 동적 계획법 핵심이론

2. 동적 계획법 실전 문제

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 동적 계획법

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결

 

동적 계획법의 원리와 구현 방식

1) 큰 문제를 작은 문제로 나눌 수 있어야 한다.

2) 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

3) 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용한다. (=메모이제이션 기법)

4) 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

 

피보나치 수열을 통해 이해해보자 (D[N] = D[N-1] + D[N-2] 의 점화식을 가지는 수열)

F[1]과 F[0]에 값 저장 후 F[2]구하고 DP테이블에 저장 -> F[3]을 구할때 저장해둔 F[1]과 F[2]를 사용 -> 같은방식으로 DP테이블에 저장되어 있는 값을 리턴 시키면서 반복해 최종적으로 F[5]값을 구함

 

톱-다운 방식으로 구현한 코드

import sys
input = sys.stdin.readline

N = int(input())
D = [-1]*(N+1)
D[0] = 0
D[1] = 1

def fibo(n):
    if D[n] != -1: 
        return D[n]
    D[n] = fibo(n-2) + fibo(n-1)
    return D[n]

fibo(N)
print(D[N])

 

 

2. 동적 계획법 실전 문제

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

1463번: 1로 만들기

문제에서 X에 3가지 연산만 사용하여 1로 만들라고 나와있다.

1) X가 3으로 나누어 떨어지면 3으로 나눈다.

2) X가 2로 나누어 떨어지면 2로 나눈다.

3) 1을 뺀다.

 

D[i] 는 i에서 1로 만드는데 걸리는 최소 연산 횟수 일 때

점화식 구하는 tip : 조합과 마찬가지로 D[10]을 구한다 하면 0~9는 이미 해결되었다고 가정한다. 따라서 10은 -1연산과 나누기2 연산만 가능하므로 D[10] = D[9]+1 과 D[10] = D[5]+1 2가지 경우가 나온다. 따라서 2가지 중 min값을 선택하면 된다.

 

따라서 각각의 점화식을 다음과 같이 도출할 수 있다.

1) if(i % 3 == 0) D[i] = min(D[i], D[i / 3] + 1)

2) if(i % 2 == 0) D[i] = min(D[i], D[i / 2] + 1)

3) D[i] = D[i - 1] + 1

위의 점화식을 이용해 DP테이블 채우기, 따라서 D[10] = 3

해설 코드

import sys
input = sys.stdin.readline
N = int(input())
D = [0]*(N+1) # DP테이블 생성

D[1] = 0 # 초기화 (인덱스:N,값:최소연산횟수)

for i in range(2,N+1):
    D[i] = D[i-1] +1 # 1을 뺄 때(2와 3으로 나누어지지 않는다면 유지)
    if i%2 == 0: # 2로 나눠 떨어질 때
        D[i] = min(D[i], D[i//2]+1) # D[i//2]의 경우의수+1과 위에서 구한 직전경우의수 +1 중 최소 경우의수 선택
    if i%3 == 0: # 3으로 나눠 떨어질 때
        D[i] = min(D[i], D[i//3]+1) # D[i//3]의 경우의수+1과 위에서 구한 직전경우의수 +1 중 최소 경우의수 선택

print(D[N]) # D[N] : N을 1로 만드는데 필요한 최소 연산 횟수

 

 

DP문제는 점화식을 도출해 내는 아이디어가 중요하다는 걸 알게 되었다.

점화식을 만들때는 DP 테이블에서 구하고자 하는 값을 제외한 그전 경우의 수(값)은 구했다고 가정하고 경우의 수를 생각해야 점화식을 만들기 수월하다.