Factorial

Q: 팩토리얼을 계산하는 시간 복잡도는 무엇인가요?

루프와 재귀 모두 n 까지의 각 숫자에 대해 곱셈을 한 번씩 수행하므로 시간 복잡도는 O(n) 입니다. 루프는 추가 공간 O(1) 이 필요합니다. 재귀는 기저 사례가 반환될 때까지 호출마다 스택 프레임 하나를 유지하므로 공간 복잡도는 O(n) 입니다.

Q: 0!은 왜 1과 같을까요?

0! 은 아무 숫자도 곱하지 않은 곱이며, 인수가 없는 곱은 1 입니다. 항이 없는 합이 0 인 것과 같습니다. 또한 n = 1 일 때도 n! = n × (n-1)! 이라는 규칙이 성립합니다. 1! = 1 × 0! = 1 입니다. 경우의 수를 세어도 같은 결과를 얻습니다. 항목이 0개일 때 배열하는 방법은 정확히 한 가지입니다.

Q: 팩토리얼을 구할 때 재귀와 반복문 중 어느 것이 더 좋을까요?

두 방법은 같은 곱셈을 수행하고 같은 답을 반환합니다. 재귀 버전은 수학적 정의처럼 읽히므로, 재귀를 처음 연습할 때 자주 사용되는 고전적인 예제입니다. 반복문은 일정한 메모리만 사용하고 호출 스택이 넘칠 수 없으므로, 실제 코드에서는 더 나은 선택입니다.

Q: 정수에 들어갈 수 있는 가장 큰 팩토리얼은 무엇인가요?

12! = 479001600 은 부호 있는 32비트 정수에 들어가는 가장 큰 팩토리얼입니다. 20! = 2432902008176640000 은 부호 있는 64비트 정수에 들어가는 가장 큰 팩토리얼입니다. 그보다 큰 수를 다루려면 Python의 int , Java의 BigInteger 또는 JavaScript의 BigInt 와 같이 크기에 제한이 없는 숫자가 필요합니다.

입문수학과 시뮬레이션 재귀

+10

정수 n의 계승은 n!로 표기하며, 1부터 n까지 모든 정수의 곱입니다. 예를 들어, 4! = 1 × 2 × 3 × 4 = 24입니다. 정의에 따라 0! = 1입니다. 함수는 n을 받아 n!을 반환합니다.

함수

factorial(n: integer) → integer

ninteger: 팩토리얼을 계산하는 정수
반환값integer: 1부터 n까지 모든 정수의 곱이며, n이 0일 때는 1입니다.

제약 조건

0 ≤ n ≤ 12
답은 부호 있는 32비트 정수에 들어갑니다. 가장 큰 값은 12! = 479001600입니다.

예제

입력: n = 5
출력: 120
설명: 1 × 2 × 3 × 4 × 5를 곱하세요. 누적 곱은 1, 2, 6, 24가 되고 마지막에는 120이 됩니다.

입력: n = 0
출력: 1
설명: 곱할 것이 없으며, 인수가 없는 곱은 1입니다. 그래서 0! = 1입니다.

제출 시 숨은 테스트 +11개

후속 질문

100!은 158자리입니다. 계산하지 않고 끝에 0이 몇 개 있는지 셀 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

팩토리얼은 서로 동등한 두 가지 설명이 있으며, 각각 코드로 바꿀 수 있습니다. 곱으로 표현하면 n! = 1 × 2 × ... × n이며, 이는 반복문입니다. 재귀적 정의로 표현하면 0! = 1이고 n! = n × (n-1)!이며, 이는 자기 자신을 호출하는 함수입니다. 둘 다 대략 n번 곱셈을 수행합니다. 마무리할 때는 반복문을 사용하는 편이 좋습니다. 호출 스택이 필요하지 않기 때문입니다.

정의에서 출발하는 재귀

핵심 아이디어

팩토리얼은 더 작은 팩토리얼을 통해 정의됩니다: n! = n × (n-1)!. 이미 4! = 24라는 것을 알고 있다면, 5! = 5 × 24 = 120입니다. 재귀 함수는 이 문장을 코드로 작성합니다. factorial(n)을 구하기 위해 factorial(n-1)을 호출하고 그 결과에 n을 곱합니다.

호출이 멈출 지점인 기본 사례가 필요합니다: factorial(0)은 아무것도 호출하지 않고 1을 반환합니다. 호출할 때마다 n이 1씩 줄어드므로, 5부터 시작하면 호출은 5, 4, 3, 2, 1, 0 순으로 이어집니다. 그런 다음 결과가 호출 체인을 따라 되돌아옵니다: 1, 1, 2, 6, 24, 120.

호출은 n + 1회, 곱셈은 n회 이루어지므로 시간 복잡도는 O(n)입니다. 각 호출은 그 아래 호출이 반환할 때까지 스택에서 대기하므로, 스택에는 n + 1개의 프레임이 쌓이며 공간 복잡도는 O(n)입니다. n ≤ 12일 때는 아주 작지만, 큰 입력에 같은 패턴을 적용하면 스택이 넘칩니다.

알고리즘

n이 0이면 1을 반환합니다. 이것이 기본 사례입니다.
그렇지 않으면 n-1에 대해 함수를 호출합니다.
그 결과에 n을 곱한 후 반환합니다.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

반복문에서 곱하기

핵심 아이디어

재귀를 풀어 쓰면 누적 곱을 얻습니다. result = 1에서 시작해 여기에 2를 곱하고, 그다음 3을 곱하는 식으로 n까지 계속합니다. n = 5일 때 결과는 1, 2, 6, 24, 120이 됩니다.

1에서 시작하면 가장 작은 입력도 처리할 수 있습니다. n = 0과 n = 1일 때 2부터 n까지의 루프는 0회 실행되며, 함수는 시작값 1을 반환합니다. 두 경우 모두 정답입니다.

루프는 n-1번 곱셈을 수행하므로 시간 복잡도는 O(n)이고, 숫자 하나만 유지하므로 공간 복잡도는 O(1)입니다. 오버플로될 호출 스택이 없기 때문에, 재귀 버전을 보여 준 뒤에는 면접관들이 이 버전을 기대합니다.

알고리즘

result = 1로 설정합니다.
k를 2부터 n까지(둘 다 포함) 반복합니다.
각 단계에서 result에 k를 곱합니다.
result를 반환합니다.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

함정과 경계 사례

팩토리얼 코드는 짧으므로 버그는 경계에 있습니다.

곱의 시작값을 0으로 설정하기. 곱셈을 할 때마다 값은 0으로 유지됩니다. 곱의 시작값은 1입니다.
n == 1에서만 재귀를 멈추기. 0을 전달해 호출하면 함수는 기본 사례에 도달하지 못하고, 스택이 넘칠 때까지 -1, -2 등으로 계속 진행됩니다. n == 0을 기본 사례로 만드세요.
k ≤ n 대신 k < n으로 반복하기. 그러면 마지막 인수가 빠져 (n-1)!을 반환하므로, 5의 결과는 120이 아니라 24가 됩니다.
오버플로를 무시하기. 13! = 6227020800은 부호 있는 32비트 정수에 들어가지 않습니다. Java와 C#에서는 곱의 값이 조용히 순환해 잘못된 숫자가 되고, C에서는 부호 있는 오버플로의 동작이 정의되지 않으며, Rust 디버그 빌드에서는 패닉이 발생합니다. 64비트 정수는 최대 20!까지 저장할 수 있습니다. 그보다 큰 값에는 큰 정수가 필요합니다.
Swift에서 for k in 2...n을 작성하기. 끝값이 시작값보다 작은 폐구간은 n이 0 또는 1일 때 런타임에 충돌합니다.

자주 묻는 질문4

팩토리얼을 계산하는 시간 복잡도는 무엇인가요?

루프와 재귀 모두 n까지의 각 숫자에 대해 곱셈을 한 번씩 수행하므로 시간 복잡도는 O(n)입니다. 루프는 추가 공간 O(1)이 필요합니다. 재귀는 기저 사례가 반환될 때까지 호출마다 스택 프레임 하나를 유지하므로 공간 복잡도는 O(n)입니다.

0!은 왜 1과 같을까요?

0!은 아무 숫자도 곱하지 않은 곱이며, 인수가 없는 곱은 1입니다. 항이 없는 합이 0인 것과 같습니다. 또한 n = 1일 때도 n! = n × (n-1)!이라는 규칙이 성립합니다. 1! = 1 × 0! = 1입니다. 경우의 수를 세어도 같은 결과를 얻습니다. 항목이 0개일 때 배열하는 방법은 정확히 한 가지입니다.

팩토리얼을 구할 때 재귀와 반복문 중 어느 것이 더 좋을까요?

두 방법은 같은 곱셈을 수행하고 같은 답을 반환합니다. 재귀 버전은 수학적 정의처럼 읽히므로, 재귀를 처음 연습할 때 자주 사용되는 고전적인 예제입니다. 반복문은 일정한 메모리만 사용하고 호출 스택이 넘칠 수 없으므로, 실제 코드에서는 더 나은 선택입니다.

정수에 들어갈 수 있는 가장 큰 팩토리얼은 무엇인가요?

12! = 479001600은 부호 있는 32비트 정수에 들어가는 가장 큰 팩토리얼입니다. 20! = 2432902008176640000은 부호 있는 64비트 정수에 들어가는 가장 큰 팩토리얼입니다. 그보다 큰 수를 다루려면 Python의 int, Java의 BigInteger 또는 JavaScript의 BigInt와 같이 크기에 제한이 없는 숫자가 필요합니다.

Python

def factorial(n):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

n = 5

기대값