메모이제이션 (Memoization)

 

메모이제이션 (Memoization)

 

 

 

이 알고리즘에 대해서는 백준 알고리즘 11051번 (이항 계수 2) 문제를 통해서 학습하게 되었다.

 

메모이제이션은 동적 계획법 (Dynamic programming)의 핵심 기술이다.

 

(동적 계획법에 대한 설명은 따로 정리를 할 예정이므로 이 게시물에서 개념에 대한 설명은 간단하게 한다.)

 

 

우선 해당 문제에 대해서 한번 살펴보자.

 

 

다음과 같이 문제가 주어져 있다.

 

즉, 예를 들어 입력으로 5 2를 입력하게 되면, 10이 출력되어야 한다.

 

 

 

이 알고리즘에 대해 알지 못하거나 익숙하지 않은 사람들은 필자를 포함하여 대부분

 

 

위의 식을 이용해서 풀었을 것이다. 즉, 만약 "10 5" 가 입력되었다면, (N = 10, K = 5)

 

1부터 10까지 곱한 후, 다시 1부터 5까지 나누어주고, 1부터 (10-5)까지 나누어주는 방식일 것이다.

 

이 방식을 이용하게 되면 작은 수로 예시를 들면 답이 나오지만, N이 어느정도만 커지더라도

 

금방 오류가 발생하는 것을 파악할 수 있다.   

 

그 이유는, "오버플로우(Overflow)"가 발생하기 때문이다.

 

 

 

예를 들어서, "1000 500" (N = 1000, K = 500)이 입력되었다고 가정하자.

 

그렇다면 우선 1부터 1000까지 곱해주어야 한다.

 

하지만 가장 큰 범위의 정수를 저장할 수 있는 long long int 데이터 타입 일지라도,

 

bit까지 최대로 저장이 가능하기 때문에 1부터 1000까지 곱하는 과정에서 이 범위를 초과하게 된다.

(실수형 double 데이터 타입도 마찬가지이다)

 

그래서 정확한 값을 저장할 수 없으므로 N이 큰 수인 경우에는 올바른 답을 구하지 못한다.

 

 

 

다음 방법으로는, 내가 수학좀 한다! 혹은 이항 계수에 대해서 잘 알고 있다!는 사람은

 

아래의 식을 떠올릴 수 있을 것이다. 

 

 

 

이 식과 더불어 재귀호출에 대한 개념까지 완벽히 이해하고 있다면 아마 별도로

 

N과 K를 parameter로 받는 함수를 만들어 이항계수를 계산하는 프로그램을 구현할 것이다.

 

물론, 간단하지만 이 과정에서 정수론 개념(modulo)이 이용되기도 한다. ( (a+b)%mod = a%mod + b%mod )

 

 

하지만 이 경우에도 적절하게 답을 도출해내기가 어렵다.

 

그 이유는 재귀함수를 호출하는 시간이 오래 걸리기 때문에 N과 K가 커지는 경우에 실행시간이 매우 길어진다.

 

이 문제의 조건으로 주어진 실행시간은 1초 이내이므로 N이 어느정도만 커져도 금방 1초를 초과하게 된다.

 

 

그럼 이제는 어떤 방법을 이용해야 할까?  여기서 이용하는 방법이 바로 "메모이제이션"이다.

 

 

메모이제이션 (Memoization) 이란, 반복되는 동일한 계산(ex 함수 호출, 동일한 input, output의 코드 등)을 수행할 때,

 

처음 구해 놓은 값을 메모리에 저장해 둠으로써 동일한 반복을 제거하여 수행 속도를 높이는 기법이다.

 

 

'기억되어야 할 것'이라는 뜻의 라틴어 'memorandum'에서 파생되었으며,

 

Memoization에서 'Memo' 즉, 메모해두다 또는 memory에 넣다, 기억해두다 등의 의미를 담고 있다.

 

사실 말은 되게 어려워 보이지만 방식 자체는 정말 단순히 따로 저장을 하는 기법이다.

 

 

 

예를 들어서 위와 같이 파스칼의 삼각형을 생각해서, 5C2를 구한다고 가정해보자.

 

그렇다면, 아래와 같이 4C1과 4C2를 구해야 하고, 4C1과 4C2 각각을 재귀호출을 통해서 구한다면 위에서 부터

 

차례대로 내려오기 때문에 결국 초록 원을 중복해서 계산하게 된다.

 

 

그러므로 재귀 호출을 이용하면 이전에 구한 값을 한번 더 계산을 통해 구하는 불필요한 과정이 발생하게 되는 것이다.

 

따라서 메모이제이션 기법을 이용해서 처음에 4C1 를 구할 때 필요했던 3C1 값을 계산 후에 별도로 저장해두면 

 

그 다음 4C2 를 구할 때에는 3C1 는 미리 저장된 값으로 바로 얻고, 3C2만 구해주면 되므로 수행 시간이 줄어든다.

 

 

이러한 방식으로 11051번 문제를 풀면 깔끔하게 통과가 된다...!

 

(https://wogud6792.tistory.com/4 참고)

 

 

 

이 기법을 이용할 수 있는 대표적인 또 다른 문제는 피보나치 수열 문제이다.

 

피보나치 수열을 재귀 호출로 구하게 되면 시간 복잡도는 O(2^n)으로 나오게 된다.

 

하지만 메모이제이션 기법을 이용하게 되면 O(n)으로 나오게 되므로 n이 커질 수록 더욱 효과적인 것을 알 수 있다.