[바미] 팩토리얼
문제
https://www.acmicpc.net/problem/10872
코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input, 10);
function factorial(n) {
if (n === 0) return 1;
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}
const result = factorial(N);
console.log(result);문제 해설
팩토리얼은 수학적으로 정의된 함수로 특정 양의 정수 𝑁에 대해 𝑁 !은 1부터 𝑁까지의 모든 양의 정수를 곱한 값입니다.
이를 수식으로 나타내면 다음과 같습니다.
N!=N×(N−1)×(N−2)×…×1
또한 팩토리얼은 다음과 같은 재귀적 정의를 가지고 있습니다.
0! = 1 (기본 경우)
𝑁! = 𝑁 × (𝑁 − 1)! (N > 0인 경우)
주어진 문제는 0보다 크거나 같은 정수 N이 주어졌을 때 N! (N 팩토리얼)을 계산하는 문제입니다.
N은 0부터 12까지의 범위를 가지기 때문에 간단한 반복문을 사용하여 팩토리얼을 계산할 수 있습니다.
시간 복잡도
시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다
factorial(n) 함수는 반복문을 통해 n번 곱셈 연산을 수행하기 때문에 시간 복잡도는 O(n)이 됩니다.
공간 복잡도
공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.
- N은 입력을 저장하는 정수 변수로 공간 복잡도는 O(1)이 됩니다.
- result 변수는 계산된 결과를 저장하는 정수 변수이기 때문에 공간 복잡도는 O(1)이 됩니다.
- 함수 호출 스택의 깊이는 최대O(1)이 됩니다.
따라서 전체 코드의 공간 복잡도는 O(1)이 됩니다.
팩토리얼 문제를 해결할 때 대부분은 재귀적으로 해결하려 하지만 반복문을 사용한 접근이 더 효율적입니다.
재귀적인 접근과 반복문을 사용한 접근을 비교하며 설명해보도록 하겠습니다.
재귀적 접근 방식
재귀적 접근은 함수가 자기 자신을 호출하는 방식으로 아래와 같이 구현 할 수 있습니다.
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}반복적 접근
반복문을 사용하여 팩토리얼을 계산할 때 아래와 같이 구현 할 수 있습니다.
명시적으로 루프를 돌며 곱셈을 해주는 형태죠.
function factorial(n) {
if (n === 0) return 1;
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}왜 반복문 접근이 좋은가?
재귀적 접근의 문제점은 함수 호출 오버헤드와 메모리 사용에 대한 이슈가 있습니다.
재귀적 접근은 함수 호출이 중첩되는 방식으로 실행되기 때문에 많은 함수 호출이 발생합니다.
이 함수 호출에는 스택에 저장해야 할 정보들이 있고, 이러한 호출이 많이 쌓이면 스택 오버플로우(stack overflow)가 발생할 수 있기 때문이죠.
그리고 재귀 함수는 호출될 때마다 호출 스택에 현재 상태를 저장하므로 깊이가 깊어질수록 더 많은 메모리를 사용하게 됩니다.
특히 N이 큰 경우에는 재귀 호출이 많아지면서 메모리 사용량이 급격히 증가하게 되죠.
그래서 반복문을 사용하는 방식은 함수 호출을 하지 않기 때문에 함수 호출 오버헤드를 피하기 때문에 실행 시간이 단축 되게 되고,
반복문은 추가 적인 함수 호출 없이 루프를 돌면서 계산을 진행하기 때문에 호출 스택에 추가적인 메모리를 할당하지 않습니다.
따라서 재귀적 접근은 코드가 간결하고 직관적일 수 있지만, 함수 호출 오버헤드와 메모리 사용 측면에서 비효율적이지만 반복적 접근은 루프를 통해 명시적으로 계산을 진행하기 때문에 함수 호출 오버헤드가 없고 메모리 사용도 최소화할 수 있어 더 효율적입니다.
특히 문제에서 주어진 범위 (0 ≤ N ≤ 12) 내에서는 반복적 접근이 더욱 적합합니다.