[ CodeSignal ] 재귀를 이용한 팩토리얼 계산: 메모이제이션

 

재귀는 복잡한 문제를 단순하고 이해하기 쉬운 코드로 표현할 수 있게 해주는 강력한 프로그래밍 기법입니다. 그러나 때로는 재귀 호출이 과도하게 발생하여 성능 저하나 스택 오버플로우와 같은 문제가 생길 수 있습니다. 이 글에서는 재귀를 사용하여 리스트의 각 정수에 대한 팩토리얼을 계산하는 방법을 살펴보고, 메모이제이션(memoization)을 통해 어떻게 성능을 향상시킬 수 있는지 알아보겠습니다.

 

팩토리얼이란?

팩토리얼은 수학에서 자연수의 곱을 의미하며, 기호 n!로 표기합니다.

• 정의:
  • n ! = n × ( n − 1 ) × ( n − 2 ) × ⋯ × 1
  • ( 0 ! = 1 ) (예외적으로 0의 팩토리얼은 1로 정의됩니다.)

예를 들어:

• 3 ! = 3 × 2 × 1 = 6
• 5 ! = 5 × 4 × 3 × 2 × 1 = 120

 

 

코드 시그널 문제 

 

https://learn.codesignal.com/course/11/unit/1/practice/3

CodeSignal Learn

 

 

양의 정수로 이루어진 리스트가 주어졌을 때, 각 정수의 팩토리얼을 계산하여 새로운 리스트로 반환하는 함수를 작성하고자 합니다.

• 입력: [2, 3, 4]
• 출력: [2, 6, 24]

또한, 입력 리스트에는 음수나 0도 포함될 수 있으며, 음수의 팩토리얼은 정의되지 않으므로 'Error'를 반환해야 합니다.

1. 재귀를 이용한 구현

 

우선, 가장 직관적인 방법으로 재귀를 사용하여 팩토리얼을 계산하는 함수를 작성해보겠습니다.

def factorial(num):
    if num < 0:
        return 'Error'
    elif num == 0 or num == 1:
        return 1
    else:
        return num * factorial(num - 1)

• 음수 처리: 입력된 숫자가 음수인 경우 'Error'를 반환합니다.
• 기저 조건: num이 0 또는 1이면 1을 반환합니다.
• 재귀 호출: 그 외의 경우 num * factorial(num - 1)을 계산합니다.

 

사용 예시

def factorials(nums):
    return [factorial(num) for num in nums]

print(factorials([2, 3, 4]))  # 출력: [2, 6, 24]
print(factorials([1, 5, 6]))  # 출력: [1, 120, 720]
print(factorials([0, -3, 10]))  # 출력: [1, 'Error', 3628800]

 

 

이렇게 작성한 함수는 작은 숫자에 대해서는 잘 동작하지만, 입력 값이 커지거나 동일한 숫자가 여러 번 등장하는 경우 문제가 발생할 수 있습니다.

 

 

재귀 호출의 과도한 증가

예를 들어, factorial(5)를 계산하려면 다음과 같은 호출이 발생합니다.

• factorial(5)는 5 * factorial(4)를 호출
• factorial(4)는 4 * factorial(3)을 호출
• ...
• factorial(1)은 1을 반환

즉, factorial(5)를 계산하기 위해 총 5번의 재귀 호출이 발생합니다.

 

 

중복 계산의 발생

입력 리스트에 동일한 숫자가 여러 개 있는 경우, 동일한 계산을 반복하게 됩니다.

nums = [5, 3, 5, 3, 5]
result = factorials(nums)

 

이 경우 factorial(5)와 factorial(3)이 각각 3번, 2번씩 계산됩니다. 따라서 성능 저하와 스택 오버플로우 위험이 있습니다. 입력 값이 매우 큰 경우 재귀 호출의 깊이가 깊어져 스택 오버플로우가 발생할 수 있으며, 계산 시간이 오래 걸리게 됩니다.

 

위에서 살펴본 문제점을 해결하기 위해 메모이제이션(memoization)을 도입할 수 있습니다.

 

 

메모이제이션이란?

메모이제이션은 이미 계산한 결과를 메모리에 저장해 두고, 동일한 입력이 들어왔을 때 저장된 결과를 재사용하는 기술입니다. 이를 통해 중복 계산을 방지하고 성능을 향상시킬 수 있습니다.

 

메모이제이션을 적용한 코드

memo = {0: 1, 1: 1}

def factorial(num):
    if num < 0:
        return 'Error'
    if num in memo:
        return memo[num]
    memo[num] = num * factorial(num - 1)
    return memo[num]

• 메모리 초기화: {0: 1, 1: 1}로 초기값을 설정합니다.
• 음수 처리: 입력된 숫자가 음수인 경우 'Error'를 반환합니다.
• 메모이제이션 체크: num이 memo에 있으면 저장된 값을 반환합니다.
• 값 계산 및 저장: memo[num] = num * factorial(num - 1)로 계산 결과를 저장합니다.
• 결과 반환: 계산된 값을 반환합니다.

 

사용 예시

def factorials(nums):
    return [factorial(num) for num in nums]

print(factorials([2, 3, 4]))  # 출력: [2, 6, 24]
print(factorials([1, 5, 6]))  # 출력: [1, 120, 720]
print(factorials([0, -3, 10]))  # 출력: [1, 'Error', 3628800]

 

 

메모이제이션의 효과!

 

1. 중복 계산 방지

이제 동일한 숫자에 대한 팩토리얼 계산이 한 번만 이루어집니다. 이전의 예시를 다시 살펴보면:

nums = [5, 3, 5, 3, 5]
result = factorials(nums)

• factorial(5)와 factorial(3)은 각각 한 번씩만 계산되고, 이후에는 memo에 저장된 값을 사용합니다.

 

2. 성능 향상

• 시간 복잡도 감소: 중복 계산이 사라지므로 전체 계산 시간이 크게 단축됩니다.
• 재귀 호출 깊이 감소: 이미 계산된 값은 재귀 호출 없이 바로 반환되므로, 스택 오버플로우의 위험이 감소합니다.

 

메모이제이션과 메모리 사용량의 균형

메모이제이션은 성능 향상에 큰 도움을 주지만, 메모리 사용량이 증가하는 단점이 있습니다. 따라서 다음과 같은 상황에서 메모이제이션의 사용을 고려해야 합니다.

• 메모리 여유가 충분한 경우: 메모리를 충분히 활용하여 성능을 높일 수 있습니다.
• 입력 데이터에 중복된 값이 많은 경우: 중복 계산이 많을수록 메모이제이션의 효과가 커집니다.
• 큰 입력 값이 있는 경우: 재귀 호출의 깊이를 줄여 스택 오버플로우를 방지할 수 있습니다.

반대로, 메모리 제한이 엄격하고 중복 계산이 거의 없는 경우에는 메모이제이션을 사용하지 않는 것이 나을 수 있습니다.

 

 

 

성능 비교: 

 

파이썬의 timeit 모듈을 사용하여 메모이제이션 사용 여부에 따른 성능 차이를 측정해보겠습니다.

 

테스트 코드

import timeit

setup_code = '''
def factorial_no_memo(num):
    if num < 0:
        return 'Error'
    elif num == 0 or num == 1:
        return 1
    else:
        return num * factorial_no_memo(num - 1)

def factorial_with_memo(num):
    if num < 0:
        return 'Error'
    if num in memo:
        return memo[num]
    memo[num] = num * factorial_with_memo(num - 1)
    return memo[num]

nums = [5, 3, 5, 3, 5]
'''

# 메모이제이션 미사용 시간 측정
no_memo_time = timeit.timeit('''
[factorial_no_memo(num) for num in nums]
''', setup=setup_code, number=10000)

# 메모이제이션 사용 시간 측정
with_memo_time = timeit.timeit('''
memo = {0: 1, 1: 1}
[factorial_with_memo(num) for num in nums]
''', setup=setup_code, number=10000)

print(f'메모이제이션 미사용 시간: {no_memo_time}')
print(f'메모이제이션 사용 시간: {with_memo_time}')

 

결과 

메모이제이션 미사용 시간: 0.011745300143957138
메모이제이션 사용 시간: 0.008576199878007174

 

메모이제이션을 사용한 경우 실행 시간이 약 27% 정도 단축되었습니다.

 

 

1. 메모이제이션의 효과
   •  중복 계산 방지: 입력 리스트 nums에는 숫자 5와 3이 반복됩니다. 메모이제이션을 사용하면 처음 계산한 5!와 3!의 값을 memo에 저장하고, 이후 동일한 숫자가 등장할 때 저장된 값을 바로 반환합니다.
   •  재귀 호출 감소: 메모이제이션을 통해 이미 계산된 부분 문제를 재사용하므로, 재귀 호출의 깊이가 줄어듭니다.
   •  실행 시간 단축: 중복 계산이 줄어들고, 재귀 호출 횟수가 감소하므로 전체 실행 시간이 단축됩니다.
2. 입력 데이터의 영향
   •  중복된 값의 존재: 리스트에 중복된 숫자가 많을수록 메모이제이션의 효과가 커집니다. 이번 테스트에서는 5와 3이 여러 번 등장하여 메모이제이션의 장점이 두드러집니다.
   •  숫자의 크기: 계산해야 할 숫자의 크기가 커질수록 메모이제이션의 효과가 더욱 커집니다. 큰 숫자의 팩토리얼은 재귀 호출이 깊어지기 때문에, 메모이제이션을 통해 재귀 깊이를 줄일 수 있습니다.
3. 메모리 사용량
   •  메모이제이션을 사용하면 계산된 결과를 저장하기 위해 추가적인 메모리가 필요합니다.
   •  그러나 테스트에서 사용하는 숫자들이 작고, 저장되는 값의 개수가 적어 메모리 사용량은 크게 문제되지 않습니다.

 

 

결론

 

재귀를 이용한 팩토리얼 계산에서 메모이제이션은 성능 향상을 위한 강력한 도구입니다.

• 메모이제이션의 장점:
  • 중복 계산 방지로 인한 속도 향상
  • 재귀 호출 깊이 감소로 인한 스택 오버플로우 방지
• 메모이제이션의 단점:
  • 추가적인 메모리 사용

문제의 특성과 요구 사항에 따라 메모이제이션의 사용 여부를 결정해야 합니다. 이번 글을 통해 재귀 함수에서 메모이제이션을 적용하는 방법과 그 효과를 이해하는 데 도움이 되었으면 좋겠네요 ㅎㅎ

 

 

 

 

 

.

.

.

.

전체 코드 정리

# 메모이제이션 미사용
def factorial_no_memo(num):
    if num < 0:
        return 'Error'
    elif num == 0 or num == 1:
        return 1
    else:
        return num * factorial_no_memo(num - 1)

# 메모이제이션 사용
memo = {0: 1, 1: 1}

def factorial_with_memo(num):
    if num < 0:
        return 'Error'
    if num in memo:
        return memo[num]
    memo[num] = num * factorial_with_memo(num - 1)
    return memo[num]

def factorials(nums, use_memo=False):
    if use_memo:
        return [factorial_with_memo(num) for num in nums]
    else:
        return [factorial_no_memo(num) for num in nums]

# 사용 예시
print(factorials([2, 3, 4], use_memo=False))  # 출력: [2, 6, 24]
print(factorials([2, 3, 4], use_memo=True))   # 출력: [2, 6, 24]