알고리즘/백준 온라인

프로그래밍_파이썬_백준_10872번_팩토리얼_재귀함수

혁오 2021. 11. 26. 16:31
BIG

안녕하세요. 오늘은 백준 온라인 10872번 팩토리얼에 대해서 풀어볼겁니다!

​

문제는 이렇습니다.

우선 팩토리얼에 대해서 알아봅시다

계승

[ factorial , 階乘 ]

요약 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다. 0!=1로 약속하고, n이 대단히 큰 경우 스털링의 공식을 써서 근삿값을 구할 수 있다.

1부터 n개의 양의 정수를 모두 곱한 것을 n계승이라 하고, n!로 나타낸다. 즉, n! = 1×2×3×……×(n-1)×n이다. n은 보통 양의 정수 범위에서 주어진다. n!＝n×(n－1)!의 성질에서 n이 1일 때 1=1×0! 이 되므로 0!=1로 약속한다.

​

​

계승은 순열과 조합의 공식에 자주 등장한다. 예를 들어, n개의 서로 다른 물건에서 순서를 고려하여 r개를 뽑는 순열의 경우의 수는

​

​

이다. 이 공식에서 r=n일 때에는 nPn= n·(n－1)· … ·3·2·1 = n!이 된다.

​

그리고 n개의 서로 다른 물건에서 순서에 상관없이 r개를 취하는 조합의 경우의 수는

​

​

이다.

​

n!은 n이 커지면 그 값이 급격히 커진다. 따라서 n이 대단히 큰 경우 실제값을 알기 어렵기 때문에 스털링의 공식을 써서 근삿값을 구한다.

​

(스털링의 공식)

[네이버 지식백과] 계승 [factorial, 階乘] (두산백과)

출처 : https://terms.naver.com/entry.naver?docId=1060921&cid=40942&categoryId=32206

​

요약하자면 영어로는 팩토리얼 한글로는 계승이라고 표현 하는군요

​

원리는 이렇습니다

​

if 9팩토리얼(이하 9!) 이면 -> 9*8*7*6*5*4*3*2*1 이런식으로 진행이 됩니다

128! -> 128*127*126*.......5*4*3*2*1 이렇게 됩니다. 값이 엄청나게 커지겠죠?

​

문제만 보고 어 이거 그냥 for문 돌려서 풀면 되는거 아냐라고 하실 수 있습니다.

ㄴ맞습니다. for문을 이용해도 되지만 알고리즘 실력 향상을 위해서 저는 재귀함수를 이용하였습니다

​

​

여기서 재귀함수가 무엇이냐는 분들에게 간단하게 말씀드리면

자기 자신을 호출하는 함수라고 생각하시면 됩니다.

만약 내가 함수 1을 만들어서 실행시키면 자기 자신인 함수1을 또 부르게됩니다.

그 불러진 함수1은 또 다시 함수1을 부르고요.

그래서 무한 루프에 빠지게 되어 조건을 걸어주어 탈출 조건을 주어야 합니다.

​

우선 이론적인 설명은 여기까지하고 코드로 직접 짜보았습니다.

​

​

for문으로도 간단하지만 재귀함수로도 되게 간단하게 표현됩니다.

#재귀함수 이용 팩토리얼 구하기
def factorial(x): #팩토리얼 함수
    if x==0: # 만약 x가 0이면 1을 반환해라
        return 1
    else:
        return x*factorial(x-1) # 만약 x가 0이 아니면 x*factorial(x-1)을 반환해라
                 ㄴ 재귀함수 사용
    x = int(input()) print(factorial(x))

 

이런식의 코드가 나왔는데

처음 입력을 만약 5를 해준다고 합시다.

if x==0: # 만약 x가 0이면 1을 반환해라
    return 1
else:
    return x*factorial(x-1) # 만약 x가 0이 아니면 x*factorial(x-1)을 반환해라

그럼 x에 5가 오게 되고 x는 0이 아닙니다

그래서 else항으로 가서 x*factorial(x-1)항이 반환되게 됩니다

​

이때, 이 값이 5*factorial(4) 가 되게 되는 겁니다.

마찬가지로 5*factorial(4)를 계산하려면 factorial(4)를 가야합니다.

​

​

다시 factorial(4)는

if x==0: # 만약 x가 0이면 1을 반환해라
    return 1
else:
    return x*factorial(x-1) # 만약 x가 0이 아니면 x*factorial(x-1)을 반환해라

0이 아니므로 4*factorial(3)이 됩니다.

즉 지금까지는 5*factorial(4) 인데

factorial(4) == 4*factorial(3) 인 것을 알 수 있습니다 -> 현재까지의 값 5*4*factorial(3)

factorial(3)을 또 계산해야 됩니다 이렇게 계속 반복될 것입니다

하지만 마지막 부분을 유의깊게 봅시다.

​

마지막은 결국 facotrial(0)이 될때가 있을 겁니다.

5*4*3*2*1*factorial(0)

​

def factorial(x): #팩토리얼 함수
    if x==0: # 만약 x가 0이면 1을 반환해라
        return 1
    else:
        return x*factorial(x-1) # 만약 x가 0이 아니면 x*factorial(x-1)을 반환해라
                    ㄴ 재귀함수 사용

이 때 factorial(0)은 x가 0이므로 1을 반환을 해줍니다.

그러면 결론적으로 값은 5*4*3*2*1*1이 될 것입니다.

BIG