[알고리즘] Memoization과 동적 프로그래밍

앞에서 보았던 피보나치 수를 재귀 함수로 구하는 프로그램은 "엄청난 중복 호출" 이라는 큰 문제가 존재한다.

이를 해결하기 위해 동적 계획법의 핵심 기술인 memoization에 대해 먼저 알아보자

 

# memoization

• 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술
• 글자 그대로 해석하면 '메모리에 넣기 (to put in memorty)'라는 의미
• 앞서 구했던 fibo(n)의 값을 계산하자 마자 저장하면 O(2^n) 시간을 O(n)으로 줄일 수 있다.

 

이제 memoization을 활용한 Dynamic Programming에 대해서 알아보자

 

# DP(Dynamic Programming)

• 동적 계획 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 먼저 입력 크기가 작은 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘

 

좀 전에 다뤄보았던 피보나치 수를 DP적용해서 풀어보자.

피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다.

1. 문제를 부분 문제로 분할한다.
   • Fibonacci(n) 함수는 Fibonacci(n-1)과 Fibonacci(n-2)의 합
   • Fibonacci(n-1) dms Fibonacci(n-2)와 Fibonacci(n-3)의 합
   • Fibonacci(n)은 Fibonacci(n-1), Fibonacci(n-2),... Fibonacci(2), Fibonacci(1), Fibonacci(0)의 부분집합으로 나뉨
2. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.
3. 그 결과는 테이블에 저장, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

def fibo2(n):
	f = [0,1]
    
    for i in range(2, n+1):
    	f.append(f[i-1] + f[i-2])
    
	return f[n]

 

어디에서나 DP를 사용할 수 있는 것일까?

 

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

 

① Overlapping Subproblems

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.

 

예를 들어, 이진 탐색와 피보나치 수열의 경우를 비교해 보자.

이진 탐색은 특정 데이터를 정렬된 배열 내에서 그 위치를 찾기 때문에 그 위치를 찾은 후 바로 반환할 뿐 그것을 재사용하는 과정을 거치지 않는다. 반면, 피보나치수열은 f(n) = f(n-1) + f(n-2) 인데, 아래와 같은 트리 구조로 함수가 호출되게 된다.

앞서 보았던 피보나치 수열 함수 호출 트리에서 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다. 그러므로 우리는 1회 계산했을 때, 저장된 값을 재활용할 수 있게 되는 것

 

② Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!

만약, A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.

위의 그림에서 A - X 사이의 최단 거리는 AX2이고 X - B는 BX2이다. 전체 최단 경로는 AX2 - BX2이다. 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.

이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
피보나치수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖고 있다.

 

이런 DP를 사용하기 전 아래의 과정을 거쳐 진행할 수 있다.

1. DP로 풀 수 있는 문제인지 확인
   • 위에서 본 조건들이 충족되는지 확인
   • 보통 특정 데이터 내 최대화/ 최소화 계산하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산 경우 대부분 사용 가능
2. 문제의 변수 파악
   • DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것
   • 즉 문제 내의 변수의 개수를 알아야 한다.
3. 변수간 관계식 만들기
   • 동일한 변숫값인 경우 결과가 동일하고 그 결과 값을 이용
   • 따라서 점화식을 만들어 낼 수 있어야 한다.
4. 메모하기
   • 변수의 값에 따른 결과를 저장해야 하고 이것이 처음에 알아본 memoization
5. 기저 상태 파악
   
   • 가장 작은 문제의 상태를 알아야 한다. 보통 직접 손으로 테스트하여 구성
   • 피보나치를 예로 들면, f(0) =0, f(1)=1과 같은 방식
6. 구현하기
   • 아래의 구현 방식을 통해 실제로 사용

DP의 구현 방식

• recursive 방식:  fib1()
  • Top-Down (Memoization 방식) 
  • 재귀의 정에 부합하게 함수 f(x)를 정의
• iterative 방식: fib2()
  • Bottom-Up (Tabulation 방식) 
  • for문 혹은 while문을 이용해서 같은 구조의 연산을, 반복해서 답을 구하는 방법

 

# Bottom-Up 방식

이름에서 보이듯이, 아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp [0]가 기저 상태이고 dp [n]을 목표 상태라고 하자. Bottom-up은 dp [0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

왜 Tabulation?

사실 위에서 메모하기 부분에서 Memoization이라고 했는데 Bottom-up일 때는 Tabulation이라고 부른다.

왜냐면 반복을 통해 dp[0]부터 하나하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다. 위에서 테이블을 채우는 과정을 보였다.

사실상 결괏값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.

 

# Top-down 방식

이는 dp [0]의 기저 상태에서 출발하는 대신 dp [n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp [0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.

 

• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적이다.
• 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문

 

 

이번 글에서는 DP와 MEMOIZATION에 대해 간단히 알아보았다. 항상 느끼는 것은 직접 코드를 풀어보며 이해하는 것이 제일 빠른 지름길인 것 같다. 

다음 글에서는 DFS에 대해 알아보자.

 

[참고] https://hongjw1938.tistory.com/47