동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic programming)이란 최적의 하위 구조를 가진 문제를 처리하는 중에 반복되는 연산을 최소화하여 효율적인 알고리즘을 작성할 수 있도록 하는 프로그래밍 기법입니다.

 

1. 동적 계획법 유형의 문제인지 확인

• 문제 해결을 위해 완전 탐색 알고리즘을 적용했을 때 비효율적인 경우 내부적으로 동작하는 일련의 반복되는 연산 중 중복되는 동일 연산이 있는지 확인합니다.
• 만약 중복되는 연산이 있다면 연산 결과를 메모리에 임시로 저장하고 이후 동일 연산은 메모리 내에 미리 계산된 값을 사용하도록 코딩하여 효율적인 코드를 작성합니다.
• 중복되는 연산이라 함은 n항의 값을 구하기 위해 n-1항 이하의 연산 결과가 반복적으로 사용되는 것을 말합니다.
  • 예를 들어 f(n) = f(n-1) + 1 또는 f(n) = f(n-1) * f(n-2)와 같은 구조입니다.
• 위와 같이 어떤 문제의 풀이법을 더 작은 문제로 정의하는 것이 최적의 풀이법인 문제의 경우 우리는 최적의 하위 구조를 가졌다고 합니다. 최적의 하위 구조를 가지지 않는 문제는 동적 계획법으로 해결하기 어렵습니다.

★ 간단한 동적 계획법 문제 구별방법

1. 문제를 같은 형태의 하위 문제로 나눌 수 있습니까?
2. 하위 문제의 계산이 반복되나요?
3. 최적화 또는 최대화, 최소화 혹은 특정 작업의 경우의 수를 구하는 유형의 문제인가요?

1, 2번에 해당한다면 동적 계획법을 사용해봅니다. 1, 2번 항목으로 동적 계획법 적용 문제인지 애매한 경우 3번 항목을 참고합니다.

 

 

2. 동적 계획법의 종류

• 하향식(top down)
  • 재귀 함수로 구현된 알고리즘에서 재귀 호출 시 호출에 대한 결과를 한 번도 연산한 적이 없는 경우만 연산을 진행하여 저장합니다.
  • 이후 동일한 재귀 호출이 발생하는 경우는 연산 대신 저장한 데이터를 결괏값으로 사용합니다. (하향식에서 결과를 저장해놓고 연산 대신 사용하는 기법을 메모이제이션이라 합니다.)
  • 처리할 데이터량이 많아지는 경우 stack의 범위를 초과한 재귀 호출로 인해 에러가 발생할 수 있습니다. sys.setrecursionlimit()를 사용하여 어느 정도 해결은 가능하지만 되도록 상향식 동적 프로그래밍을 통해 알고리즘을 작성하도록 합니다.
• 상향식(bottom up)
  • 반복문을 사용하여 작은 연산 단위를 실행하고 그 결과를 DP테이블에 저장합니다.
  • DP테이블에 저장된 결과에 해당하는 연산은 진행하지 않고 DP테이블의 데이터를 그대로 사용합니다.

3. 동적 계획법 적용 단계

 

1. 동적 계획법을 적용할 수 있는 문제인지 확인합니다.
2. 점화식 또는 재귀 과정을 정의 (최적의 하위 구조를 지니고 있는지 확인)
   
   1. 재귀를 사용하여 하향식으로 정의 (이 과정에서는 알고리즘의 시간 복잡도가 높아져도 무시합니다.)
   2. 가장 말단의 재귀호출 시 반환할 값(기초 값)을 지정합니다.
   3. 종료 조건을 추가합니다. 대부분의 종료 조건은 가장 말단의 재귀 호출에서 기초 값을 반환하도록 하는 것입니다.
3. 재귀 호출 시 동일한 하위 계산이 반복적으로 수행되는 경우 메모이제이션 기법을 통해 계산 결과를 메모리에 임시로 저장하고 동일 계산을 필요로 할 때마다 메모리에 저장된 계산 결과를 그대로 사용하도록 수정합니다.
4. 재귀 호출을 제거하고 기초 값 부터 값을 구해가도록 구조를 변경합니다. 이때 문제를 해결하는데 필요한 결과들만 메모리에 저장합니다.

 

 

동적 계획법 첫 번째 예제: 피보나치수열

피보나치 수열이란?

• 1항과 2항의 값은 1이며
• 3항 이후의 모든 n항은 n-2항과 n-1항을 더한 값을 취하는 수열입니다.

위의 알고리즘은 재귀 함수를 사용하여 다음과 같이 간단히 작성해볼 수 있습니다.

n = int(input())
data = [0] * (n + 1)


def fibonacci(data, n):
    if n == 1:
        data[n] = 1
        return 1
    elif n == 2:
        data[n] = 1
        return 1
    else:
        data[n] = fibonacci(data, n - 2) + fibonacci(data, n - 1)
        return data[n]


fibonacci(data, n)
print(data[1:])

위 코드는 n항을 구하기 위해 n-2항과 n-1항을 구해야 하기 때문에 시간 복잡도 O(2^n)에 해당하는 매우 비효율적인 알고리즘이라 할 수 있습니다. 위 코드는 현재 기준으로 낮은 머쉰 파워의 MacBook Pro(13-inch, Late 2011)에서 테스트한 것을  감안하더라도 n = 30과 n = 35일 때 각각 결과 값을 얻는데 까지 소요된 시간은 866ms와 9,362ms로 알고리즘 성능에 엄청난 차이가 있음을 확인해볼 수 있습니다.

 

이 알고리즘은 다음과 같이 일련의 순서대로 동적 계획법을 적용하여 의외로 간단하게 최적화할 수 있습니다.

1. 먼저 결과를 얻기 위해 반복되는 연산을 파악합니다. 여기서는 fibonacci(n) 함수가 연산이 됩니다.
2. 연산 결과를 메모리에 넣습니다. 위의 코드에서는 이미 data라는 list에 각 n항에 대한 연산 결과를 넣고 있으니 동적 프로그래밍에 data를 사용하도록 합니다.
3. fibonacci(n)에 해당하는 결과 값이 이미 data[n]에 존재하는 경우 연산을 하지 않고 data(n)을 사용하도록 코드를 변경합니다.

변형된 코드는 다음과 같습니다.

n = int(input())
data = [0] * (n + 1)


def fibonacci(data, n):
    if n == 1:
        data[n] = 1
        return 1
    elif n == 2:
        data[n] = 1
        return 1
    elif data[n] != 0:
        return data[n]
    else:
        data[n] = fibonacci(data, n - 2) + fibonacci(data, n - 1)
        return data[n]


fibonacci(data, n)
print(data[1:])

재귀 호출을 통한 완전 탐색 문제의 비효율적인 알고리즘을 하향식 동적 계획법을  통해 개선할 수 있었습니다.

 

위의 코드를 반복문을 사용한 상향식 동적 계획법을 적용한 코드로 변경하면 다음과 같습니다.

def fibonacci(data, n):
    data[0] = 1
    data[1] = 1
    for i in range(2, n + 1):
        data[i] = data[i - 2] + data[i - 1]


n = int(input())
data = [0] * (n + 1)
fibonacci(data, n)
print(data)

 

 

동적 계획법 두 번째 예제: 2 등분된 앞과 뒤의 각 요소합이 동일한 부분 문자열 중 가장 긴 부분 문자열의 길이 구하기

• 모든 입력은 자연수 형태의 문자열로 입력됩니다. 
• 입력된 문자열의 부분 문자열을 취하여 2등분 후 앞부분의 모든 숫자합과 뒷부분의 모든 숫자의 합이 동일한 경우 중 가장 긴 문자열의 길이를 구합니다.
• 입출력 예
  • (입력) 142124, (출력) 6
  • (입력) 9430723, (출력) 4

이 문제를 접할 때 기본적으로 떠오르는 풀이법은 완전 탐색을 사용하는 것입니다.

• 조건을 만족하는 최대 부분 문자열 길이를 L이라고 하고 그 값을 0으로 초기화합니다.
• 모든 부분 문자열에 중 짝수의 길이 n인 문자열 S에 대해 로직을 실행합니다.
  • 인덱스 범위 S[0] ~ S[(n - 1) / 2]에 해당하는 요소들의 총 합과  S[(n - 1) / 2 + 1] ~ S[n-1]에 해당하는 요소들의 총합이 동일한 때 
  •  L < n을 만족하는 경우 L = n

코드로 구현해보면 다음과 같습니다.

S = input()
length = len(S)

result = 0
for i in range(0, length-1):
    for j in range(i, length):
        sub_string_length = len(S[i:j + 1])
        if sub_string_length % 2 == 0 and sub_string_length > result:
            middle_index = (i + j + 1)//2
            sub_sum_1 = 0
            sub_sum_2 = 0
            for k in S[i:middle_index]:
                sub_sum_1 += int(k)
            for k in S[middle_index:j + 1]:
                sub_sum_2 += int(k)
            if sub_sum_1 == sub_sum_2:
                result = len(S[i:j + 1])

print(result)

하지만 시간 복잡도가 O(n^3)으로 데이터의 개수가 많아지면 사용하기 부담스러운 알고리즘입니다. 이런 경우 동적 계획법으로 최적화할 수 있는 문제가 아닌지 의심해봐야 합니다.

 

먼저 최적의 하위 구조를 가지고 있는지 확인해보도록 합니다.

 

입력 문자열이 "142124"이고, 인덱스 i부터 j까지의 합을 T(i, j)라고 하면

 

i == j인 경우 즉, 부분 문자열의 길이가 1인 경우의 결과는 다음과 같습니다.

T(0, 0)= 1

T(1, 1) = 4

T(2, 2) = 2

T(3, 3) = 1

T(4, 4) = 2

T(5, 5) = 4

 

i < j인 경우는 다음과 같습니다. (i > j 인 경우는 i < j일 때와 중복되는 정보이므로 무시합니다.)

T(0, 1) = T(0, 0) + T(1, 1) = 1 + 4 = 5

T(0, 2) = T(0, 1) + T(2, 2) = 5 + 2 = 7

T(0, 3) = T(0, 2) + T(3, 3) = 7 + 1 = 8

T(0, 4) = T(0, 3) + T(4, 4) = 8 + 2 = 10

T(0, 5) = T(0, 4) + T(5, 5) = 10 + 4 = 14

T(1, 2) = T(1, 1) + T(2, 2) = 4 + 2 = 6

T(1, 3) = T(1, 2) + T(3, 3) = 6 + 1 = 7

...

T(3, 4) = T(3, 3) + T(4, 4) = 1 + 2 = 3

T(3, 5) = T(3, 4) + T(5, 5) = 3 + 4 = 7

T(4, 5) = T(4, 4) +T(5, 5) = 2 + 4 = 6

이것을 일반화하면 T(i, j) = T(i, j - 1) + T(j, j) (단, i != j) 가 됩니다.

부분 문자열 요소의 합을 구하기 위해 동일 연산이 반복적으로 발생하고 있음을 알 수 있습니다.

또한 부분 문자열 요소의 합을 구하는 데 있어 모든 부분 문자열의 합을 직접 구하는 대신 이전에 이미 구해놓은 더 짧은 길이의 부분 문자열 요소 합을 사용할 수 있으므로 동적 계획법으로 풀기에 적합한 문제임을 알 수 있습니다.

 

위의 내용은 다음과 같이 코드로 구현할 수 있습니다.

import sys

data = sys.stdin.readline().rstrip()

def get_max_len(string):
    full_len = len(string)
    current_max_len = 0	# 현재까지 조건에 부합하는 가장 긴 부분 문자열의 길이입니다.
    dp_table = [[0] * full_len for _ in range(0, full_len)]	# dp table을 만들고 초기화합니다.
    for i in range(0, full_len):	# 길이가 1인 부분문자열에 대한 값을 dp table에 기록합니다.
        dp_table[i][i] = int(string[i])
    for i in range(0, full_len):	# 길이가 2 이상인 부분문자열에 대한 요소의 합을 tp table에 기록합니다.
        for j in range(i + 1, full_len):
            dp_table[i][j] = dp_table[i][j - 1] + dp_table[j][j]
    #dp table을 기준으로 모든 부분문자열에 대해
    for i in range(0, full_len):
        for j in range(i + 1, full_len):
            substring_len = len(string[i:j + 1])
            # 부분문자열의 길이가 짝수이고
            # 부분문자열의 길이가 현재까지 가장 긴 조건에 부합하는 부분문자열 길이보다 길고
            # 부분문자열의 앞 1/2 요소의 합과 뒤 1/2 요소의 합이 동일한 경우
            if substring_len % 2 == 0 and \
                    current_max_len < substring_len and \
                    dp_table[i][(i + j) // 2] == dp_table[(i + j) // 2 + 1][j]:
                current_max_len = substring_len
    return current_max_len


print(get_max_len(data))