[알고리즘] 6. 다이나믹 프로그래밍

/* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */

 

 

1. 다이나믹 프로그래밍

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과 (작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 (탑다운 - 하향식, 보텀업 - 상향식)으로 구성된다.

 

- 다이나믹 프로그래밍은 동적 계획법이라고도 부른다.

- 일반적인 프로그래밍 분야에서의 동적 (Dynamic)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.

- 반면에, 다이나믹 프로그램에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.

 

 

 

2. 다이나믹 프로그래밍의 조건과 종류

- 다이나믹 프로그래밍은 문제가 다음의 두 조건을 만족할 때 사용할 수 있다.

1) 최적 부분 구조 (Optimal substructure) :

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2) 중복되는 부분 문제 (Overlapping subproblem) :

동일한 작은 문제를 반복적으로 해결해야 한다.

 

 

※ 메모이제이션 (Memoization) : 

다이나믹 프로그래밍을 구현하는 방법 중 하나

 

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법

- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

- 값을 기록해 놓는다는 점에서 캐싱 (Caching)이라고도 한다.

- 한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

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

 

 

 

3. 피보나치 수열 구현

- 피보나치 수열을 우리가 익숙한 단순 재귀 코드로 구현해보면 다음과 같다.

def Fibo(i):
    if i <= 2:
        return 1
    else:
        return Fibo(i-2) + Fibo(i-1)


fibo = int(input())
result = Fibo(fibo)

print(result)

- 피보나치를 위와 같이 재귀함수로 구현하면 최대 지수 시간 복잡도를 갖는다. O(2^N)

- 중복되는 부분이 문제가 된다. 예를 들어서 f(6)을 구하려면 f(2)를 5번 구해야 한다.

- 심한 경우, 빅오 표기법을 기준으로 f(30)을 계산하기 위해서는 약 10억번 가량의 연산을 수행해야 한다.

 

- 피보나치 수열은 최적 부분 구조, 중복되는 부분 문제 두 조건을 모두 만족한다.

- 최적 부분 구조 : 피보나치 6을 구하기 위해서 6보다 작은 숫자들에 대한 피보나치 수열 값도 알아야 한다.

- 중복되는 부분 문제 : 위에서 말한 대로, f(6)을 구하려면 f(2)를 5번 구해야 한다.

 

 

- 피보나치 수열을 다이나믹 프로그래밍 (탑다운)으로 구현해본다.

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

평소에 재귀 함수로 구현한 방식과 비슷하지만 리스트 d로 연산된 결과를 저장해놓았다는 점이 다르다고 할 수 있다.

 

 

- 피보나치 수열을 다이나믹 프로그래밍 (바텀업)으로 구현해본다.

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

원하는 값에서의 피보나치 수를 알기 위해서 그 전까지 구해두어야 할 연산을 다 해주고 그 결과값을 d 리스트에 저장한다.

 

 

 

4. 다이나믹 프로그래밍 vs. 분할 정복

- 공통점 :

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

- 차이점 :

부분 문제의 중복 - 다이나믹 프로그래밍은 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. 하지만, 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

 

 

5. 다이나믹 프로그래밍 문제에 접근하는 방법

- 일단 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.

- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토해봐야 한다.

- 다른 알고리즘으로 풀이 방법이 생각나지 않는다면 다이나믹 프로그래밍 알고리즘을 고려해본다.

 

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

 

- 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.

 

 

 

6. 문제 (1)

개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량 창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량 창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다.

 

< 정답 코드 >

N = int(input())
foods = list(map(int, input().split()))
sum = 0

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0]*100

# 다이나믹 프로그래밍 진행 (보텀업)
d[0] = foods[0]
d[1] = max(foods[0], foods[1])

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

print(d[N-1])

< 출력 >

4

1 3 1 5

8

 

< 해설 >

- (i-1)번째 식량 창고를 털면 연속해서 창고를 털 수 없으므로 현재의 값이 a_(i-1)이 된다.

- (i-2)번째 식량 창고를 털면 현재 식량을 털 수 있으므로 현재의 값이 a_(i-2) + (지금 위치의 식량)

- 둘 중 큰 값이 현재의 값이 되므로, max 함수를 사용하여 비교한다.

 

 

 

7. 문제 (2)

정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지입니다.
1. X가 5로 나누어 떨어지면, 5로 나눕니다.
2. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
3. X가 2로 나누어 떨어지면, 2로 나눕니다.
4. X에서 1을 뺍니다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 합니다. 연산을 사용하는 횟수의 최솟값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다.
26 -> 25 -> 5 -> 1

 

< 정답 코드 >

x = int(input())
d = [0] * 30001

# 다이나믹 프로그래밍 진행 (보텀업)
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 % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])

< 출력 > 

26

3

 

< 해석 >

- 이 문제는 무조건적으로 나누기를 많이 한다고 해서 연산이 최소가 되는 것이 아니다. 네가지의 연산을 적절하게 조화해서 더 작게 만드는 것이 포인트이다.

- 피보나치의 트리 구조를 떠올린다면 도움이 될 것이다.

- 1을 빼는 경우는 모든 수에 대해서 공통적으로 수행되는 연산이기 때문에, 1을 뺀 값으로 일단 갱신을 해두고, 각각 2로 나눌 수 있는 수, 3으로 나눌 수 있는 수, 5로 나눌 수 있는 수로 나누어서 비교연산을 진행한다.

- 이때, if ~ elif로 구성하면 안된다. 예를 들어서 30 같은 경우 2와 3, 5의 배수이므로 모든 경우를 다 비교해보아야 하기 때문이다.

 

 

 

8. 문제 (3)

n X m 크기의 금광이 있습니다. 금광은 1 X 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어있습니다. 채굴자는 첫번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

< 정답 코드 >

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)

< 출력 >

2 

3 4

1 3 3 2 2 1 4 1 0 6 4 7

4 4

1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

------------------------------------------

19

16

 

< 해설 >

- 금광의 모든 위치에 대하여 1) 왼쪽 위에서 오는 경우 2) 왼쪽 아래에서 오는 경우 3) 왼쪽에서 오는 경우

- 세가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결한다.

 

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

- 리스트의 범위를 벗어나지 않는지 꼭 체크해주어야 한다.