6일차 - 다이나믹 프로그래밍

알고리즘 강의 시간에 배웠던 프로그래밍 기법이다.

탑다운과 바텀업 방식이 있고, 이것을 위해 사용하는 메모이제이션 기법이 있다.

 

수학자들은 점화식을 사용해서 수열의 항이 이어지는 형태를 간결하게 표현한다.

우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다.

프로그래밍에서는 점화식에 사용되는 수열을 배열이나 리스트로 표현할 수 있다.

 

다이나믹 프로그래밍은 아래의 조건을 만족해야 사용할 수 있다.

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

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

 

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다.

메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를

그대로 가져오는 것을 의미하는데, 캐싱이라고도 한다.

메모이제이션 기법을 통해서 피보나치 수열을 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))

99번째 피보나치 수인데도 금방 정답이 출력되는것을 확인할 수 있다.

 

DP(다이나믹 프로그래밍)이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

재귀함수, DP에 약한 나는 항상 호출되는 함수를 확인해야 한다고 생각한다.

친절하게도 해당 예제 코드가 있었다.

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)

이처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 탑다운 방식이라고 한다.

메모이제이션 기법도 탑다운 방식이다.

 

작은문제부터 차근차근 답을 도출하는 방식을 바텀업 방식이라고 한다. DP의 전형적인 형태는 보텀업 방식이다.

 

나는 개인적으로 DP가 제일 어렵게 느껴진 알고리즘인데, 이 책에서는 이해하기 쉽게 풀어 작성했다.

 

연습문제 1. 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

1. X가 5로 나누어떨어지면, 5로 나눈다.

2. X가 3으로 나누어떨어지면, 3으로 나눈다.

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

4. X에서 1을 뺀다.

연산을 사용하는 횟수의 최솟값을 출력하는것이 문제이다.

입력으로 26을 준다면

1. 26 - 1 = 25

2. 25 / 5 = 5

3. 5 / 5 = 1, 이렇게 최솟값이 3이다.

처음에 그리디 문제인지 알았는데, 아니다. 점화식을 먼저 표현해야한다.

Ai = min(Ai-1, Ai/2, Ai/3, Ai/5) + 1

(i가 붙은것은 index임)

Ai-1, Ai/2, Ai/3, Ai/5인 경우는 총 4가지이다.

Ai-1 : 현재의 수에서 1을 빼는 경우

Ai/2 : 현재의 수가 2로 나누어 떨어지는 경우

Ai/3 : 현재의 수가 3으로 나누어 떨어지는 경우

Ai/5 : 현재의 수가 5로 나누어 떨어지는 경우

x = int(input())

# 입력범위가 3만이 최대이므로, DP 테이블 30001 초기화
d = [0] * 30001

# DP진행(바텀업)
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 % 2 == 0:  
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])

 

 

연습문제 2. 개미전사

문제 내용은 개미전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

예를들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.

[1, 3, 1, 5]

이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개를 식량을 빼앗을 수 있다.

여기서 개미전사가 얻을 수 있는 식량의 최댓값을 구하라.

 

옆에 한칸만 떨어져있으면 된다.

i번째 식량창고에 대한 최적의 해를 구할 때 왼쪽부터 (i-3)번째 이하의 식량 창고에 대한 최적의 해에 대해서는 고려할 필요가 없다는 점이다.

예를 들어 d[i-3]는 d[i-1]과 d[i-2]을 구하는 과정에서 이미 계산되었기 때문에, d[i]의 값을 구할 때는 d[i-1]과 d[i-2]만 고려하면 된다.

따라서 i번째 식량창고에 있는 식량의 양이 Ki라고 했을때 점화식은 Ai = max(Ai-1, Ai-2+Ki)이다.

 

n = int(input())
arr = list(map(int, input().split()))

d = [0] * 100

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

 

 

연습문제 3. 바닥공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.

이 얇은 바닥을 1 * 2의 덮개, 2 * 1의 덮개, 2 * 2의 덮개를 이용해 채우고자 한다.

경우의 수를 구하라.

 

본 책에서는 왼쪽부터 차례대로 바닥을 덮개로 채웠다.

1. 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 * 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.

2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 * 2 덮개 2개를 넣는 경우, 혹은 2 * 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. 단 2 * 1덮개 2개를 넣는 경우를 고려하지 않는 이유는 1에서 이미 해당 경우가 고려되었기 때문이다.

 

이 문제도 최적의 해를 구할때 왼쪽부터 (i-3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다.

사용할 수 있는 덮개의 형태가 2*2크기의 직사각형 형태이기 때문이다.

점화식은 Ai = Ai-1 + Ai-2 * 2

n = int(input())

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