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

 

 

접근방식

이번 문제는 알고리즘의 수행시간3과 비슷해보이지만 반복문의 범위가 다릅니다.

반복문의 입력 크기 n에 대해 선형적으로 실행되더군요.

 

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

---------------------------------------------------------

for(let i=0; i<n; i++) {
    for(let j=i+1; j<n; j++) {

    }
  }

 

우선 보기 쉽게 javascript로 변형해보았습니다.

 

외부 반복문과 내부 반복문으로 나눠서 보겠습니다.

 

외부 반복문

i는 0부터 n-1번까지 반복합니다.

이 말은 즉, 우리가 잘 알고 있듯이 n번 반복을 의미합니다.

 

내부 반복문

j는 i+1부터 n-1번까지 반복합니다.

 

i = 0 일 때, j는 1부터 n-1번 반복합니다.

i = 1 일 때, j는 2부터 n-1번 반복합니다.

i = n-1 일 때는 j = n 이므로 n < n 이 성립되지 않아 반복하지 못합니다.

i = n-2 일 때는 j = n-1 이므로 딱 1번 실행됩니다.

 

그럼 j 루프에서 반복되는 횟수는 등차수열의 합에 의해

항의 총갯수(첫항 + 마지막항) / 2 를 해주게 되면

n ( n - 1 ) / 2 가 되므로 시간 복잡도는 O(n^2)가 됩니다.

 

혹시 모를 참조글을 남겨두고 풀이를 진행하겠습니다.

 

참조 💬

왜 외부는 계산하지 않고 내부만 계산하여 푸는지?

 

외부와 내부를 각각 따로 계산하는 것이 아닌, 전체 반복 횟수를 계산할 때에는

외부 반복문과 내부 반복문을 함께 고려하는 것입니다.

다만, 외부 반복문은 항상 n번 반복되는 고정된 부분이기 때문에, 주된 시간 복잡도를 결정하는 것은

내부 반복문이 얼마나 자주 실행되는지입니다.

 

외부 반복문 : for(let i=0; i<n; i++) 으로 항상 n번 반복됩니다.

내부 반복문 : for(let j=i+1; i<n; j++) 으로 각 i에 대해 반복 횟수가 달지면서 위에 계산했듯이

n ( n - 1 ) / 2 번 반복됩니다.

 

외부 반복문 자체는 n번 반복되지만, 내부 반복은 각 i마다 다른 횟수로 실행하기 때문에

주된 시간 복잡도를 결정하 것은 내부 반복문이 얼마나 자주 실행되는지 입니다.

 

 

 

풀이 ⏰

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) {
  //     sum <- 0;
  //     for i <- 1 to n
  //         for j <- 1 to n
  //             sum <- sum + A[i] × A[j]; # 코드1
  //     return sum;
  // }
  let n = Number(input[0]);
  n = (n * (n - 1)) / 2;
  console.log(n);
  console.log(2);
});

 

백준 24265번 링크

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