[Python] 재귀 함수(Recursive Function)와 동적 계획법(Memoization) 사용 예제(이항계수)

이전 포스팅에서 이항계수를 계산할 때 재귀함수를 사용하는 방법과 약간의 문제점을 살펴봤다.

[Python] 재귀 함수와 예제(팩토리얼, 이항계수 계산)

 

재귀 함수를 사용한 이항계수를 구하는 코드와 문제점은 다음과 같다.

class BinomialCoefficientCalculator:
    def calculate(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1
        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        return self.calculate(n - 1, k - 1) + self.calculate(n - 1, k)

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 이항 계수 계산 및 결과 출력
    calculator = BinomialCoefficientCalculator()
    result = calculator.calculate(n, k)
    print(f"{n}C{k} = {result}")

위 코드의 문제점은 작아진 입력 값을 계산할 때 같은 입력에 대한 결과를 여러 번 계산하는데 있다.

별 거 아닌 계산인데 시간이 꽤 걸린다

같은 계산을 여러 번 반복하기 때문에 \( \binom{30}{15} \)을 계산하는데 무려 14초 가량이 소요된다.

 

이런 문제를 해결하기 위해 동적 계획법(Memoization)을 사용할 수 있다.

이번 포스팅에서는 동적 계획법이 무엇이고 구현 방법과 예제를 살펴보자.

---

동적 계획법(Memoization)이란

동적 계획법(Memoization, 메모이제이션) 기법은 이전에 계산한 값을 저장해서 동일한 계산을 반복하지 않도록 하는 최적화 기법이다.

이는 동일한 입력에 대한 함수의 결과를 캐시에 저장해두고 같은 입력이 다시 들어올 때 이전에 계산해둔 값을 불러오므로 중복된 계산을 피하는 방식이다.

Memorization이 아님에 유의하자.

 

구현하는 방식은 아래와 같다.

def memoized_function(input, memo={}):
    # 이미 계산된 결과가 memo에 있으면 반환
    if input in memo:
        return memo[input]

    # 기저 조건을 확인하고 결과 계산
    result = compute_result(input)

    # 계산된 결과를 memo에 저장
    memo[input] = result

    return result

설명하자면 input을 검사하여 이미 계산된 결과가 있다면 계산해둔 값을 리턴한다.

없다면 계산을 하고 계산된 결과를 저장해둔다.

필요에 따라 기저 조건을 설정해야할 수도 있다.

 

이제 직접 예제를 통해 자세한 방법을 알아보자.

---

동적 계획법(Memoization)을 사용해서 이항계수 계산

먼저 동적 계획법을 사용하지 않은 이항계수를 계산하는 코드는 다음과 같다.

시간을 비교하기 위해 함수가 돌아가는 시간도 측정해보자.

import time

class BinomialCoefficientCalculator:
    def calculate(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1
        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        return self.calculate(n - 1, k - 1) + self.calculate(n - 1, k)

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 이항 계수 계산 및 시간 측정
    start_time = time.time()
    calculator = BinomialCoefficientCalculator()
    result = calculator.calculate(n, k)
    end_time = time.time()
    elapsed_time = end_time - start_time

    # 결과 및 시간 출력
    print(f"{n}C{k} = {result}")
    print(f"Time taken to calculate: {elapsed_time} seconds")

만약 이 코드로 5C2을 계산한다고 가정해보자.

• n와 k로 5와 2을 입력받으면 출력은 4C1와 4C2가 된다.
  • 4C1은 3C0와 3C1을 리턴한다.
    • 3C0은 1을 리턴하고
    • 3C1은 2C0와 2C1을 리턴한다.
      • 2C0은 1을 리턴한다.
      • 2C1은 1C0, 1C1을 리턴한다.
        • 1C0은 1을 리턴
        • 1C1은 1을 리턴한다.
  • 4C2는 3C1와 3C2을 리턴한다.
    • 3C1은 2C0와 2C1을 리턴한다.
      • 2C0은 1을 리턴한다.
      • 2C1은 1C0, 1C1을 리턴한다.
        • 1C0은 1을 리턴
        • 1C1은 1을 리턴한다.
    • 3C2는 2C1와 2C2을 리턴한다.
      • 2C1은 1C0, 1C1을 리턴한다.
        • 1C0은 1을 리턴
        • 1C1은 1을 리턴한다.
      • 2C2는 1을 리턴한다.

보다시피 같은 입력에 대한 함수의 결과 값을 여러 번 계산하는 부분이 있고(내가 쓰다가 헷갈린 부분이 있을지도 모르겠다.) 이런 부분이 쌓이면 컴퓨팅 시간을 많이 잡아먹게 된다.

 

이제 각 값을 구하면 저장하는 방식을 추가해서 동적 계획법을 사용해보자.

import time

class BinomialCoefficientCalculator:
    def __init__(self):
        self.memo = {}

    def calculate(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이미 계산된 값이 있다면 바로 반환
        if (n, k) in self.memo:
            return self.memo[(n, k)]

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate(n - 1, k - 1) + self.calculate(n - 1, k)

        # 결과를 memo에 저장
        self.memo[(n, k)] = result

        return result

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # 이항 계수 계산 및 시간 측정
    start_time = time.time()
    calculator = BinomialCoefficientCalculator()
    result = calculator.calculate(n, k)
    end_time = time.time()
    elapsed_time = end_time - start_time

    # 결과 및 시간 출력
    print(f"{n}C{k} = {result}")
    print(f"Time taken to calculate: {elapsed_time} seconds")

크게 바뀌는 점은 없지만 결과 값을 저장하는 부분과 입력을 if문에 넣어 계산된 값이 있다면 바로 리턴하는 부분만이 추가되었다.

 

이 코드의 작동 방식을 살펴보자.

아까와 같이 이 코드로 5C2을 계산한다고 가정해보자.

 

• n와 k로 5와 2을 입력받으면 출력은 4C1와 4C2가 된다.
  • 4C1은 3C0와 3C1을 리턴한다.
    • 3C0은 1을 리턴하고
    • 3C1은 2C0와 2C1을 리턴한다.
      • 2C0은 1을 리턴한다.
      • 2C1은 1C0, 1C1을 리턴한다.
        • 1C0은 1을 리턴
        • 1C1은 1을 리턴한다.
  • 4C2는 3C1와 3C2을 리턴한다.
    • 3C1은 아까 계산해둔 값(3)을 가져온다.
    • 3C2는 2C1와 2C2을 리턴한다.
      • 2C1은 아까 계산해둔 값(2)을 가져온다.
      • 2C2는 1을 리턴한다.

다 썼으니 동적 계획법을 사용하지 않았을 때와 과정을 비교해보자.

동적 계획법 미사용	동적 계획법 사용
n와 k로 5와 2을 입력받으면 출력은 4C1와 4C2가 된다. 4C1은 3C0와 3C1을 리턴한다. 3C0은 1을 리턴하고 3C1은 2C0와 2C1을 리턴한다. 2C0은 1을 리턴한다. 2C1은 1C0, 1C1을 리턴한다. 1C0은 1을 리턴 1C1은 1을 리턴한다. 4C2는 3C1와 3C2을 리턴한다. 3C1은 2C0와 2C1을 리턴한다. 2C0은 1을 리턴한다. 2C1은 1C0, 1C1을 리턴한다. 1C0은 1을 리턴 1C1은 1을 리턴한다. 3C2는 2C1와 2C2을 리턴한다. 2C1은 1C0, 1C1을 리턴한다. 1C0은 1을 리턴 1C1은 1을 리턴한다. 2C2는 1을 리턴한다.	n와 k로 5와 2을 입력받으면 출력은 4C1와 4C2가 된다. 4C1은 3C0와 3C1을 리턴한다. 3C0은 1을 리턴하고 3C1은 2C0와 2C1을 리턴한다. 2C0은 1을 리턴한다. 2C1은 1C0, 1C1을 리턴한다. 1C0은 1을 리턴 1C1은 1을 리턴한다. 4C2는 3C1와 3C2을 리턴한다. 3C1은 아까 계산해둔 값(3)을 가져온다. 3C2는 2C1와 2C2을 리턴한다. 2C1은 아까 계산해둔 값(2)을 가져온다. 2C2는 1을 리턴한다.

계산하는 것들이 확 없어졌다.

5C2라 간단했지 이런 부분이 누적되면 성능 차이가 나게 된다.

 

코드는 완성됐으니 다음 장에서 두 방법의 시간을 비교해보자.

---

동적 계획법을 사용했을 때 시간 비교

이제 각 방법의 컴퓨팅 시간을 측정해보자.

같은 입력을 주고 두 가지 방법을 사용했을 때의 컴퓨팅 시간을 직접 측정해보자.

 

코드는 다음과 같다.

import time

class BinomialCoefficientCalculator:
    def __init__(self):
        self.memo = {}

    def calculate_recursive(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_recursive(n - 1, k - 1) + self.calculate_recursive(n - 1, k)

        return result

    def calculate_memoized(self, n, k):
        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이미 계산된 값이 있다면 바로 반환
        if (n, k) in self.memo:
            return self.memo[(n, k)]

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_memoized(n - 1, k - 1) + self.calculate_memoized(n - 1, k)

        # 결과를 memo에 저장
        self.memo[(n, k)] = result

        return result

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # Recursive 방식의 계산 및 시간 측정
    start_time_recursive = time.time()
    calculator_recursive = BinomialCoefficientCalculator()
    result_recursive = calculator_recursive.calculate_recursive(n, k)
    end_time_recursive = time.time()
    elapsed_time_recursive = end_time_recursive - start_time_recursive

    # Memoization 방식의 계산 및 시간 측정
    start_time_memoized = time.time()
    calculator_memoized = BinomialCoefficientCalculator()
    result_memoized = calculator_memoized.calculate_memoized(n, k)
    end_time_memoized = time.time()
    elapsed_time_memoized = end_time_memoized - start_time_memoized

    # 결과 및 시간 출력
    print(f"{n}C{k} (Recursive) = {result_recursive}")
    print(f"Time taken (Recursive): {elapsed_time_recursive} seconds")

    print(f"\n{n}C{k} (Memoized) = {result_memoized}")
    print(f"Time taken (Memoized): {elapsed_time_memoized} seconds")

입력으로 n=30, k=10을 줘보자.

내 컴퓨터로 돌렸을 때의 출력은 아래와 같다.

유의미한 시간 차이가 난다

동적 계획법을 적용하지 않았을 땐 14초가 걸리던 계산이 동적 계획법을 적용했더니 0.0002초 수준에서 계산을 끝내버린다.

---

각 방법 별 함수 호출 횟수 비교

각 방법 별 함수 호출 횟수도 비교해보자.

 

각 함수 별로 변수를 만들고 0으로 초기 값을 세팅한 다음 함수가 실행될 때마다 +1을 해보자.

코드는 다음과 같다.

import time

class BinomialCoefficientCalculator:
    def __init__(self):
        self.memo = {}
        self.recursive_calls = 0
        self.memoized_calls = 0

    def calculate_recursive(self, n, k):
        self.recursive_calls += 1

        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_recursive(n - 1, k - 1) + self.calculate_recursive(n - 1, k)

        return result

    def calculate_memoized(self, n, k):
        self.memoized_calls += 1

        # 기저 조건: k가 0이거나 k가 n과 같을 때
        if k == 0 or k == n:
            return 1

        # 이미 계산된 값이 있다면 바로 반환
        if (n, k) in self.memo:
            return self.memo[(n, k)]

        # 이항 계수의 성질을 이용하여 재귀적으로 계산
        result = self.calculate_memoized(n - 1, k - 1) + self.calculate_memoized(n - 1, k)

        # 결과를 memo에 저장
        self.memo[(n, k)] = result

        return result

if __name__ == "__main__":
    # 사용자로부터 n과 k 입력 받기
    n = int(input("Enter the value of n: "))
    k = int(input("Enter the value of k: "))

    # Recursive 방식의 계산 및 시간 측정
    start_time_recursive = time.time()
    calculator_recursive = BinomialCoefficientCalculator()
    result_recursive = calculator_recursive.calculate_recursive(n, k)
    end_time_recursive = time.time()
    elapsed_time_recursive = end_time_recursive - start_time_recursive
    calls_recursive = calculator_recursive.recursive_calls

    # Memoization 방식의 계산 및 시간 측정
    start_time_memoized = time.time()
    calculator_memoized = BinomialCoefficientCalculator()
    result_memoized = calculator_memoized.calculate_memoized(n, k)
    end_time_memoized = time.time()
    elapsed_time_memoized = end_time_memoized - start_time_memoized
    calls_memoized = calculator_memoized.memoized_calls

    # 결과, 시간, 호출 횟수 출력
    print(f"{n}C{k} (Recursive) = {result_recursive}")
    print(f"Time taken (Recursive): {elapsed_time_recursive} seconds")
    print(f"Recursive calls: {calls_recursive}")

    print(f"\n{n}C{k} (Memoized) = {result_memoized}")
    print(f"Time taken (Memoized): {elapsed_time_memoized} seconds")
    print(f"Memoized calls: {calls_memoized}")

 

이제 또 입력으로 n=30, k=10을 줘보자.

내 컴퓨터로 돌렸을 때 출력은 아래와 같다.

함수 호출 횟수 카운트

동적 계획법을 사용하지 않은 깡코드는 함수가 무려 310,235,039번 호출되었다.

반면 동적 계획법을 사용한 코드는 함수가 겨우 451번만 호출되는 것을 확인할 수 있다.

---

알아본 것처럼 함수에 같은 입력이 반복될 때 동적 계획법(memoization)을 사용하면 강력한 성능을 보여준다.

잘 써먹어보자.