Dynamic Programming 2

저번 시간에는 중복 문제를 해결하는 Dynamic Programming에 필요한 두 조건과 이를 구현하기 위한 두 방법 중 하나인 Memoization에 대해 배웠습니다.

이번 시간에는 두번째 방법인 Tabulation에 대해 배우고 두 방법의 장단점을 알아보겠습니다.

🕺 Tabulation

저번 시간에 Dynamic Programming을 활용하기 위한 두 가지 방법이 있다고 했죠? 그 중 하나는 부분 문제를 메모하면서 해결하는 Memoization이었습니다. 간단히 복습해보죠.

Memoization으로 fib(5)라는 문제를 풀 때, fib(4)와 fib(3)으로 나누고 다시 fib(4)를 fib(3)과 fib(2)로 나누고 이러한 과정들을 반복하면서 중복되는 연산을 캐시라는 저장 공간에 넣어두었다가 다시 나타나면 가져다 쓰는 방식을 사용했습니다.

이렇게 fib(5)에서 fib(4)로, 다시 fib(4)에서 fib(3)으로 내려가면서 문제를 푸는 방식을 '하향식 접근(Tod-down Approach)'이라고 합니다.

이번 시간에 배울 Tabulation은 중복되는 것부터 해결하는 방법인데요. Memoization과 반대로 아래서부터 차례로 문제를 풀며 올라갑니다.

fib(1)을 먼저 구하고 그 다음 fib(2), fib(3), fib(4) 등으로 문제를 해결하는 거죠. 이러한 방식은 '상향식 접근(Bottom-up Approach)'이라고 불립니다. 이렇게 문제를 풀면 문제가 중복될 일이 없습니다.

실제 예시를 함께 보죠.

피보나치 수열의 조건 상, fib(1)과 fib(2)는 1입니다. fib(3)은 fib(1)과 fib(2)의 합인 2입니다. fib(4)는 fib(2)와 fib(3)을 더한 3이 되고 fib(5)는 fib(3)과 fib(4)를 더한 5, fib(6)은 fib(4)와 fib(5)를 더한 8입니다.

이처럼 Tabulation은 표를 채워나가는 방식입니다. 표는 영어로 table이죠? Tabulation이라는 단어는 Table 방식으로 정리한다는 것을 의미합니다.

눈으로 봐도 Memoization과 다른 방식이라는 게 보이죠? 재귀 기반으로 코드를 작성하는 Memoization과 다르게 Tabulation은 반복문을 활용하여 리스트를 채워나가는 방식으로 코드를 작성합니다.

❗ Tabulation 구현하기

Tabulation을 실제 코드로 접해봅시다. Memoization과 마찬가지로 피보나치 수열 구하는 문제를 활용하겠습니다.

fib_tab은 Tabulation 방식으로 n번째 피보나치 수를 찾아주는 함수입니다. 파라미터로는 정수 n을 받습니다.

Tabulation식 문제 풀이에서 기억해야 할 것은 두 가지입니다. 첫째, 테이블 형태로 풀이할 것. 둘째, 반복문을 활용할 것.

테이블 형태로 풀이하는 것을 어떻게 프로그래밍에서 구현할 수 있을까요? 리스트와 사전 등의 자료형을 활용하면 됩니다. 사전형이 리스트보다 메모리를 더 잡아먹기 때문에 효율상 리스트를 활용하겠습니다.

먼저, 연산 결과가 들어갈 리스트를 선언해야겠죠? 그런데 피보나치 조건 상, 첫 번째 피보나치 수와 두 번째 피보나치 수는 1로 고정되어 있습니다. 그리고 인덱스는 0부터 시작하기 때문에 0번째 피보나치 수를 가정하고 0이라는 값을 넣어줍니다.

fib_table = [0, 1, 1]

이제 세 번째 피보나치 수를 리스트에 추가해줘야 하는데요. 지금부터는 반복문을 활용해야 합니다.

반복문의 조건 부분에는 인덱스 i가 2보다 큰 경우에는 연산을 통해 피보나치 수를 구하고 해당 인덱스에 결괏값을 넣어주어야 합니다.

for i in range(3, n+1):
    fib_table.append(fib_table[i - 1] + fib_table[i - 2])

for문을 사용할 때는 인덱스의 범위 지정에 유의해야 하는데요. 이미 인덱스 0, 1, 2의 값은 채워져 있으므로 인덱스는 3부터 시작해야 합니다. 그리고 파라미터로 들어온 정수 번째의 인덱스 값도 포함해야 하므로 마지막 인덱스는 n+1이 되는 것이죠.

피보나치 연산은 이미 여러 번 접했듯 이전 수와 그 전 수를 더한 값이 현재 수가 됩니다. 그 값을 append 메소드를 통해 리스트에 넣어주면 되죠.

이제 전체 코드와 예시를 봅시다.

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

이때, 반환되어야 할 값은 리스트가 아니라 해당 인덱스의 값임을 주의하세요.

print(fib_tab(1))
print(fib_tab(3))
print(fib_tab(10))

1
2
55

🕺 Memoization vs. Tabulation

Dynamic Programming 구현을 위한 두 가지 방식을 접해봤는데요. 두 접근 방식의 공통점은 중복되는 부분 문제의 비효율을 해결할 수 있다는 것입니다. 이는 Dynamic Programming의 목적이기도 하죠.

그럼 두 접근 방식의 차이점은 뭘까요? 가장 핵심적인 차이점은 Memoization은 일반적으로 재귀 함수를 사용하고 Tabulation은 반복문을 사용한다는 것입니다.

재귀 함수를 사용한다는 것은 재귀 함수의 단점을 그대로 가지고 있다는 것을 의미하는데요. 우리는 앞서 재귀 호출이 너무 많이 일어나면 스택이 쌓여 과부하가 걸릴 수 있다는 것을 봤습니다.

Tabulation은 테이블을 활용하기 때문에 이러한 오류가 생길 가능성이 없죠. 이 점에서는 Tabulation이 Memoization보다 좋은 방식이라고 할 수 있겠네요. 그렇다면 Memoization은 쓸모가 없는 방식일까요? 그렇지 않습니다.

Tabulation은 테이블을 채워나가는 과정이기 때문에 n번째 값을 구하기 위해서 처음부터 구하려는 값까지 모든 계산을 해야 합니다. 이 말은 즉, 중간에 필요없는 부분까지 계산할 수 있다는 것을 뜻합니다.

그러나 Memoization은 위에서부터 필요한 계산이 무엇인지 요구하기 때문에 불필요한 계산은 하지 않는다는 장점이 있습니다.

🕺 DP 공간 최적화

피보나치 수열을 Tabulation 방식으로 구현하면 시간 복잡도가 O(n)이고 공간 복잡도도 O(n)입니다. 이는 Dynamic Programming으로 구현함으로써 더 효율적인 코드가 되었다는 걸 나타내는데요. 그러나 아직도 비효율이 존재합니다.

fib(5)를 계산하기 위해서는 fib(4)와 fib(3)만 알면됩니다. fib(10)을 계산할 때도 fib(9)와 fib(8)만 있어도 되죠. 하지만 우리는 Tabulation 방식을 활용하며 fib(10)을 구하기 위한 모든 값들을 테이블에 저장하고 있었습니다.

이를 더 효율적으로 바꾸기 위해서는 리스트 대신 가장 최근 값들을 저장하는 변수 두 개를 활용하면 됩니다. 예를 들어 가장 최근 값을 나타내는 current와 그 직전 값을 나타내는 previous라는 변수를 선언합니다.

current의 초기값은 1이고 previous의 초기값은 0입니다. 그 다음 피보나치 수를 구하고 싶으면 이 두 값을 갱신하면 되겠죠?

previous와 current를 더한 값이 current의 새로운 값이 됩니다. 그리고 previous에는 기존의 current값이 들어가게 되죠. 이렇게 하면 current와 previous 값 모두 1로 갱신됩니다.

그 다음 피보나치 수도 구해보죠. 기존의 previous와 current 값을 더한 수가 current에 새롭게 들어가고 기존의 current 값이 previous에 새롭게 들어갑니다. 그럼 이제 current는 2가 되고 previous는 1이 됩니다.

한 번만 더 해보겠습니다. 기존의 previous와 current 값을 더한 3이라는 수가 current에 들어가고 기존의 current 값인 2가 previous 안에 새롭게 들어갑니다. 이런 식으로 계속하면 결국 원하는 값을 찾을 수 있겠죠.

중요한 것은 사용하는 메모리가 변수 두 개로 고정되어 있기 때문에 공간 복잡도는 O(1)이 됩니다. 굉장히 효율적인 알고리즘이라는 것이죠.

앞으로 Dynammic Programming을 할 때, 모든 계산값을 저장할 필요가 없다면 공간 사용을 최적화할 방법을 생각해볼 필요가 있습니다.

❗ 공간 최적화 구현하기

위 내용을 코드로 구현해봅시다. 리스트 대신 변수 두 개를 사용한다고 했죠? 따라서, 변수 두 개를 선언해줍니다. 초기값 설정도 잊지마세요.

previous = 0
current = 1

이제 반복문을 돌며 원하는 값을 구할 때까지 피보나치 연산을 반복합니다. 반복문의 조건 범위는 1부터 n까지로 정합니다. 1부터 시작하는 이유는 current값이 이미 1로 정해져있기 때문이죠.

for i in range(1, n):

이제 반복할 연산을 생각해봐야 합니다. 앞서 current 변수에는 기존 previous의 값과 current값을 더한 값이 들어가야 하고 previous 변수에는 기존 current 값이 들어가야 한다고 했죠?

그런데 previous에 current 값이 들어가면 기존 previous 값을 잃게 되면서 previous와 current의 합을 구할 수 없습니다. 따라서, temp라는 임시 변수에 기존 previous 값을 먼저 보관해 두어야 합니다.

temp = previous
previous = current
current += temp

한 가지 팁을 드리자면 Python에서는 임시 저장 변수 없이 한 줄에 위와 같은 연산을 수행할 수 있는 코드를 작성할 수 있습니다.

current, previous = current + previous, current

이해가 어려우실 분들을 위해 일반화하여 설명 드리겠습니다. 일종의 공식처럼 생각하면 편하실 수 있는데요.

a, b = b, a

동작 원리는 이렇습니다. 먼저 b, a 값이 들어간 튜플을 생성하고(임시 변수 temp와 같은 역할) 이 튜플을 a, b에 집어 넣는 원리입니다.

사실 엄밀히 말하면 임시 저장 변수가 아예 없는 것은 아니고 코드상으로만 보이지 않을 뿐 튜플이 들어갈 임시 저장 공간은 존재합니다. 그 공간으로부터 값을 가져와 새로운 변수에 넣어주는 것이죠.

이제 전체 코드와 예시를 봅시다.

def fib_optimized(n):
    
    current = 1
    previous = 0
    
    for i in range(1, n):
        current, previous = current + previous, current

    return current

fib_optimized(1)
fib_optimized(10)

1
55

---

이번 시간에는 Dynamic Programming을 구현하는 두 가지 방법 중 Tabulation에 대해 배웠습니다. 그리고 두 가지 방법의 효율도 비교해봤죠.

또 하나, 모든 연산 값이 필요없는 경우에는 공간 복잡도를 최적화할 새로운 방법을 고안할 필요성이 있다는 점도 배웠습니다.

다음 시간에는 마지막으로 Dynamic Programming을 활용하여 문제를 풀어보도록 하겠습니다. 마지막까지 꼭 따라와 주세요!

* 이 강의는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.