정의

주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것

• 배열 안의 특정 범위를 좁혀가는 목적으로 사용
• 최대 최소값과 같은 최적해를 구하는 문제에서 유용하게 쓰임
• 시간 복잡도 : O(logN)

조건

파라메트릭 탐색은 모든 문제에 적용할 수 없고, 아래의 세 조건을 만족해야 함

• 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제
• 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면
  그 값보다 작은 값은 모두 조건을 만족 (반대로, 최솟값의 경우 그 보다 큰 값은 모두 조건 만족해야 할 것)
• 답의 범위가 이산적(정수)이거나 허용 오차 범위가 있어야 함

구현

구하고자 하는 값의 범위를 start와 end로 크게 두고,
조건문을 이용하여 해당 문제의 유효한 범위인지를 파악하고,
조건이 만족되면 start와 end를 점점 좁혀가는 방식으로 구현

---

문제

연료 탱크의 상태를 문자열로 입력받고, 연료량을 %로 표현하는 문제

입력

######____

출력

60%

제한조건

입력되는 문자열의 길이는 항상 10개로 고정되어 있음

풀이

fuel = input()          # 연료량을 입력받음
start, end = 0, 9
Max = 0                 # 최대값을 넣을 변수 생성
while start <= end:
    mid = (start+end)//2
    if fuel[mid]=='#':
        start = mid + 1
        Max = mid       # 최댓값 갱신
    else:
        end = mid - 1
print(f'{(Max+1)*10}%')

fuel의 갯수는 10으로 고정되어 있으므로 위와 같이 초기 범위를 0 ~ 9로 두고, mid를 중간값으로 설정한다.

while문 내의 조건문을 통해 fuel[mid]가 #인 경우, start를 mid+1로, 최댓값을 mid로 갱신하고, 그렇지 않은 경우 end를 mid-1로 조정하였다.

위 작업을 start와 end가 같아질 때까지 계속 반복하게 되면, 최댓값이 결정되게 된다.

하지만 위 문제에서 fuel가 하나도 없는 경우 즉, __________ 인 경우, 10%라고 표시되는 버그가 발생한다.

이 경우 초기 Max값을 -1로 설정해주면, 위와 같은 버그는 해결된다.

최종 답안

fuel = input()          # 연료량을 입력받음
start, end = 0, 9
Max = -1                 # 최대값을 넣을 변수를 -1로 초기화
while start <= end:
    mid = (start+end)//2
    if fuel[mid]=='#':
        start = mid + 1
        Max = mid       # 최댓값 갱신
    else:
        end = mid - 1
print(f'{(Max+1)*10}%')