[바미] 이항 계수 1

문제

https://www.acmicpc.net/problem/11050

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ');

const N = parseInt(input[0], 10);
const K = parseInt(input[1], 10);

function factorial(n) {
    if (n === 0 || n === 1) return 1;
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

function binomialCoefficient(n, k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

const result = binomialCoefficient(N, K);
console.log(result);

문제 해설

이항 계수는 주어진 두 수 𝑁과 𝐾에 대해, 𝑁개의 원소 중 𝐾개를 선택하는 방법의 수를 나타냅니다.

이항 계수는 아래와 같은 수식으로 정의됩니다.

 

위 식에서 !는 팩토리얼을 의미하기 때문에 이항 계수를 계산하기 위해서는 팩로리얼을 계산하는 함수를 사용하여 계산할 수 있습니다.

 

따라서  팩토리얼을 계산하는 factorial함수와 이항 계수를 계산하는 binomialCoefficient를 만들어 해결하였습니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

팩토리얼 계산의 시간 복잡도는 𝑂(𝑛)이 됩니다.

그리고 이항 계수의 공식에 따라 주어진 N과 K에 대해 팩토리얼을 세 번 계산하게 되는데 각 계산의 시간의 시간 복잡도는 𝑂(𝑛)이 됩니다.

 

따라서 전체 시간 복잡도는 𝑂(𝑛)이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

입력과 결과를 저장하는 변수들이 사용되고, 추가적으로 팩토리얼 계산을 위한 몇 개의 변수들이 사용됩니다. 

각 변수들은 모두 상수 공간을 차지하므로 전체 공간 복잡도는 𝑂(1)이 됩니다.