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

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

---

문제

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

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

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

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

 

입력

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

예제 입력

7

 

출력

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

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

예제 출력

343
3

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

 

제한

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

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

---

문제 풀이

해당 문제는 이전 문제에 이어서 시간 복잡도에 대한 이해가 있는지 판단하는 문제이지만 나 또한 왜 틀렸는지 모르고 여러번 같은 코드를 작성했었다. 아마 이 글을 읽는 사람은 나와 같은 실수를 했을 것이라 생각된다.

node.js로 코딩한 사람들의 고뇌의 흔적

 

MenOfPassion 알고리즘에서 코드 1의 수행 횟수와 수행 횟수를 다항식으로 나타내었을 때, 최고차항을 알기 위해서는 해당 구문의 for문의 개수 파악을 통해 알 수 있다.

for문이 3개이고 1에서 n까지 범위만큼 실행된다. 따라서 해당 알고리즘은 실행하게 되면 n^3번 실행되며 다항식으로 나타내면 n^3에 해당된다. Big-O(빅오) 표기법으로 나타내면 O(N^3)이며 3차 시간이라고도 한다.

따라서 실행 횟수는 n^3, 다항식의 최고차항은 3이다.

여기까지는 동일한 내용이지만 우리가 하나 간과한 사항이 있다. JavaScript로 표현할 수 있는 Number의 범위가 -2^53+1에서 2^53-1(9,007,199,254,740,991)까지인데 문제 입력의 최대 범위는 이를 초과하는 125,000,000,000,000,000 값을 가지게 된다. 따라서 Number 대신 Number 범위를 넘는 숫자를 사용할 수 있게 해주는 BigInt를 사용해야한다.

여기서도 주의할 점은 BigInt를 그냥 사용할 경우 뒤에 n이 붙어서 나오게 된다. 따라서 이를 문자열로 다시 변경해줘야 우리가 원하는 숫자값을 출력할 수 있다.

---

코드

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

console.log(`${num * num * num}`);
console.log('3');

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

---

마무리

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

 

Github 구경하기