이진 탐색 Binary Search

🐶 이진 탐색 Binary Search

• 이미 정렬된 데이터에서 특정 원소를 찾을 때
• 시작점, 끝점, 중간점을 지정하여 수행함
• 찾으려는 값과 중간값을 비교하여 중간점 이후 혹은 이전으로 데이터 탐색의 범위를 절반으로 줄일 수 있음
  • 따라서 확인할 때마다 데이터의 개수가 절반으로 줄어들기 때문에 시간 복잡도 = O(logN)
• 탐색 범위가 1000만을 넘어갈 때 사용하면 좋다는 점!

recursion으로 구현한 이진 탐색

const n = 10, target=7;
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

function binarySearch(start, end, target) {
  let mid = Math.floor((start + end) / 2);
  if(start > end)  return -1;
  if(array[mid] === target)  return mid;

  array[mid] > target ? end = mid-1 : start = mid+1;
  return binarySearch(start, end, target);
}


const result = binarySearch(0, n-1, target);
if(result === -1)  console.log('원소가 존재하지 않습니다.');
else  console.log('output: ', result);

 

🐶 트리 자료구조

노드와 노드의 연결로 표현

노드는 정보의 단위로 어떠한 정보를 가지고 있는 개체

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드를 루트노드, 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라고 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

🐶 이진 탐색 트리

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

🐶 부품 찾기

/*
* 부품이 N개, 부품은 정수 형태의 고유한 번호를 가짐
* 손님이 M개 종류의 부품을 대량으로 구매하겠다고 요청함
* 가게에 부품이 모두 있는지 확인하는 프로그램
* output : 각 부품이 존재하면 yes를, 없으면 no를 출력함
* 계수 정렬, 자료형 set을 사용해서도 풀이할 수 있음
*/

const N = 5;
const list = [8, 3, 7, 9, 2];
const M = 3;
const request = [5, 7, 7];  // 5, 7, 9번 부품이 list에 있는지를 확인해야 함

list.sort(); // list 정렬

function BinarySearch(start, end, target) {
  let mid = Math.floor((start + end) / 2);
  if( start > end )  return -1;
  if( list[mid] === target )  return mid;
  list[mid] > target ? end = mid-1 : start = mid+1;
  return BinarySearch(start, end, target);
}

let answer = [];
for(req of request) {
  if(BinarySearch(0, N-1, req) === -1)  answer.push('no');
  else  answer.push('yes');
}
console.log(answer.join(' '));

 

 

🐶 떡볶이 떡 만들기

파라메트릭 서치(Parametric Search)

원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제

ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾는 최적화 문제

• 보통 이진 탐색을 이용하여 탐색하고자 하는 범위를 좁혀 나감
• 아이디어: 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것.
• 현재 이 높이로 자르면 조건을 만족할 수 있는가? => 만족 여부 예, 아니요에 따라 탐색 범위 좁히기
• 이 문제의 경우 떡볶이의 양에 따라서 자를 위치를 결정해야 하기 때문에 재귀적으로 짜기 보다는 반복문을 이용하면 더 간결하게 짤 수 있다

/*
* 떡의 개수는 1000000, 떡의 길이 M은 2000000000까지 입력 가능
* 첫쨰줄 input: 떡의 개수 N, 요청한 떡의 길이 M
* 둘째줄 input: 떡의 개별 높이 높이는 (10억보다 작거나 같은 양의 정수 또는 0)
* output: 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값
*/
const N=4, M=6;
const riceCakes = [19, 15, 10, 17];
const maxRice = riceCakes.sort().reverse()[0];
let start=0, end=maxRice;
let maxHeight = 0;

while(start <= end) {
  let mid = Math.floor((start + end) / 2);
  let length = 0;
  for(rice of riceCakes)
    if( rice - mid > 0 ) // 손님이 가져갈 수 있는 떡이 있으면
      length += rice - mid;
    
  if(length >= M) { // 떡의 양이 충분하면 떡을 덜 자름
    maxHeight = mid;
    start = mid + 1;
  }
  if(length < M)  end = mid-1; // 떡의 양이 부족하면 더 자름
}
console.log('result : ', maxHeight);