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

 

접근방식

알고리즘의 시간 복잡도에 대해 다루는 기초문제이며 제시된 코드의 시간복잡도를 분석하는 문제입니다.

 

이 문제를 풀기 위해서 기본적으로 알아두셔야 할 것이 2가지가 있는데,

시간복잡도와 Big-O 표기법입니다.

 

1. 시간복잡도

알고리즘이 얼마나 빨리 실행되는지를 측정하는 기준입니다.

즉, 입력의 크기(데이터 양)가 커지면 알고리즘이 얼마나 더 많은 시간을 필요로 하는지를 보는 것입니다.

 

예를 들어

let sum = 0;
for(let i=0; i<n; i++) {
  sum += arr[i];
}

 

n = 3 이면 3개의 숫자를 더해야 하므로 연산이 3번 일어납니다.

n = 1000이라면 1000개의 숫자를 더해야 하므로 연산이 1000번 일어납니다.

 

즉, 배열의 크기에 비례해서 연산 횟수도 늘어납니다.

결국 배열의 합을 구할 때, 배열의 크기가 커질수록 더 많은 시간이 걸리는데,

이 과정에서 시간 복잡도는 O(n)이며, 입력 크기 n에 비례해서 시간이 걸린다는 의미를 가지고 있습니다.

 

2. Big - O 표기법

Big-O 표기법은 시간복잡도를 표현하는 방법 중 하나로, 알고리즘의 성능을 입력 크기 n에 대한

함수로 나타냅니다. Big-O는 입력 크기가 매우 클 때, 즉 n이 무한대로 커질 때 시간복잡도가

어떻게 변하는지 나타냅니다.

• O(1) : 입력 크기와 상관없이 항상 일정한 시간.
• O(n) : 입력 크기에 비례해서 시간이 늘어나는 경우.
• O(n^2) : 입력 크기에 따라 시간이 급격히 늘어나는 경우

 

 

그 외에도 로그 시간 복잡도, 선형 로그 시간, 지수 시간, 팩토리얼 시간 등등이 많지만 여기에선

위 3개만 다뤄보았습니다.😎

 

 

예시: O(1)

let a = 0;

이 코드는 입력 크기에 상관없이 단 한번의 연산으로 끝나게됩니다.

입력 크기가 아무리 커져도 이 작업에는 항상 일정한 시간이 걸리므로 O(1) 입니다.

 

예시: O(n)

for (int i = 0; i < n; i++) {
  if (arr[i] == target) {
    return i;
  }
}

 

이 코드는 배열 전체를 탐색해야 하므로 시간 복잡도는 O(n)입니다.

 

예시: O(n^2)

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
  	
  }
}

 

이 코드는 두 개의 이중 루프가 있기 때문에 시간 복잡도는 O(n^2)입니다.

 

 

 

풀이 ⏰

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  // MenOfPassion(A[], n) {
  //   i = ⌊n / 2⌋;
  //   return A[i]; # 코드1
  // }
  
  // 함수의 시간 복잡도가 상수 시간이므로 1을 출력
  console.log(1);
  // 다항식의 최고차항 차수는 0이므로 0을 출력
  console.log(0);
});

 

백준 24262번 링크

👉 https://www.acmicpc.net/problem/24262