[Python] 다양한 방법으로 팩토리얼(Factorial) 구해보기

0. 목차

1. 들어가며
2. 문제 소개
3. 여러 방법들 살펴보기
   • 3.1. Don’t reinvent the wheel by yourself
   • 3.2. 단순 반복문
   • 3.3. 재귀함수 사용
   • 3.4. reduce 함수 사용
   • 3.5. Meta!! programming
4. 효율성 극대화: Cache 사용
5. 마치며
6. 자료 출처

1. 들어가며

알고리즘 문제들을 풀면서 팩토리얼은 정말 많이 마주친다. 방금도 코드워즈에서 팩토리얼과 관련된 문제를 하나 풀었고, 내 블로그에도 팩토리얼을 사용해서 다른 문제를 해결하는 포스트들이 여럿 있다. 개념 자체도 쉽고 구현도 어렵지 않아서 많은 코더들이 알고리즘을 처음 공부할 때 한 번씩 풀어보지 않나 싶다.

오늘 문제를 풀면서 문득 ‘내가 파이썬으로 몇 가지 방법으로 팩토리얼을 구할 수 있을까?’하는 생각이 들었고 이 포스트를 작성하게 됐다. 지금 내 수준에서는 한 5가지 방법이 생각난다. 각 방법을 구현해보자. 그리고 이것만으로 끝나면 섭하니 Memoization을 통해 효율을 높이는 수준까지 가보자. 5가지 방법에 모두 memoization을 사용할텐데 이때 decorator의 강력함이 빛난다. 살펴보자.

2. 문제 소개

팩토리얼(Factorial)은 너무나 유명하고 친숙한 문제다. 0 이상의 정수 N을 받아서 N부터 (N-1), (N-2), …, 2, 1까지 곱하는 문제로 아마 고등학교 수준에서 배우는 것으로 기억한다.

\[ \text{Factorial of N} = factorial(N) = N! = N * (N-1) * \cdots * 2 * 1 \]

이때 5 팩토리얼은(5!)은 120이 된다.(5! = 5 * 4 * 3 * 2 * 1 = 120) 팩토리얼은 N이 증가함에 따라 무식하게 커져서 N이 10만 되어도 3,628,800이나 되기 때문에 알고리즘 문제에서 시간복잡도가 \(O(N!)\)이 되는 문제들은 보통 N 값이 작다.

팩토리얼은 여러 알고리즘 문제에서 사용되는데 팩토리얼과 직접적으로 연관된 문제들도 있지만(ex: 팩토리얼의 끝 0의 개수), 보통은 팩토리얼을 사용하는 이항계수, 조합론 문제에서 많이 등장한다. 개념 자체가 너무 쉽고 유용하기 때문에 개발이나 수학을 공부하는 사람들에게는 ‘기본’이라고 할 수 있는 알고리즘이다.

참고로 팩토리얼은 한글로는 계승(階乘)이라고도 하는데, 보통은 영어로만 사용한다.

3. 여러 방법들 살펴보기

살펴볼 방법은 모두 5가지다. 이 포스트의 목적은 ‘팩토리얼을 구하는 알고리즘을 만들자’가 아니라 ‘파이썬으로 팩토리얼을 어떻게 구하지?’이다. 참고하기 바란다.

모든 알고리즘들에서 입력되는 정수 N은 0이상이라고 가정하겠다. 따라서 입력에 대한 validation은 따로 진행하지 않는다.

3.1. Don’t reinvent the wheel by yourself

첫 번째 방법의 제목으로 쓸데없는 영어 격언을 넣었는데 저 문장의 뜻은 ‘바퀴를 직접 재발명하지 마라’이다. 이 격언은 소프트웨어 공학에서 유명한 Phrase로 이미 개발되어 있는 프로그램, 기능을 필요할 때마다 개발하지 말고 있는 코드를 모듈화해서 비슷한 문제상황에서 재사용하라는 뜻을 담고 있다.(또는 ‘복붙’이라고 이해되기도 한다.) 다시 말해 ‘있는거 가져다 쓰라’이다. 많은 경우에서 반복작업해야 하는 코딩은 문제해결에 있어서 꼭 필수적이지만 창의적이지는 않다. 애초에 반복된다는 것이 ‘새롭다’와는 대조적인 의미를 갖기 때문이다. 따라서 이 격언은 ‘필수적이지만 창의적이지 않은 코딩에 자원(시간, 인력)을 투입하지 말고 프로그램에 있어 창의적이고 새로운 기능에 자원을 더 투자하라’는 의미를 갖고 있다.

그래서 첫 번째 방법은 ‘파이썬에서 제공하는 팩토리얼 함수를 쓰자’이다. 파이썬은 다양한 수학적 연산을 지원하는 math 모듈을 내장하고 있는데 이 모듈에서 팩토리얼 함수를 제공한다.

import math

>>> math.factorial(5)
>>> math.factorial(20)

120
2432902008176640000

내가 알기로 C++이나 자바에는 팩토리얼을 구하는 내장 함수나 STL이 없는 걸로 아는데, 그래서인지 사람들이 팩토리얼을 직접 구현하려는 생각만 한다. 물론 구현이 매우 쉬운 것은 맞지만, 파이썬에서 있는 것을 가져다 쓰는 방법도 있다는 것을 참고하면 좋겠다.

3.2. 단순 반복문

다음은 아마 초보분들이 이 문제를 해결할 때 가장 많이 사용할 것으로 생각되는 반복문을 사용한 방법이다. 팩토리얼이 N부터 1까지 곱하는 것이기 때문에 반복문을 통해 1씩 늘리며 곱해나가면 충분하다. for, while 반복문을 모두 사용할 수 있는데 for 문을 사용하자.(코드가 더 짧다.)

def factorial_for(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
    return ret


>>> factorial_for(5)
>>> factorial_for(20)

120
2432902008176640000

for 반복문을 통해 팩토리얼을 구하는 factorial_for 함수를 구현했다. 첫 값을 1로 두고 n까지 반복하면서 곱해나가면 팩토리얼 값이 나온다. 매우 간단하고 무난한 해결방식이다.

3.3. 재귀함수 사용

난 재귀함수가 정말 좋다. 자주 예상하지 못하는 결과를 내놓기 때문이다. 분명 큐와 대조되는 스택의 비직관성 때문일 것이다.

때로 단순 반복문으로 해결할 수 있는 문제들은 재귀함수로도 구현할 수 있다. 그런데 재귀함수는 함수 내에서 동명의 함수를 재호출하기 때문에, 함수를 무한히 호출해 스택오버플로우가 발생할 수 있어서 재귀의 탈출 조건(base case)를 정해줘야 한다. 팩토리얼을 재귀함수로 구할 factorial_recursive 함수를 다음과 같은 식으로 정리할 수 있다.

\[ \text{factorial_recursive}(n) = \begin{cases} n * \text{factorial_recursive}(n-1) & \quad \text{if } n > 1 \\ 1 & \quad \text{else} \end{cases} \]

위 함수는 N이 1일 때는 1을 그대로 내놓고(\(1! = 1\)이기 때문에.) 아닐 때는 N에 (N - 1)! 재귀함수를 곱해 반환한다. 처음 이런 재귀함수를 보면 살짝 어리둥절할 수 있는데 N을 한 3, 4만 주고 저 식을 따라가보라. 정확히 값이 나온다.

알고리즘을 포함해 어떤 문제에서 문제의 해결책에 대한 일반식을 도출할 수 있으면 나머지는 그 식을 구현만 하면 되고 매우 쉽다.

def factorial_recursive(n):
    return n * factorial_recursive(n-1) if n > 1 else 1


>>> factorial_recursive(5)
>>> factorial_recursive(20)

120
2432902008176640000

재귀함수를 통해 팩토리얼을 구하는 factorial_recursive 함수를 구현했다. 이 구현의 장점은 삼항 연산자(ternary operator)를 통해 1줄로 구현이 가능하다는 점인데 이때 조건이 ‘n > 1’이라는 것을 확인하면 된다. 팩토리얼은 0!과 1! 모두 1이다. 이 함수는 이 두 값 모두 1로 적절히 반환한다.

3.4. reduce 함수 사용

함수형 프로그래밍 언어를 사용한 분들은 친숙하지만 파이썬 등으로 프로그래밍을 시작한 사람들이 잘 모르는 reduce라는 함수가 있다.

함수형 프로그래밍에서, reduce는 fold라고 일컬어지는 함수 집합의 일원으로 재귀적인 자료구조를 분석하고 주어진 결합 동작을 사용해서 원 자료구조의 부분구조를 반복적으로 처리해 재결합해서 하나의 결과값으로 반환하는 고순위(higher-order) 함수이다.

이게 대관절 무슨 말일까? 이때 저 문장을 조금씩 분해해서 설명하면 조금은 쉽게 이해할 수 있다.

• 재귀적인 자료구조
  • 파이썬의 리스트나 튜플 또는 range 처럼, 원소들을 하나씩 순회할 수 있는 자료구조를 뜻한다. 우리는 for문 등으로 리스트 순회를 밥먹듯 해왔다.
• … 결합 동작을 사용해 … 반복적으로 처리해 재결합해서 하나의 결과값으로 반환:
  • 여기가 핵심이다. 리스트 같은 자료구조는 원소의 개수가 임의적이다. 단 하나의 값이 아닌 상태다. reduce는 이런 자료구조에 결합동작(예를 들면, 합, 곱 등)을 사용해 원소들을 반복적으로 재결합해 하나의 값으로 반환한다.
  • 예를 들어 [1, 2, 3, 4, 5]라는 리스트가 있을 때 모든 원소를 더한 ‘하나의 값’을 구하고 싶다면 ‘합(add)’라는 결합동작을 이용해 각 원소를 더해나가며 최종적인 값 15를 구할 수 있을 것이다. 이것이 reduce의 역할이다.
  • 정리하면, 반복될 수 있는 자료구조에서 원소마다 원하는 연산을 반복해 단 하나의 값으로 환원하는 것, 이것이 reduce의 역할이다. 이 이름은 다양한 현상을 하나의 단일 원칙으로 귀속시키는 환원주의를 영어로 Reductionism이라고 하는 것과 무관하지 않을 것이다.

이 reduce의 개념을 이용해 팩토리얼을 구할 수 있다. 1부터 N까지 1의 간격으로 반복되는 자료구조(이를테면 리스트)가 있고 우리가 원하는 연산을 ‘곱’이라고 정의한다면, 그리고 이를 reduce 연산에 입력으로 주면 1부터 N까지 곱한 값, 즉 N!이 나오지 않겠는가?

바로 구현해보자. 파이썬에서는 functools라는 내장 모듈에서 reduce라는 함수를 제공한다. 이 함수는 첫 번째 인자로 원하는 연산, 두 번째 인자로 재귀적인 자료구조를 받는다.

from functools import reduce

def factorial_reduce(n):
    return reduce(lambda x, y: x * y, range(1, n+1))


>>> factorial_for(5)
>>> factorial_for(20)

120
2432902008176640000

reduce 를 활용해 팩토리얼을 구하는 factorial_reduce 함수를 작성했다.

• lambda x, y: x * y
  • 첫 번째 인자로서 두 원소의 곱을 반환하는 익명 람다함수를 작성했다. 이 함수는 재귀적인 자료구조에서 (1, 2번째), (2, 3) 번째, (3, 4) 번째의 원소들을 차례로 곱해나가며 자료구조의 끝 원소까지 나아가 결국 단 하나의 곱값을 반환할 것이다.
• range(1, n+1)
  • 우리가 for 반복문에서 자주 사용하는 range 는 사실 재귀적인 자료구조다! 이는 파이썬의 중급 이상의 내용으로 이 포스트와 직접적인 관련이 없어 넘어간다. Iterator, Generator, Iterable 등의 지식이 필요한 분은 메일 주시면 포스트를 작성하겠습니다.
  • 1부터 n 까지 곱을 해야하기 때문에 n+1 을 두 번째 인자로 넣어준다.

factorial_reduce 또한 답을 잘 구하는 것을 확인할 수 있다. 이렇게 함수형 프로그래밍과 관련 있는 map, filter, reduce 등은 익숙해지면 좋다. 파이썬에서 배열을 생성하는 리스트 컴프리헨션이 고차원으로 복잡해지면 이해하기 힘든 불편함이 생기는 데 이때 이 함수들이 좋은 대안이 되기도 한다. 이 개념과 함수는 파이썬이 아니더라도 자바스크립트 등의 언어에서라도 언젠가 마주칠 확률이 높기 때문에 기억하면 좋겠다.(예를 들어, 자바스크립트의 배열(array)은 map이라는 메소드를 지원한다. 많이 쓰이는 것 같다.)

3.5. Meta!! programming

이름이 뭔가 무시무시하다. ‘Meta’라. 위키피디아에 따르면 Meta programming(이하 ‘메타프로그래밍’)은 컴퓨터 프로그램이 다른 별개의 프로그램을 자신의 입력값으로 취할 수 있도록 하는 기법이다. 이 뜻은 컴퓨터 프로그램이 다른 프로그램을 읽고, 생성, 분석하며 실행 중에 수정할 수 있는 것을 말한다.

간단한 형태의 예시를 보자. 우리가 짜는 간단한 프로그램은 인터프리트에 해석되기 전에는 문자열의 형태다. ~~.py라는 이름의 파일 안에 들어간 내용들은 모두 문자열이다! 작성할 때 문자를 입력했지, 이미지나 동영상을 집어넣은 게 아니지 않은가. 당연한 사실이지만 처음 들으면 인식하지 못하기도 한다. ‘hi’ 라는 문자열을 출력하는 프로그램을 짜되, 그 프로그램의 이름을 runtime에 결정할 수 있는 메타프로그램을 짜보자.

name = input("함수의 이름을 정하시오: ")
program = f"""def {name}():
    print('hi')"""

exec(program)

program 은 정확히 ‘hi’를 표준출력에 표현하는 프로그램이다. 그런데 지금은 그냥 문자열의 형태로 저장되어 있으며 함수 이름도 정해지지 않았다. 이름은 사용자에게서 런타임일 때 입력받을 수 있다!

함수의 이름을 ‘hihi’라고 내 맘대로 정한 뒤 이 이름의 함수를 실행해보자.

함수의 이름을 정하시오: hihi

hihi()


hi

정말 신기하다! 원래의 프로그램의 이름을 미정으로 남겨두고 그 함수를 지배하는 메타프로그램을 통해 함수의 이름을 동적으로 결정했다.

여기서 exec 은 문자열 형태의 코드를 실행하는 함수다. program 변수는 프로그램을 문자열 형태로 담고 있었다. 이 코드를 실행함으로써 전역 이름공간에 hihi라는 함수가 기록될 수 있었던 것이다.

이 개념을 어떻게 사용해서 팩토리얼을 구한다는 것인가?

접근은 간단하다. 앞서 문자열 형태의 원 프로그램에 변화를 주는 등의 행동 뒤에 프로그램을 실행하는 것이 메타프로그래밍이라고 말했다.

그리고 팩토리얼은 다음과 같은 식으로 쓸 수도 있다.

\[ N! = 1 * 2 * 3 * … * (N - 1) * N \]

뭐 당연한 식이다. 이때 숫자 N을 받아 1부터 N까지 나열하고 그 사이에 우변처럼 ‘*‘를 끼어넣어 문자열로 반환하는 프로그램을 짜면 어떨까?

프로그램의 결과 생성된 식을 변형을 가하지 않고 실행해 평가값을 반환하면 팩토리얼을 구하는 것이 된다. 우변이 당연한 식이라고 인정했으니까.

코드를 먼저 보자.

def factorial_meta(n):
    if not n:
        return 1
    return eval('*'.join(str(i) for i in range(1, n+1)))



>>> factorial_for(5)
>>> factorial_for(20)

120
2432902008176640000

일단 n이 0이면 1을 반환한다. 그 밑의 식이 문제인데 결론만 말하면 eval 이라는 함수는 expression을 받아 그 평가값을 반환한다. ‘eval(“1 + 5”) == 6’인 것처럼.

이때 받은 expression 식은 n에 따라 ‘1*2*3*4*…*n’ 꼴의 문자열을 반환한다. 이 프로그램을 eval 함수에 넣고 실행해 생성된 값을 반환하며 이 값이 곧 팩토리얼이다.

위 식은 파이썬의 Iterator, str.join 등의 지식이 필요하다. 일단 넘어가겠다.

3장에서 5가지 방법으로 팩토리얼을 구해봤다. 모두 충분히 짧고 문제없이 동작한다.

근데 여기서 만족하면 안 되지. 한 단계 더 나아가자.

4. 효율성 극대화: Cache 사용

방금 짠 5가지 코드들의 시간 복잡도는 어떻게 될까? 가령 n이 10이면 재귀함수에서 10번의 재귀가 일어나기 때문에 시간복잡도는 \(O(N)\)이 된다. 좋다. 보통 어지간한 알고리즘에서 복잡도가 이 정도에 수렴하면 굉장히 훌륭한 수준의 알고리즘이다.

근데 팩토리얼을 한 두번이 아닌, 한 번 만들어놓고 매우 많이 실행해야 하는 경우에는 어떻게 될까?

쉬운 예를 들어서 인간은 10진수를 사랑하기 때문에 여하튼 무슨 이유로 10!을 지속적으로 한 1000번 계속해서 실행하면 그때마다 10번의 재귀함수 실행을 1000번을 해야 한다. 바로 이때 동적 계획법(Memoization)을 사용하면 좋겠다! 한 번 구한 값을 저장해서 같은 요청이 올 때마다 계산하지 않고 바로 반환하는 그런 함수 말이다.

3번 재귀함수에 이를 적용해보자.

cache = {}

def factorial_recursive(n):
    global cache

    if n in cache:
        return cache[n]
    elif n <= 1:
        return 1
    else:
        cache[n] = n * factorial_recursive(n-1)
	return cache[n]

    return n * factorial_recursive(n-1) if n > 1 else 1

전역 공간에 캐쉬로 쓸 dict를 선언했다. 이제 재귀함수에서 cache에 n에 해당하는 key가 있으면 value를 바로(계산할 필요없이) 반환한다. 계산한 적이 없으면 앞서 구현했던 대로 계산하고 차후에 쓰일 수 있도록 캐시에 저장한 뒤 반환한다. 다음에 같은 n으로 요청이 오면 해당하는 n!을 반환하면 된다.

정말 무난한 동적 계획법으로 피보나치 수열마냥 동적 계획법 입문용으로 쓰일 수 있는 코드이다.

하지만 저 코드를 보고 흐뭇해지면 그건 틀린 거다. 저 코드는 개선의 여지가 다분하다.

1. 일단 캐시가 전역으로 선언됐다. 이 캐쉬는 팩토리얼 기능만을 위해 존재할텐데 굳이 전역에 둬서 위험에 빠드릴 필요가 없다.
2. cache에 값을 요청하는 코드와 실제 계산하는 코드가 Couplinge된 상태다. 이 둘을 나누면 좋을 것 같다.
3. 코드가 중복된다. cache에 값을 요청하는 위 코드는 5가지 팩토리얼에 모두 중복해 쓸 수 있다. 이때 저 코드를 함수 각각에 넣으면 5개의 부분이 중복되는 것이다. 정말 쓸데없는 코드 낭비로 대충 계산해서 대략 100 Byte는 더 낭비될 것 같다. 코드의 중복 작성을 없애자.

이 3가지 문제점을 모두 해결할 수 있는 동적 계획법 구현은 없을까? 답은 있다. 바로 decorator

decorator를 써서 재사용성을 높이자 :)

decorator는 매우 유용해서 가급적 많이 사용하면 좋다. 저 재귀함수를 데코레이터를 사용해 Memoization하면 다음과 같이 코드를 짤 수 있을 것이다.

def in_cache(func):
    cache = {}
    def wrapper(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = func(n)
            return cache[n]
    return wrapper

@in_cache
def factorial_recursive(n):
    return n * factorial_recursive(n-1) if n > 1 else 1

cache에 n에 해당하는 팩토리얼이 존재하는지 먼저 검사하는 함수 in_cache 함수를 만들었다. 이 부분은 데코레이터를 이해해야 정확히 파악할 수 있는데 중요한건 캐시에 값을 확인하는 부분과 실제로 계산하는 부분이 유연하게 분리됐다는 사실을 기억하는 것이다.

위외 같이 작성함으로써 아까의 무식한 동적 계획법에 비해

1. 캐시가 전역공간이 아닌, in_cache 내의 이름공간을 쓰기 때문에 더 안전하며,
2. 캐시에 값을 확인하는 코드와 실제 계산하는 코드가 분리되어 재사용성이 강화됐으며,
3. 값을 확인하는 코드를 일일이 복붙할 필요가 없다는 것이다. 단순히 함수명(in_cache)을 ‘@’와 함께 적용하는 함수의 윗 줄에 둬서 함수를 감싸면 된다.

5가지 함수에 대해서 모두 @in_cache 데코레이터로 함수를 wrap해보자. 너무나 단순하다.

@in_cache
def factorial_recursive(n):
    ...

@in_cache
def factorial_for(n):
    ...

@in_cache
def factorial_meta(n):
    ...

@in_cache
def factorial_reduce(n):
    ...

## math.fatorial은 이미 정의되어 있다.

factorial = in_cache(math.factorial)

다섯 가지 함수를 모두 구현한다고 했을 때 캐시에 값을 확인하는 함수를 데코레이터로 감싸니 훨씬 이해하기 싶고 코드도 간결하다. 좋다. 동적 계획법을 아름답게 구현했다.

근데 첫 번째 방법(Don’t reinvent the wheel by yourself)은 다른 함수들과 달리 이미 함수가 정의되어 있는데 데코레이터를 어떻게 적용할까?

어렵지 않다. 원 함수를 in_cache 함수의 인자로 넣어 반환된 함수를 사용하는 것이다. 애초에 데코레이터가 하는 일이 저거다.

이제 우리는 데코레이터를 통해 깔끔하게 동적 계획법을 적용한 팩토리얼을 구현했다.

5. 마치며

파이썬으로 팩토리얼을 구하는 5가지 방법에 대해서 알아보았다. 그리고 데코레이터를 통한 동적 계획법까지 살펴봤다. 이게 참 어렵다. 데코레이터나 Iterator를 이전에 다루지 않았다보니 이 개념을 모두 설명하고 넘어가야 하는지, 아니면 독자분들이 이해하고 있다고 가정해도 되는지를 모르겠다. GA를 통해 살펴본 유저들의 유입 데이터를 보건대 다 이해하고 계시지는 않을 것 같은데 말이다.

일단 나는 파이썬의 원시 자료구조를 포함하는 collections, collections.abc 모듈에 관심이 많기 때문에 Iterator, Iterable, Generator, Sequence 등은 언젠가 다루어야겠다는 생각을 한다.

글쎄요. 수요가 있는 글을 썼는지 모르겠습니다. 팩토리얼은 너무 쉬운가요? 다음엔 좀더 어려운 알고리즘이나 내용을 살펴보도록 하겠습니다.

이상 포스트를 마칩니다.

6. 자료 출처

• Parkito’s on the way: 3 ways to get multiplication in a list in python
• Wikipedia: Metaprogramming
• Wikipedia: Reinventing the wheel