[알고리즘] DP 풀이에서의 메모이제이션 Memoization

DP 외에도 DFS/BFS 등등 여러 유형의 알고리즘에서 재귀함수를 사용할 때면 종종 마주쳤던 효율성 이슈,,

그럴 수밖에 없는 것이, 재귀를 사용하면 하나의 해답을 얻기 위해 정말 많은 반복적인 연산이 필요하게 된다.

이로 인한 시간 초과 문제를 해결할 수 있는 방법이 바로 메모이제이션!

 

DP에서의 메모이제이션은 memo라는 배열을 만들어서 초기값은 답이 될 수 없는 값(-1도 많이 쓴다고 함)으로 설정하고, 계산이 이루어지면 memo 배열에 계산 값을 저장해주는 식으로 사용한다. 배열에 초기값이 들어있다면 계산을 진행하고, 아니라면 저장된 값을 가져와 사용하는 식이다. 이렇게 되면 중복 탐색을 예방할 수 있다.

 

아래는 피보나치 문제에 메모이제이션을 적용한 사례.

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

function fibbo(n)
    if memo[n] != -1           // 이미 n번째 값을 구해본 적이 있다면
        return memo[n]         // memo에 적혀있는 값을 반환해줍니다.
    if n <= 2                  // n이 2이하인 경우에는 종료 조건이므로 
        memo[n] = 1            // 해당하는 숫자를 memo에 넣어줍니다.
    else                       // 종료조건이 아닌 경우에는 
        memo[n] = fibbo(n - 1) + fibbo(n - 2)   // 점화식을 이용하여 답을 구한 뒤
                                                // 해당 값을 memo에 저장해줍니다.
    return memo[n]             // memo 값을 반환합니다.