[코딩 테스트] 10일차: 탐색 알고리즘

탐색 알고리즘

탐색 알고리즘은 주어진 데이터 집합에서 특정 값을 찾는 방법입니다. 이번 글에서는 가장 기본적인 탐색 알고리즘인 선형 탐색과 효율적인 탐색 알고리즘인 이진 탐색에 대해 알아보겠습니다.

선형 탐색 (Linear Search)

선형 탐색은 배열의 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 방법입니다. 시간 복잡도는 O(n)입니다.

JavaScript에서의 선형 탐색 구현

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

let arr = [2, 3, 4, 10, 40];
let target = 10;
console.log(linearSearch(arr, target)); // 3

Python에서의 선형 탐색 구현

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

arr = [2, 3, 4, 10, 40]
target = 10
print(linear_search(arr, target)) # 3

이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 절반으로 줄여가며 값을 찾는 방법입니다. 시간 복잡도는 O(log n)입니다.

JavaScript에서의 이진 탐색 구현

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;
}

let arr = [2, 3, 4, 10, 40];
let target = 10;
console.log(binarySearch(arr, target)); // 3

Python에서의 이진 탐색 구현

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

arr = [2, 3, 4, 10, 40]
target = 10
print(binary_search(arr, target)) # 3

재귀를 이용한 이진 탐색

이진 탐색은 재귀를 이용하여 구현할 수도 있습니다.

JavaScript에서의 재귀를 이용한 이진 탐색 구현

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;
  }

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

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

let arr = [2, 3, 4, 10, 40];
let target = 10;
console.log(binarySearchRecursive(arr, target)); // 3

Python에서의 재귀를 이용한 이진 탐색 구현

def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

arr = [2, 3, 4, 10, 40]
target = 10
print(binary_search_recursive(arr, target)) # 3

연습 문제

문제 1: 제곱근 계산

주어진 정수의 제곱근을 이진 탐색을 이용하여 구하는 프로그램을 작성하세요.

JavaScript

function sqrt(n) {
  if (n < 0) return -1;

  let left = 0;
  let right = n;
  let ans = -1;

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

    if (midSq === n) {
      return mid;
    } else if (midSq < n) {
      left = mid + 1;
      ans = mid;
    } else {
      right = mid - 1;
    }
  }

  return ans;
}

let n = 16;
console.log(sqrt(n)); // 4

Python

def sqrt(n):
    if n < 0:
        return -1

    left, right = 0, n
    ans = -1

    while left <= right:
        mid = (left + right) // 2
        mid_sq = mid * mid

        if mid_sq == n:
            return mid
        elif mid_sq < n:
            left = mid + 1
            ans = mid
        else:
            right = mid - 1

    return ans

n = 16
print(sqrt(n)) # 4

문제 2: 회전 정렬 배열에서의 탐색

회전된 정렬 배열에서 주어진 값을 찾는 프로그램을 작성하세요. 시간 복잡도는 O(log n)이어야 합니다.

JavaScript

function searchRotatedArray(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;
    }

    // 왼쪽 반이 정렬된 경우
    if (arr[left] <= arr[mid]) {
      if (target >= arr[left] && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // 오른쪽 반이 정렬된 경우
    else {
      if (target > arr[mid] && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

let arr = [4, 5, 6, 7, 0, 1, 2];
let target = 0;
console.log(searchRotatedArray(arr, target)); // 4

Python

def search_rotated_array(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        # 왼쪽 반이 정렬된 경우
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽 반이 정렬된 경우
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

arr = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search_rotated_array(arr, target)) # 4

결론

이번 글에서는 코딩 테스트 준비를 위해 탐색 알고리즘에 대해 배웠습니다. 이를 통해 선형 탐색, 이진 탐색의 개념과 구현 방법을 익힐 수 있었습니다. 다음 글에서는 재귀와 백트래킹에 대해 알아보겠습니다.

다음 글에서 만나요!