[코드트리 조별과제] Memoization? 메모이제이션이란?

1. "Memoization"이란?

자, 굉장히 어려워 보이는 모습으로 보일 수 있다.

하지만 굉장히 간단하고 우리에게 친숙할 수 있다.

 

"Memory"  ==  "기억"

"~tion" == "행위", "상태" 등.

 

기억하는 행위다.

의미 자체는 어떤가, 굉장히 쉽지 않은가?

이론도 매우 간단하다.

 

DP의 기초로 배우는 가장 첫 단계로, 사실 모두가 알게 모르게 쓰고 있는 기법이기도 하다.

 

2. 이해를 위한 예시

2-1. 과거 DFS와의 연관성

일전에 DFS를 했었는데, 기억을 더듬어보자.

https://devbini.tistory.com/14

[코드트리 조별과제] 깊이 우선 탐색[DFS] 기초

 

거기서 실습하는 과정에서 했던

"이미 지나갔던 정점"을 체크하는 부분이 기억이 나는가?

과거 정점체크

 

이 부분이 사실 Memoization의 원리와 동일하다.

재귀, 혹은 For 반복을 하면서

이미 한번 진행했던 것인지를 검사하는 과정을 포함시켜 재귀의 수를 줄인다.

다시 한번 말하자면,  "이미 계산된 값을 저장해 두었다가 필요할 때 재사용하는 기법이다."

 -> 중복 계산을 피하고 성능을 최적화할 수 있는 이점이 있다!

 

3. 기본 문제 풀이

3-1. 문제 개요 확인

이번에도 역시 코드 트리(Codetree)를 이용해 보겠다.

문제

 

자.. 우선 Padovan(10)을 실행하면 일어나는 첫 재귀는 어떻게 될까?

재귀 시작

이제 우린 "?"에 들어가는 값을 먼저 찾아볼 것이다.

우선 코드에서 "재귀"를 더 이상 진행하지 않는 부분은 어디인지를 알아야 한다.

    if memo[n] != -1
        return memo[n]
    if n <= 3
        memo[n] = 1

 

이 부분이다.

padovan(3) 이하로 들어오는 모든 값에선 "1"을 반환하도록 되어있다.
동시에, "메모이제이션" 배열의 값이 -1이 아니라면, 해당 값을 반환한다.

 

우선 지금 당장은 메모이제이션을 제외하고 생각해 보자.

 

모든 경우의 수

 

자,, 이렇게, "Padovan(10)"을 동작시키는 데 있어 이 모든 재귀를 수행하게 된다.

총 몇 번 실행되었을까?

 

무려 16회다.

그럼 만약 Padovan의 인자가 50, 100이 된다면?

상상도 못 할 정도로 엄청난 시간복잡도를 보여주는 폭탄 덩어리가 되어버릴 것이다.

 

이래서 "메모이제이션"을 사용하는 거다.

메모이제이션은 간단하다.

memoization이란?

이런 것처럼, "한 번 도달한 데이터의 결과를 저장"하고, 중복적인 재귀를 다시 실행할 필요를 없애는 거다.

 

위에서 했던 예시를 보면 16개의 재귀를 통과하여 결과를 도출해내야만 한다.

하지만 만약 Memoization을 사용한다면 어떻게 바뀔까?

memo 구분

짜잔, 이렇게 바뀌게 된다.

 

노란 동그라미가 memo 배열의 값을 수정하고,

회색의 동그라미는 memo 배열의 값만을 가져와 사용한다.

 

Padovan(10)만 해도 이렇게 결과를 볼 수 있는데,

재귀의 인자가 늘어날수록 이러한 성능 개선은 중요한 요소가 될 것이다.

 

자, 그럼 이제 문제를 풀어보자.

memo = [-1, -1, -1, ...]

function padovan(n)
    if memo[n] != -1
        return memo[n]
    if n <= 3
        memo[n] = 1
    else
        memo[n] = padovan(n - 2) + padovan(n - 3)
        print(memo[n])

    return memo[n]

 

출력 결과를 보여줘야 하니 간단하다.

print() 부분이 실행되는 경우만 찾아서 써 주면 된다.

 

"3 이하" 이거나 이미 "memo"에 있는 값이라면 출력하지 않는다.

그럼, print가 실행되는 경우는

print 실행 경우

이렇게, 빨간 동그라미 친 부분에서 발생할 것이다.

 

print는 재귀가 종료된 시점으로부터 계단처럼 한 계단씩 돌아오며 수행이 된다.

그렇다면 순서는?

print 실행 순서

 

이렇게 될 것이다.

 

그러면 결과를 써 보면...

2 3 2 5 4 9

 

정답입니다!