5-2. DP: 메모이제이션

1. 동적 프로그래밍(DP)과 메모이제이션의 만남

동적 프로그래밍(DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 재사용하여 전체 문제의 효율적인 해결을 이끌어내는 강력한 알고리즘 설계 패러다임입니다. DP는 최적 부분 구조(optimal substructure)와 중복되는 하위 문제(overlapping subproblems)라는 두 가지 핵심 특징을 가질 때 효과적입니다. 최적 부분 구조는 전체 문제의 최적해가 하위 문제의 최적해로부터 구성될 수 있음을 의미하며, 중복되는 하위 문제는 동일한 하위 문제가 여러 번 나타나는 상황을 의미합니다.

이러한 DP의 효율성을 극대화하는 데 핵심적인 기법 중 하나가 바로 "메모이제이션(memoization)"입니다. 메모이제이션은 이전에 계산한 하위 문제의 결과를 저장해두고, 동일한 하위 문제가 다시 나타났을 때 재계산하지 않고 저장된 결과를 활용하는 기술입니다. 이는 중복 계산을 피하고, 알고리즘의 시간 복잡도를 획기적으로 개선하는 데 기여합니다. 특히, 재귀 호출을 기반으로 하는 "탑다운(top-down)" 방식의 DP 구현에서 메모이제이션은 필수적인 요소입니다.

2. 메모이제이션의 원리

메모이제이션은 본질적으로, 결과를 "기억"하는 것입니다. 즉, 계산된 값을 특정 자료구조(일반적으로 배열, 해시 테이블, 딕셔너리 등)에 저장해두는 방식입니다. 이후 동일한 입력에 대한 계산이 필요할 때, 저장된 값을 확인하여 존재하면 즉시 반환하고, 없으면 계산을 수행한 후 저장합니다. 이러한 과정을 통해 중복 계산을 방지하고, 실행 시간을 단축할 수 있습니다.

1) 작동 방식

메모이제이션은 다음과 같은 과정을 거칩니다.

1. 함수 호출: 특정 입력값에 대한 함수가 호출됩니다.
2. 결과 확인: 먼저, 해당 입력값에 대한 결과가 저장되어 있는지 확인합니다.
3. 결과 반환 (저장된 경우): 저장된 결과가 있다면, 해당 결과를 즉시 반환합니다. 이 단계에서 계산은 수행되지 않습니다.
4. 계산 및 저장 (저장되지 않은 경우): 저장된 결과가 없다면, 함수는 계산을 수행합니다. 계산이 완료되면, 입력값과 계산된 결과를 함께 저장합니다.
5. 결과 반환 (계산된 경우): 계산된 결과를 반환합니다.

2) 자료구조 선택

메모이제이션을 위한 자료구조 선택은 성능에 직접적인 영향을 미칩니다.

• 배열: 입력값이 제한적인 범위 내에서 정수형인 경우, 배열은 빠르고 효율적인 선택입니다. 배열의 인덱스를 입력값으로, 해당 인덱스에 값을 저장하는 방식으로 구현할 수 있습니다.
• 해시 테이블/딕셔너리: 입력값의 범위가 넓거나, 정수형이 아닌 다른 형태(예: 문자열, 튜플 등)인 경우, 해시 테이블이나 딕셔너리가 적합합니다. 해시 테이블은 빠른 검색 속도를 제공하며, 유연하게 다양한 입력값을 처리할 수 있습니다.

3. 탑다운(Top-down) 방식 DP와 메모이제이션

탑다운 방식은 큰 문제를 작은 하위 문제로 재귀적으로 분해하여 해결하는 접근 방식입니다. 각 하위 문제는 다시 하위 문제로 분해될 수 있으며, 이러한 재귀적 호출 과정에서 동일한 하위 문제가 여러 번 나타날 수 있습니다. 바로 이 지점에서 메모이제이션이 빛을 발합니다.

1) 구현 예시 (피보나치 수열)

피보나치 수열은 DP와 메모이제이션을 이해하기 위한 전형적인 예시입니다. 피보나치 수열은 다음과 같이 정의됩니다.

• $F(0) = 0$
• $F(1) = 1$
• $F(n) = F(n-1) + F(n-2)$ (for $n \ge 2$)

메모이제이션을 사용하지 않는 순수한 재귀적 구현은 동일한 하위 문제를 반복적으로 계산하여 비효율적입니다.

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 예시 호출
print(fibonacci_recursive(5)) # 결과: 5

메모이제이션을 적용한 탑다운 방식의 구현은 다음과 같습니다.

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n] # memo에 값이 있으면 즉시 반환
    if n <= 1:
        return n
    result = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    memo[n] = result # 계산된 값을 memo에 저장
    return result

# 예시 호출
print(fibonacci_memoization(5)) # 결과: 5

위 코드에서 memo 딕셔너리가 메모이제이션을 위한 자료구조 역할을 합니다. 함수가 호출될 때마다, memo에 해당 값이 있는지 확인하고, 있으면 즉시 반환합니다. 계산이 필요한 경우, 계산을 수행하고 결과를 memo에 저장합니다.

2) 시간 복잡도 분석

• 메모이제이션을 사용하지 않는 재귀적 구현: 시간 복잡도는 $O(2^n)$입니다. 이는 동일한 하위 문제가 중복 계산되기 때문에 지수적으로 증가합니다.
• 메모이제이션을 사용하는 탑다운 방식 구현: 시간 복잡도는 $O(n)$입니다. 각 하위 문제는 한 번만 계산되고, 그 결과가 저장되므로 전체 계산 횟수가 선형적으로 증가합니다.

메모이제이션을 통해 시간 복잡도를 획기적으로 개선할 수 있음을 알 수 있습니다.

4. 메모이제이션 활용 사례

메모이제이션은 다양한 DP 문제에 적용될 수 있습니다.

1) 최단 경로 문제

다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford) 알고리즘과 같은 최단 경로 탐색 알고리즘에서, 각 노드까지의 최단 거리를 계산하는 과정에서 메모이제이션을 사용하여 중복 계산을 방지할 수 있습니다.

2) 배낭 문제

배낭 문제(Knapsack Problem)는 DP의 대표적인 예시입니다. 주어진 가치와 무게를 가진 물건들을 배낭에 담아, 배낭의 용량 제한 내에서 최대 가치를 얻는 문제로, 메모이제이션을 통해 최적해를 효율적으로 찾을 수 있습니다.

3) LCS (Longest Common Subsequence, 최장 공통 부분 수열)

두 문자열의 최장 공통 부분 수열을 찾는 문제 역시 DP와 메모이제이션을 활용하여 해결할 수 있습니다.

4) 그 외 다양한 DP 문제

메모이제이션은 "최적 부분 구조"와 "중복되는 하위 문제"를 갖는 거의 모든 DP 문제에 적용 가능합니다. 예를 들어, 행렬 곱셈 순서 결정 문제, 동전 거스름돈 문제, 편집 거리 문제 등 다양한 알고리즘 문제에서 메모이제이션을 통해 성능을 향상시킬 수 있습니다.

5. 메모이제이션의 주의사항

1) 메모리 사용량

메모이제이션은 계산된 결과를 저장하기 때문에, 입력값의 범위가 넓거나, 하위 문제의 수가 많을 경우 메모리 사용량이 증가할 수 있습니다. 따라서, 메모리 사용량을 고려하여 적절한 자료구조를 선택하고, 불필요한 값은 제거하는 등의 최적화가 필요할 수 있습니다.

2) 재귀 호출 스택 오버플로우

탑다운 방식은 재귀 호출을 사용하므로, 깊은 재귀 호출로 인해 스택 오버플로우가 발생할 수 있습니다. 이러한 문제를 해결하기 위해, 재귀 호출 깊이를 제한하거나, 반복문을 사용하는 바텀업(bottom-up) 방식으로 구현을 변경할 수 있습니다.

3) 초기화

메모이제이션을 위한 자료구조(예: 배열, 딕셔너리)는 초기화가 필요합니다. 특히, 배열을 사용하는 경우, 각 요소의 초기값을 적절하게 설정해야 합니다(예: -1, float('inf') 등).

6. 결론

메모이제이션은 DP의 핵심적인 기법으로서, 알고리즘의 효율성을 크게 향상시키는 데 기여합니다. 특히 탑다운 방식의 DP 구현에서 메모이제이션은 필수적이며, 중복 계산을 제거하여 시간 복잡도를 획기적으로 개선합니다. 메모이제이션을 효과적으로 활용하기 위해서는, 문제의 특성을 파악하고, 적절한 자료구조를 선택하며, 메모리 사용량과 재귀 호출 깊이 등을 고려해야 합니다. DP와 메모이제이션에 대한 깊이 있는 이해는 알고리즘 문제 해결 능력을 향상시키고, 더 효율적인 소프트웨어 개발을 가능하게 합니다.