[알고리즘] 파라메트릭 서치(Parametric search)

💡파라메트릭 서치(Parametric search)란?

Parametric search는 이분(이진) 탐색과 매우 유사하다. Parametric search란 쉽게 말해서, 최적화 문제를 결정 문제로 변형하여 이분(이진) 탐색을 통해 해결하는 것을 말한다.

• Parametric search 적용 조건
  • 최적화된 값을 요구하는 문제
  • 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제
  • 조건을 만족하는 최댓값을 구했을 경우 그 값보다 작은 값은 모두 조건을 민족해야 한다.

Parametric search 문제

• 커서의 위치 찾기

# 워드작업 중 정전으로 인하여 컴퓨터가 강제로 종료가 되었습니다.
# 다시 전기가 들어어 컴퓨터를 켰더니 다행이도 자동복구가 실행 되었습니다.
# 우리는 자동복구가 되었을때 커서의 위치가 어디인지를 알려줘야 합니다.
# 커서의 위치를 알려주는 프로그래밍을 완성해 주세요.
# 시간복잡도 (On^2)보다 빨라야 합니다.

curser = [ # '#'이 존재하는 최대 위치 찾기
    '##########',
    '##########',
    '##########',
    '##________',
    '__________'
]

def parametric_search(start, end, arr):
    max = 0 
    while (True): # 이진 탐색을 활용
        mid = (start + end) // 2
        if start > end:
            break
        if arr[mid] == '#':
            max = mid
            start = mid + 1

        elif arr[mid] == '_':
            end = mid - 1
    return max   

newls=[s[0] for s in curser]

x_idx=parametric_search(0,len(newls)-1, newls)

y_idx=parametric_search(0,len(curser[x_idx])-1,curser[x_idx])

print(x_idx,y_idx)

• 백준
  • 랜선 자르기
  • 기타 레슨
  • 반도체 설계