완전탐색과 이분탐색

완전탐색이란

완전탐색은 가능한 모든 경우의 수를 전부 탐색하여 문제의 해를 찾는 방법입니다. 이 방법은 간단하고 확실하지만, 데이터의 크기가 커질수록 시간 복잡도가 급격히 증가합니다.

주요 특징:

• 모든 가능성을 고려하므로 항상 정확한 답을 찾을 수 있습니다.
• 구현이 비교적 간단합니다.
• 작은 크기의 입력에 대해 효과적입니다.

장점:

• 모든 경우를 고려하므로 항상 정확한 결과를 얻습니다.
• 구현이 간단하고 직관적입니다.

단점:

• 시간 복잡도가 높아 큰 데이터셋에서는 비효율적입니다.
• 문제의 크기가 커질수록 실행 시간이 기하급수적으로 증가합니다.

이분탐색이란

이분탐색은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 중간 값을 기준으로 탐색 범위를 절반씩 줄여가며 빠르게 원하는 값을 찾습니다.

주요 특징:

• 정렬된 데이터에서만 사용 가능합니다.
• 탐색 범위를 절반씩 줄이므로 매우 효율적입니다.
• 시간 복잡도는 O(log n)으로, 대규모 데이터에서도 빠른 검색이 가능합니다.

장점:

• 대규모 데이터에서도 빠른 검색이 가능합니다.
• 시간 복잡도가 O(log n)으로 매우 효율적입니다.

단점:

• 정렬된 데이터에서만 사용 가능합니다.
• 데이터가 자주 변경되는 경우, 정렬 상태를 유지하는 데 추가 비용이 발생합니다.

차이점

1. 탐색 방식:
   • 완전탐색: 모든 가능한 경우를 순차적으로 탐색합니다.
   • 이분탐색: 중간 값을 기준으로 탐색 범위를 절반씩 줄여갑니다.
2. 시간 복잡도:
   • 완전탐색: O(n) 또는 그 이상 (경우에 따라 지수 시간 복잡도)
   • 이분탐색: O(log n)
3. 적용 가능한 데이터:
   • 완전탐색: 모든 종류의 데이터에 적용 가능
   • 이분탐색: 정렬된 데이터에만 적용 가능

사용 예시

완전탐색 예시

• 비밀번호 크래킹: 가능한 모든 조합을 시도
• 배낭 문제: 모든 물건의 조합을 고려하여 최적의 조합 찾기
• 순열/조합 문제: 모든 가능한 경우의 수를 생성

이분탐색 예시

• 사전에서 단어 찾기
• 정렬된 배열에서 특정 값의 존재 여부 확인
• 최적화 문제에서 최솟값 또는 최댓값 찾기

JS로 코드 구현한 완전탐색, 이분탐색

완전탐색

function permute(arr) {
  const result = [];

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, remaining.slice(0, i).concat(remaining.slice(i + 1)));
      current.pop();
    }
  }

  backtrack([], arr);
  return result;
}

이분탐색

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}