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

[11강] 이분 탐색 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 이분 탐색 알고리즘에 대해 알아보겠습니다. 목차 이분 탐색 알고리즘 파라매트릭 서치 알고리즘 실제 문제에서 이분 탐색 알고리즘 1. 이분 탐색 알고리즘 이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다. 정렬된 배열이 아니라면 이분 탐색을 시행할 수 없음. 이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로 예시를 통해서 어떻게 동작하는지 살펴보자. 아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자. 방법1 [1단계] left = 0, right = 11 처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다. mid = (lef..

https://gliver.tistory.com/31

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

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

• 문제에서 파라매트릭 서치 알고리즘을 사용할 수 있는 경우
• 결정 문제로 바꾸었을 때, O/X의 형태가 연속적으로 나타나야 한다.

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. 파라매트릭 서치 문제 예제

BOJ 2805 나무 자르기

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]