Skip to main content
동호의 블로그

파라매트릭 서치 알고리즘 [개념]

•1 min•145 words

https://gliver.tistory.com/31

1. 파라매트릭 서치 알고리즘

  • 파라매트릭 서치 알고리즘은 이분 탐색을 이용하여 답을 구하는 알고리즘이다.
    • 최대값, 최소값을 구하는 문제를 결정 문제로 바꾸어 푸는 알고리즘이다.
  • 문제에서 파라매트릭 서치 알고리즘을 사용할 수 있는 경우

    • 결정 문제로 바꾸었을 때, O/X의 형태가 연속적으로 나타나야 한다.

      image.png

2. 파라매트릭 서치 구현

  • 방법1

    def parametric_search(arr):
    ret = -1

    left = 0
    right = len(arr) - 1

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

        if arr[mid] == True: 
            left = mid + 1
            ret = mid
        else: 
            right = mid - 1

    return ret


arr = [True, True, True, True, True, True, True, True, False, False, False, False]
print(parametric_search(arr))

  • 방법2

    def parametric_search(arr):
    cur = -1
    step = len(arr)
    
    while step != 0:
        while (cur + step < len(arr) and arr[cur + step] == True): 
            cur += step
        step //= 2
        
    return cur

arr = [True, True, True, True, True, True, True, True, False, False, False, False]
print(parametric_search(arr))

3. 파라매트릭 서치 문제 예제

Untitled

4. 실제 문제에서 파라매트릭 서치 알고리즘

  • 파라매트릭 서치의 특징
    • 파라매트릭 서치는 문제에서 배열이 주어지는 것이 아닌, 상황 자체를 일종의 정렬된 배열처럼 보는 것이다.
    • 따라서, 파라매트릭 서치는 보통 최대값 또는 최소값을 구하는 문제에서 많이 쓰인다.
  • 자주 쓰이는 파라매트릭 서치 유형
    • k인 경우에 답이 가능한가? - 최소값, 최대값을 구하는 문제
      • [False, False, False, False, True, True, True]
      • [True, True, True, True, False, False, False]
    • k 이하인 경우에 답이 가능한가? - 최소값을 구하는 문제
      • [False, False, False, False, True, True, True]
    • k 이상인 경우에 답이 가능한가? - 최대값을 구하는 문제
      • [True, True, True, True, False, False, False]
  • k 일 때의 개수 - 인덱스(몇 번째 인지)를 구하는 문제
    • [3, 5, 5, 7, 7, 8, 9, 10, 10, 11, 13, 14, 15, 19, 19]