[2021/08/18][짤막한 이야기 - 메모이제이션]

[2021/08/18][짤막한 이야기 - 메모이제이션]

당신이 “알고리즘”에 전혀 관심이 없더라도 “피보나치 수열”을 한번쯤은 들어본 적이 있을 것이다.

피보나치 수열은 첫째 및 둘째 항(F1 & F2)이 1이며 셋째 항(F3)부터는 앞의 두 항의 합(F2 + F1)으로 구성되는 수열이다.

이를 점화식으로 표현하면 “F(i) = F(i-1) + F(i-2)”가 될 것인데, 간단하게 생각하면 “재귀 함수(Recursive Function)”로 구현할 수 있을 것 같다.

그런데 피보나치 수열은 매우 비효율적이다.

왜냐하면 F(7)을 구하기 위하여 F(3)을 구하는 횟수가 5번이나 되기 때문이다.

즉, “중복되는 부분 문제(Overlapping Sub Problem)”가 너무 많기 때문에 F(N)을 단순하게 재귀로 구현하면 시간 복잡도가 엄청나게 커지게 된다(약 O(2^N)).

이는 동적 계획법(Dynamic Programming)의 "메모이제이션(Memoization)" 방식을 활용하면 쉽게 해결할 수 있다.

기본 재귀 함수에 “메모이제이션” 개념을 추가하면 매우 효율적으로 동작하게 된다(약 O(N)).

메모이제이션은 이미 생성해본 값을 “기억(Memorization)”해두는 것이다.

피보나치 수열을 단순 재귀로 계산한다면 이미 생성해봤던 값도 모두 다시 생성해야하기 때문에 비효율적인 것이다.

메모이제이션의 기본 개념은 매우 간단하므로 예시 코드만을 남겨둔다.

두 코드를 실행해본다면 엄청난 시간 차이를 보일 것이다.

[관련된 짤막한 이야기 - 시간 복잡도[2021/08/04]]

#이야기 #루니프 #알고리즘 #피보나치 #동적계획법 #메모이제이션

 

[2021/08/18][Short Story - Memoization]

Even if you're not interested in "Algorithm", you've probably heard of "Fibonacci Sequence" at least once.

The Fibonacci sequence is a sequence in which the first and second terms (F1 & F2) are 1, and from the third term (F3), the sum of the previous two terms (F2 + F1).

Expressing this as an ignition formula, it would be “F(i) = F(i-1) + F(i-2)”.

However, the Fibonacci sequence is very inefficient.

In order to calculate F(7), the number of times to calculate F(3) is 5 times.

In other words, because there are many “Overlapping Sub Problems”, simple recursive implementation for calculating F(N) will increase the time complexity enormously (about O(2^N)).

This can be solved by using the "Memoization" method of Dynamic Programming.

Adding the concept of memoization to the code above makes it work very efficiently (about O(N)).

Memoization is to “Memorize” values ​​that have already been calculated.

If you calculate the Fibonacci sequence by simple recursion, it is inefficient because you have to recalculate all the values ​​that have already been calculated.

The basic concept of memoization is very simple, so only example code is left.

If you run the two codes, you will see a huge time difference.

[Related Short Story - Time-Complexity[2021/08/04]]

#Story #LootNiP #Algorithm #Fibonacci #DynamicProgramming #Memoization