8. 이코테 - 다이나믹 프로그래밍

김혁·2022년 2월 14일

이코테

목록 보기

6/9

중복되는 연산을 줄이자

현실세계에는 다양한 문제가 있다. 그런데 이 중에서 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이란는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 이번 장에서 다루는 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 먼저 다이나믹 프로그래밍의 기본적인 아이디어를 소개한뒤에, 다이나믹 프로그래밍의 2가지 방식(탑다운, 보텀업)을 설명할 것이다. 특히 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법까지 소개하겠다.

ex) 피보나치 수열

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 잇다. 수열 자체가 여러개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다. 파이썬에서는 리스트 자료형이 이를 처리하고, c나 자바에서는 배열을 이용해 이를 처리한다. 리스트나 배열 모두 '연속된 많은 데이터를 처리한다는 점은 동일하다.

그렇다면 이 점화식에 따라서 실제로 피보나치 수를 구하는 과정을 어떻게 표현할 수있을까? n째 피보나치 수를 f(n)이라고 표현할 때 4번째 피보나치 수 f(4)를 구하려면 다음과 같이 함수f를 반복해서 호출할 것이다. 그런데 f(2)와 f(1)은 항상 1이기 때문에 f(1), f(2)를 만났을 대 호출을 정지한다.

def fibo(x):
  if x == 1 or x==2:
    return 1
  return fibo(x-1) + fibo(x-2)

print(fibo(4))

위는 피보나치 수열의 소스코드이다. 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n) 함수에서 n이 커지면 커질 수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이 소스코드의 시간 복잡도는, 엄밀히 말하면 피보나치 수열의 정확한 시간 복잡도는 세타 표기법을 사용하여 O(2^N)의 지수 시간이 소요된다고 표현한다. 이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효육적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

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

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션 기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다. 그렇다면 실제로 메모이제이션 어떻게 구현될 수 있을까?
단순하다. 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다. 이를 소스코드로 나타내면 다음과 같다.

피보나치 수열 소스코드(재귀적)

파이썬 프로그램을 실행해보면 99번째 피보나치 수를 구하도록 했음에도 불구하고 금방 정답을 도출하는 것을 알 수 있다.
정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 사실 큰 문제를 작게 나누는 방법은 퀵정렬에서도 소개된 적이다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복 알고리즘으로 분류된다. 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
퀵 정렬을 예로 들면, 한 번 기준 원소가 자리를 변경해서 자리를 잡게 되면 그 기준의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇게 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다. 예를 들어 재귀 함수를 이용하는 방법에서는 한 번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다.

재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.

*오버헤드 : 어떤 과정을 처리하기 위한 간접적인 시간

일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다. 그렇다면 다이나믹 프로그래밍을 적용했을 때 피보나치 수열 알고리즘의 시간 복잡도는 어떻게 될까? 바로 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는 데 사용되는 방식으로 이어지기 때문이다. 한 번 구한 결과는 다시 구해지지 않는다. 다음의 코드를 보자

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다.
반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 말한다. 피보나치 수열 문제를 아래에서 위로 올라가는 보텀업 방식으로 풀면 다음과 같다. 동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다.

피보나치 반복문 소스코드)

수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 때에 따라서 다른 자료형, 예를 들어 사전(dict)자료형 이용할 수도 있다. 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용한데, a(0~ n-1) 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 존재할 수 있다. 이럴 때에는 사전 자료형을 사용하는게 더 효과적이다. 다이나믹 프로그래밍을 이용하여 피보나치 수열 문제를 풀었던 방법을 잘 알아두면 다른 다이나믹 프로그래밍 문제에 접근하는 방법 또한 떠올릴 수 있을 것이다. 물론 3차원 리스트를 이용해야 하는 복잡한 난이도의 문제가 출제될 수도 있다. 이런 문제는 이어서 배울 9장 최단 경로의 플로이드 워셜 알고리즘에서 다룬다. 코테에서는 간단한 다이나믹 프로그래밍 문제를 풀기에는 큰 어려움이 없을 것이다.

문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자. 일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운)작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어다. 앞서 다루었던 피보나치 수열의 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코들 수정하는 것도 좋은 방법이다. 또한 탑다운 보다는 보텀업을 권장한다. 재귀의 스택 크기가 한정되어 있을 수 있기 때문이다. 오천 번째 이상의 재귀가 일어날시 'recursion depth'와 관련된 오류가 발생할 수 있다. 이 경우 sys라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다는 점 정도만 기억하자.