[백준BOJ] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 - JavaScript(node.js)

본 글은 백준 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 문제를 javascript를 이용하여 풀이한 내용이다.

---

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해 보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

 

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

예제 입력

7

 

출력

첫째 줄에 코드 1의 수행 횟수를 출력한다.

둘째 줄에 코드 1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

예제 출력

35
3

코드 1 이 35회 수행되고 알고리즘의 수행 시간이 n^3에 비례한다.

 

제한

• 시간 제한 : 1초
• 메모리 제한 : 512MB

1초에 최대 연산 횟수
O(N)	약 1억번
O(N^2)	약 1만번
O(N^3)	약 500번
O(2^N)	약 20번
O(N!)	10번

---

문제 풀이

해당 문제는 이전 문제와 비슷한 문제이다. 시간 복잡도에 대한 이해가 있는지 판단하는 문제이지만 위의 알고리즘 그대로 실행하면 시간초과가 발생한다. 시간 복잡도를 판단하기 위해서는 기본적으로 해당 구문의 for문의 개수 파악을 통해 알 수 있지만 3개의 for문이 1에서 n-2까지 범위와 i+1에서 n-1까지 범위와 j+1+에서 n까지 범위만큼 실행된다. 이를 for문 한 개로 줄이는 게 중요하다. 

이 문제는 여러 방식으로 풀 수 있는데 코드 1에 대한 설명 먼저 진행하겠다.

삼중 for문을 하나씩 실행해 보면

i=1   j=2  k=3,4,5,6,7... =n-2
        j=3  k=4,5,6,7,8... =n-3
        j=4  k=5,6,7,8,9... =n-4
        ...
        j=n-1 k=n =1
i=2   j=3  k=4,5,6,7... =n-3
        j=4  k=5,6,7,8... =n-4
        j=5  k=6,7,8,9... =n-5
        ...
        j=n-1 k=n =1     
 ...
 =>(n-2) * 1 + (n-3) * 2 + (n-4) * 3 +... + 1 * (n-2) 이러한 점화식을 얻을 수 있다. 이를 for문을 사용하여 작성한 것이 코드 1이다.

코드 2에서는 결국 이 문제의 핵심에 대하여 파악하면 풀 수 있다.

1에서 n까지 3개의 수를 뽑는 방법이 이와 같다. 이는 순열과 조합에서 조합을 사용하면 쉽게 풀 수 있다. 공식은 아래와 같다.

조합의 수 계산

n개 중 3개의 수를 순서에 상관없이 뽑는 방법을 계산해 보면 아래와 같다.

시간복잡도는 수학과 많은 연관이 되어 있기 때문에 쉽지 않을 수 있다.

해당 알고리즘을 다항식으로 나타내면 n^3에 해당된다. Big-O(빅오) 표기법으로 나타내면 O(N^3)이며 3차 시간이라고도 한다.

---

코드 1

const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt").toString().trim();
let num = BigInt(input);
let hap = 0n;
let getNum = num - 2n;
for (let i = 1n; i <= num - 1n; i++) {
    hap += getNum * i;
    getNum -= 1n;
}
console.log(`${hap}`);
console.log(3);

입력받는 부분 코드가 이해가 가지 않는다면 해당 글을 읽고 오길 추천한다.

코드 2

const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt").toString().trim();

const result = ( BigInt(input) * BigInt(input - 1) * BigInt(input - 2) ) / BigInt(6);
console.log(`${result}\n${3}`);

---

마무리

백준 브론즈단계 문제는 내가 처음에 이 글을 읽고도 이해되도록 최대한 자세하게 풀이하려고 노력하는데 막상 설명이 장황해져서 이해하기 힘들지는 않을까 걱정된다. javascript(node.js)로 풀이된 문제들을 찾기 힘든 경우들이 많을 수 도 있는데 최대한 다른 언어의 문제들로도 같이 보면서 해석할 줄 아는 힘을 기르도록 노력하자.

 

Github 구경하기