팩토리얼로 bottom-up과 top-down 구분하기

paul 2025.01.19 324words (1m)

팩토리얼은 답이 뻔해서 오히려 형태를 비교하기 좋다. 같은 계산을 다섯 가지로 써봤다.

반복문

python 
n = 5
f = 1

for i in range(1, n + 1):
    f *= i

이걸 "dynamic의 특수한 경우"로 봤다. 작은 것부터 차례로 구해서 다음 계산에 쓰는 구조가 같고, 다만 앞의 값 하나만 필요해서 배열이 아니라 변수 하나로 끝난 것이다.

아래에서 위로 쌓기

python 
n = 5
f = [1]

for i in range(1, n + 1):
    f.append(i * f[i - 1])

print(f[n])

중간값을 전부 배열에 남긴다. f[3] 이 필요해지면 다시 계산하지 않고 꺼내 쓴다. 팩토리얼에서는 남길 이유가 없지만 형태는 이게 tabulation이다.

같은 걸 재귀로도 쓸 수 있다.

python 
def fact(i):
    if i == n + 1:
        return f[n]

    f.append(i * f[i - 1])
    return fact(i + 1)

재귀를 쓰지만 방향은 위와 같다. 작은 것부터 채워 올라가고, 다 채우면 마지막 값을 돌려준다. 재귀냐 반복이냐와 bottom-up이냐 top-down이냐는 다른 축이라는 게 여기서 보인다.

위에서 아래로 내려가기

python 
def fact(i):
    if i == n + 1:
        return 1

    return i * fact(i + 1)

이건 쌓아두는 게 없다. 부르고 부르고 부르다가 끝에서 1을 돌려주면 돌아오면서 곱해진다. 중간값을 저장하지 않으므로 같은 값을 두 번 계산해야 하는 문제였다면 그대로 두 번 계산한다.

메모이제이션

python 
def fact(i):
    if i not in f:
        f[i] = i * fact(i - 1)
        return f[i]
    return f[0]

n = 5
f = {0:1}

위에서 아래로 내려가되 결과를 dict에 남긴다. 이미 있으면 계산하지 않고 꺼낸다.

if 에 걸리지 않았을 때 f[i] 가 아니라 f[0] 을 돌려주는 게 눈에 걸린다. 그런데 답은 120으로 맞게 나온다. 미리 넣어둔 키가 0 하나뿐이고, 내려가다 이미 있는 키를 만나는 경우가 i == 0 일 때뿐이라 f[0] 과 f[i] 가 같은 값이라서 그렇다.

한 번만 부르면 문제가 안 드러난다. 같은 f 를 두고 fact 를 다시 부르면 그때는 이미 채워진 값을 만나게 되고 전부 1이 나온다.