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

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

---

문제

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

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

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

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

 

 

입력

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

예제 입력

1

 

출력

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

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

예제 출력

1
0

 

제한

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

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

---

문제 풀이

해당 문제는 시간 복잡도에 대한 이해가 있는지 판단하는 가장 기본적인 문제이다.

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

해당 알고리즘은 실행하게 되면 단 1번만 실행되며 다항식으로 나타내면 1에 해당된다. Big-O(빅오)표기법으로 나타내면 O(1)이며 상수 시간이라고도 한다.

따라서 실행횟수는 1, 다항식의 최고차항은 0이다.

---

코드

console.log(1);
console.log(0);

---

마무리

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

 

Github 구경하기