다이나믹 프로그래밍 - 한 번 계산한 문제는 다시 계산 안한다!

다이나믹 프로그래밍(동적 계획법) 이란 ?

    : 컴퓨터 연산을 하면서 중복되는 연산을 줄이자는 목적으로 나온 기법이다. 보통, 다이나믹이라고 하면 '프로그램이 실행되는 도중에' 라는 의미로 쓰이는데(ex.동적할당), 여기서는 그런 의미는 아니다. 연산을 줄이자는 것이 목적이라면, 재귀함수로 프로그램을 짤 수도 있는 것 아니냐고 생각할 수 있다. 물론, 할 수는 있다. 하지만, 수가 크다면, 실행시간은 기하급수적으로 늘어나기 때문에, 계속해서 재귀함수를 호출하는 것은 컴퓨터에 많은 부하를 줄 수 있다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면, n이 100 이기만 해도, 연산 횟수가 약 1,000,000,000,000,000,000,000000,000,000번이다. 즉, 1초에 1억번 정도의 연산을 한다고 해도, 수백억년이 넘어간다. 

    이렇게, 단순히 매번 계산하도록 하면, 문제를 효율적으로 해결할 수 없기 때문에, 나온 방법이 다이나믹 프로그래밍인 것이다. 다이나믹 프로그래밍의 2가지 방식으로는 탑다운 방식(top-down)과 바텀업 방식(bottom-up)이 있으며, 메모제이션 기법 또한 활용된다.

    먼저 다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

※ 메모제이션 기법이란?

    - 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱(Caching)이라고도 한다.

이런, 메모제이션 기법은 한 번 구한 정보를 리스트에 저장함으로써 구현할 수 있다. 피보나치 수열을 예로 들어, 코드로 구현해보자면 아래와 같다.

# 메모제이션을 위한 리스트 초기화
memo = [0]* 100

# 피보나치 함수를 재귀함수로 구현(top-down 방식으로)
def fibo(n):
    if n == 1 or n == 2 :
    	return 1
    # 이미 계산한 적이 있다면, 그대로 반환
    if memo[n] != 0:
    	return memo[n]
    # 아직 계산하지 않았다면,
    memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

print(fibo(99))      #   218922995834555169026

99번째 피보나치 수를 구하려고 했음에도, 바로 계산되어 값이 나오는 것을 확인 할 수 있다. 다이나믹 프로그래밍을 적용한 피보나치 수열 알고리즘의 시간복잡도는 O(N) 이라는 것을 알 수 있는데, f(1) 을 구하고, 그 값이 f(2)를 푸는데 사용되고, f(2)의 값이 f(3)을 푸는데 사용되는 방식으로 이어지기 때문이다.

    이렇게, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 탑다운 방식(top-dwon)이라고 하며, 단순히 반복문을 이용하여 소스코드를 작성하는 경우, 작은 문제부터 차근차근 답에 도달한다고 하여 바텀업 방식(bottom-up) 이라고 한다. 바텀업 방식으로 코드를 짜면, 재귀함수 대신 반복문을 사용하여 메모리에 적재되는 과정을 따르지 않아도 되므로, 오버헤드를 줄일 수 있다는 장점이 있다.

피보나티 수열을 바텀업 방식(bottom-up)으로 구현한 코드는 아래와 같다.

# DP 테이블 초기화
memo = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
memo[1] = 1
memo[2] = 1
n = 99

# 반복문으로 피보나치 구현
for i in range(3,n+1):
    memo[i] = memo[i-1] + memo[i-2]

print(memo[99])     #  218922995834555169026n -- 역시 값은 똑같이 나온다.

탑다운 방식을 '하향식'이라고도 하고, 바텀업 방식을 '상향식'이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식(bottom-up)을 따르고 있고, 그 과정에서 사용되는 저장용 리스트를 'DP테이블' 이라고 부른다.

반면, '메모제이션'이라는 이름은 탑다운 방식(top-down)에서 국한되어 사용되는 표현이다. 다이나믹 프로그래밍과 메모제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면, 메모제이션은 이전에 계산된 결과를 저장만하지, 다이나믹 프로그래밍을 위해 활용되지 않을 수도 있다.

    또한, 메모제이션은 때에 따라서 dict(딕셔너리) 자료형을 이용할 수도 있다. 물론, 3차원 리스트를 이용해야 하는 복잡한 난이도의 유형도 있다. 이런 문제는 '최단 경로' 알고리즘의 '플로이드 워셜' 알고리즘에서 살펴볼 것이다. 하지만, 보통 코딩 테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제되기 때문에, 너무 걱정할 필요는 없다. 다이나믹 프로그래밍 유형에 익숙해지려면, 많이 풀어봐야 하고, 어떠한 문제를 그리디로 접근했을 때, 시간이 매우 오래 걸린다면 DP를 적용할 수 있는지 중복 여부를 살펴볼 필요가 있다.

    푸는 과정에 있어서, 단순히 재귀함수로 비효율적인 프로그램을 작성한 후에, 작은 문제이서 구한 답이 큰 문제에서도 그대로 사용될 수 있다면,(메모제이션을 적용할 수 있다면) 코드를 개선하는 방법도 하나의 팁이다. 보통 바텀업 방식으로 구현하되, sys 라이브러리의 setrecursionlimit()함수를 호출하면 파이썬의 기본 재귀 깊이 제한인 1000을 더 깊게 늘릴 수 있다.

(ex. sys.setrecursionlimit(10 ** 6) ) 과 같이 사용하면 된다. (재귀 호출 횟수 제한 때문에 억울하게 틀릴 수도 있으니까 알아두자! )