ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [λ°±μ€€] 24262번: μ•Œκ³ λ¦¬μ¦˜ μˆ˜μ—… - μ•Œκ³ λ¦¬μ¦˜μ˜ μˆ˜ν–‰ μ‹œκ°„ 1 (Node.js)
    πŸ“ μ•Œκ³ λ¦¬μ¦˜/λ°±μ€€ 2024. 9. 9. 11:19

     

    접근방식

    μ•Œκ³ λ¦¬μ¦˜μ˜ μ‹œκ°„ λ³΅μž‘λ„μ— λŒ€ν•΄ λ‹€λ£¨λŠ” 기초문제이며 μ œμ‹œλœ μ½”λ“œμ˜ μ‹œκ°„λ³΅μž‘λ„λ₯Ό λΆ„μ„ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.

     

    이 문제λ₯Ό ν’€κΈ° μœ„ν•΄μ„œ 기본적으둜 μ•Œμ•„λ‘μ…”μ•Ό ν•  것이 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

Designed by Tistory.