코딩테스트 - 이진탐색

개념

• 어떤 값을 찾을 때 정렬의 특징을 이용해 빨리 찾음
• 정렬되어있을 경우, 어떤 값 찾을때: O(N) => O(logN)
• 처음부터 생각하기 어려움, 쉬운방법부터 생각

핵심코드

function search(st, en, target){
  //시작과 끝이 만나면
  if(st == en){
    //~~
    return
  }
  
  //가운데 값 구하고
  const mid = Math.floor((st+en) / 2)
  //목표값보다 작으면
  if(nums[mid] < target){
   //시작점을 이동
   search(mid+1, en target) 
  } else { //목표값보다 작으면
   //끝점을 이동
   search(st, mid, target) 
  }

문제 1920

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
조건 : N(1 ≤ N ≤ 100,000) = 1e5, M(1 ≤ M ≤ 100,000) = 1e5

ex)
input:
5
4 1 5 2 3
5
1 3 7 9 5

output:
1
1
0
0
1

• 처음 아이디어 및 시간복잡도

  • M개의 수마다 각각 어디에 있는지 찾기
  • for : M개의 수 - O(M)
  • for : N개의 수안에 있는 확인 -> O(N)
  • O(MN) = 1e10(1백억) > 2억 = 시간초과

• M개를 확인해야하는데, 연속하다는 특징 활용 가능(투포인터)? => 불가

• 정렬해서 이진탐색 가능?

  • N개의 수 먼저 정렬
  • M개의 수 하나씩 이진탐색으로 확인

• 시간복잡도

  • N개의 수 정렬 : O(N*logN)
  • M개의 수 정렬 : O(M*logN)
  • O((N+M)logN) = 2e5 * 20 = 4e6 => 가능
  • logN = log2N = log2 * 10^3
  • 10^3^2 = 2^10^2 -> 2의 10승은 10의 3승과 같음 = log2 * 2^20 = 20

• 자료구조

  • 탐색 대상 수 : int[]
  • 탐색 하려는 수 : int[]

코드

//이진탐색
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", () => {
  /*
1. 아이디어
- N개의 숫자를 정렬
- M개를 for 돌면서, 이진탐색
- 이진탐색 안에서 마지막에 데이터 찾으면, 1출력, 아니면 0출력

2. 시간복잡도
- N개의 입력값 정렬 = O(N*lgN)
- M개의 입력값 정렬 = O(M*lgN)
- O((N+M)lgN) > 가능

3. 자료구조
- N개의 숫자 = []
- M개의 숫자 = []
*/

  const N = parseInt(input[0]);
  const nums = input[1].split(" ").map(Number);
  const M = parseInt(input[2]);
  const target_list = input[3].split(" ").map(Number);

  //정렬해주고
  nums.sort((a, b) => a - b);

  function search(st, en, target) {
    if (st == en) {
      if (nums[st] == target) {
        console.log(1);
      } else {
        console.log(0);
      }
      return;
    }

    const mid = Math.floor((st + en) / 2);

    if (nums[mid] < target) {
      search(mid + 1, en, target);
    } else {
      search(st, mid, target);
    }
  }

  for (const index in target_list) {
    search(0, N - 1, target_list[index]);
  }
});

알아야할것

• 처음부터 생각하기 어렵다, 쉬운방법부터 생각한다 -> 2중 for
  • 어떤 값을 여러번 탐색해야 하는 경우
• 입력의 개수가 1e5정도의 경우라면 의심해봐라