본문으로 건너뛰기

Day 4: 탐욕법(Greedy) & 이분탐색(Binary Search)

이번 섹션에서는 두 가지 핵심 알고리즘 기법을 다룬다.
탐욕법은 각 단계에서 최적이라고 판단되는 선택을 통해 문제의 해답에 접근하는 방법이며, 이분탐색은 정렬된 배열 내에서 빠르게 특정 요소를 찾는 알고리즘이다.

1. 탐욕법 (Greedy)​

1.1 기본 개념​

  • 정의:
    탐욕법은 문제를 여러 단계로 나눈 후, 각 단계에서 가장 최적의 선택(탐욕적 선택, Greedy Choice)을 하여 전체 해답을 구하는 접근법이다.

  • 특징:

    • 각 단계에서 지역 최적해를 선택하여 문제를 해결한다.
    • 문제에 따라 전체 최적해(Global Optimum)를 보장할 수도, 보장하지 못할 수도 있다.
    • 탐욕 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure) 조건이 만족되어야 한다.

1.2 대표 문제 및 예시​

  • 거스름돈 문제:
    동전의 단위가 서로 배수 관계에 있을 경우, 가장 큰 단위부터 선택하여 최소 동전 수로 거스름돈을 만드는 문제.
    예시: 500원, 100원, 50원, 10원 동전이 있을 때 760원을 거슬러 주기 위해, 500원 1개, 100원 2개, 50원 1개, 10원 1개를 사용하는 방식.

  • 회의실 배정 문제:
    회의 시작과 종료 시간이 주어졌을 때, 회의실을 최대한 효율적으로 배정하기 위해 종료 시간이 가장 빠른 회의를 먼저 선택하는 방식.
    이 경우, 종료 시간이 빠른 회의를 선택하면 이후 선택 가능한 회의의 수가 최대화된다.

1.3 탐욕법의 한계 및 고려사항​

  • 전역 최적해 미보장:
    탐욕법은 각 단계에서 최선의 선택을 하지만, 일부 문제에서는 전체 문제에 대해 최적의 해답을 보장하지 않는다.
    예를 들어, 동전 단위가 일반적이지 않거나, 선택 기준이 명확하지 않은 문제에서는 탐욕법이 실패할 수 있다.

  • 적용 조건:
    탐욕법이 효과적으로 작동하기 위해서는 문제에 탐욕 선택 속성과 최적 부분 구조가 존재해야 한다.
    이러한 조건이 충족되지 않으면, 동적 계획법(Dynamic Programming) 등 다른 기법을 고려해야 한다.

2.1 기본 개념​

  • 정의:
    이분탐색은 정렬된 배열 또는 리스트에서 특정 값이나 조건에 맞는 요소를 효율적으로 찾기 위해 사용하는 알고리즘이다.

  • 시간 복잡도:
    배열을 반씩 나누어 탐색하기 때문에 시간 복잡도는 O(log N)이다.

2.2 구현 방식​

  • 재귀 구현:
    재귀 함수를 이용하여 배열의 중간 값을 기준으로 탐색 범위를 계속해서 줄여 나간다.

    function binarySearch(arr, target, low = 0, high = arr.length - 1) {
      if (low > high) return -1;
      const mid = Math.floor((low + high) / 2);
      if (arr[mid] === target) return mid;
      else if (arr[mid] < target) return binarySearch(arr, target, mid + 1, high);
      else return binarySearch(arr, target, low, mid - 1);
    }

  • 반복 구현:

    function binarySearch(arr, target) {
      let low = 0,
        high = arr.length - 1;
      while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
      }
      return -1;
    }

2.3 Lower Bound와 Upper Bound 개념​

  • Lower Bound:
    배열에서 주어진 값 이상이 처음 나타나는 위치를 찾는 방법.
    예시: [1, 2, 2, 2, 3, 4]에서 2의 Lower Bound는 1(인덱스 1)이다.

  • Upper Bound: 배열에서 주어진 값보다 큰 값이 처음 나타나는 위치를 찾는 방법.
    예시: [1, 2, 2, 2, 3, 4]에서 2의 Upper Bound는 4(인덱스 4)이다.

  1. 종합 정리
  • 탐욕법: 각 단계에서 현재 상황에 최적인 선택을 통해 문제를 해결하지만, 문제의 특성에 따라 전역 최적해를 보장하지 않을 수 있다. 대표 문제로는 거스름돈 문제와 회의실 배정 문제가 있으며, 문제의 조건에 따라 적용 여부를 신중히 판단해야 한다.
  • 이분탐색: 정렬된 배열에서 빠른 탐색을 가능하게 하며, 재귀 혹은 반복 방식으로 구현할 수 있다. lower bound와 upper bound 개념을 통해 범위 검색 등 다양한 응용이 가능하다.