[Algorithm] 5. 다이나믹 프로그래밍

1. 다이나믹 프로그래밍 개념

 

개념: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

다이나믹 프로그래밍은 동적계획법이라고 부르고 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어이다.

 

구현: 탑다운과 보텀업 

 

조건:

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

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

 

- 예시1)  피보나치 수열

점화식이란 인접한 항들 사이의 관계식을 의미하고  다이나믹 프로그래밍으로 피보나치 수열 문제를 깔끔하게 계산할 수 있다.

def fibo(x):

    if x == 1 or x==2:

        return 1

    return fibo(x-1) +fibo(x-2)

print(fibo(4))

 

단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게된다.

f(2)가 여러 번 호출되는 중복되는 부분문제 발생 = > 빅오 2^n 제곱 시간 복잡도

 

 

2. 다이나믹 프로그래밍 기법: 메모이제이션

다이나믹 프로그래밍 사용 조건

1) 최적 부분 구조: 큰 문제를 작은문제로 나눌 수 있냐

2) 중복되는 부분문제: 동일한 작은문제를 반복적으로 해결할 수 있냐

- 메모이제이션

: 한 번 계산한 결과를 메모리 공간에 메모하는 기법으로 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 캐싱과 유사

 

- 메모이제이션 방식

1) 메모이제이션 방식에는 탑다운(하향식), 보텀업(상향식)이 있고 다이나믹 프로그래밍의 형태는 보텀업 방식이다.

2) 결과 저장용 리스트는 DP 테이블이라고 부른다

3) 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.

 

- 예시2) 피보나치 수열을 다이나믹 프로그래밍으로 해결(탑다운)

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]

print(fibo(99))

 

- 예시3) 피보나치 수열을 다이나믹 프로그래밍으로 해결(보텀업)

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]

print(d[n])

 

3. 다이나믹 프로그래밍과 분할정복의 차이점

 

1) 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분구조를 가질 때 사용할 수  있다.

2) 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.

3) 다이나믹 프로그래밍 문제에서 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

4) 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

- 분할정복

분할 정복의 퀵정렬을 보면 한 번 기준 원소가 자리를 변경해서 자리를 잡으면 그 기준원소의 위치는 바뀌지 않는다.

분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지않는다.

 

- 다이나믹 프로그래밍

먼저 그리디, 구현, 완전탐색 등의 아이디어로 해결되지않으면 다이나믹 프로그래밍을 고려하자.

재귀함수로 비효율적인 완전탐색 프로그램을 작성한뒤에 탑다운 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용한다.

 

4. 예제

 

- 예제1. 개미 전사들이 얻을 수 있는 식량의 최댓값을 구하는 프로그램

아이디어:

1) 하나하나 따져보고 DP 테이블을 갱신한다.

2) 규칙을 찾는다.

3) 현재식량창고를 털 수 있는지 털 수 없는지를 i-1, i-2를 통해 비교하자

4) ai = max(ai-1, ai-2 + k)

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

 

- 예제2. 1로 만들기 => 연산을 사용하는 횟수의 최솟값

아이디어: 점화식 세우기 1을 빼는 연산을 제외하고는 해당수로 나누어 떨어질 때에 한해 점화식을 적용할 수 있다.

ai = min(ai-1, ai/2,ai/3, ai/5) +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])

 

- 예제3. 효율적인 화폐 구성: m원을 만들기위한 최소한의 화폐 개수

아이디어: 금액 i를 만들 수 있는 최소한의 화폐 개수( 점화식 세우기)

ai-k를 만드는 방법이 존재하는 경우 min(ai, ai-k +1) 

ai-k를 만드는 방법이 존재하지않는경우 ai = INF

ai-k를 만들수 있는경우 거기서 k하나를 얹어서(+1) ai와 ai-k +1을 비교해서 더 적게 쓰는 쪽을 고르면 된다.

n, m = map(int ,input().split())

array =[]

for i in range(n):

    array.append(int(input()))

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:

            d[j] = min(d[j], d[j-array[j]+1])

if d[m] == 10001:

    print(-1)

else:

    print(d[m])          

 

- 예제4. 금광 => 채굴자가 얻을 수 있는 금의 최대 크기 출력

아이디어

array[i][j]: i행 j열에 존재하는 금의양

dp[i][j]: i행 j열까지의 최적의 해

 

dp[i][j]= array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

for tc in range(int(input())):

    n, m = map(int, input().split())

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

    dp = []

    index = 0

    for i in range(n):

        dp.append(array[index:index+m])

        index+=m

   

    for j in range(1, m):

        for i in range(n):

            if i ==0:

                left_up =0

            else:

                left_up =dp[i-1][j-1]

            if i == n-1:

                left_down=0

            else:

                left_down=dp[i+1][j-1]

           

            left= dp[i][j-1]

            dp[i][j] = dp[i][j] +max(left_up, left_down, left)

    result =0

    for i in range(n):

        result = max(result, dp[i][m-1])

    print(result)

 

- 예제 5. 병사 배치하기 => 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치

아이디어: 가장 긴 증가하는 부분수열(LIS)의 변형인 가장 긴 감소하는 부분 수열을 찾는 문제

모든 병사가 내림차순으로 정렬되어야되기때문에 값이 같아서는 안된다. 4,4 같은거는 하나를 제거하고 4보다 작은 것도 제거해줘야지 가장 긴 감소하는 부분수열이된다.

점화식: D[i] = max(D[i], D[j] +1) if array[j] < array[i]

n = int(input())

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

array.reverse()

dp = [1]*n

for i in range(1, n):

    for j in range(0, i):

        if array[j] < array[i]:

            dp[i] = max(dp[i], dp[j]+1)

print(n-max(dp))