분할 정복

• 문제를 중복이 안 일어나게 쪼개서 (주로 절반) 푸는 알고리즘

이분 탐색

• 정렬되어 있는 리스트에서 특정 값을 빠르게 찾는 알고리즘
• 시간복잡도: 정렬 O(NlogN) + 탐색 O(logN)
• 이분 탐색으로 정답 찾기
  • 하나의 기준으로 가능/불가능 여부가 나누어질 때 이분 탐색 방법을 활용하여 해결
• 구현

  const binarySearch = (array, target) => {
    let left = 0;
    let right = array.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (array[mid] === target) {
        return mid;
      }
      if (array[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  };

머지 소트

퀵 소트

• 평균 O(NlogN), 최악 O(N^2)

버블 소트

• 앞에서 부터 연속한 두 수를 비교해 교환하며 정렬