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

파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 방법입니다. 주어진 범위 내에서 특정 조건을 만족하는 값의 최대/최소를 찾기 위해 이분 탐색을 활용합니다.

이 기법은 주로 이분 탐색을 변형하여 사용하며, 시간 복잡도를 크게 줄일 수 있는 강력한 방법입니다.

1. 파라메트릭 서치의 핵심 아이디어

1. 최적화 문제란?
   • 어떤 값을 최대화하거나 최소화하는 문제를 의미.
   • 예: "길이 x로 나누었을 때 가능한 가장 큰 값을 찾기", "시간을 최소화하는 경우".
2. 결정 문제로 변환
   • 주어진 조건을 만족하는지 '예/아니오(True/False)'로 판단하는 문제로 바꿉니다.
   • 이 조건을 만족하는 값을 이분 탐색으로 찾아냅니다.
3. 이분 탐색 활용
   • 범위를 좁히며 조건을 만족하는 값의 최대/최소를 찾습니다.
   • 결정 문제를 만족하면 범위를 조정하여 탐색을 계속 진행합니다.

2. 파라메트릭 서치의 기본 구성

1. 탐색 범위 설정

• 탐색할 값의 범위를 설정합니다. (예: 최소값 low, 최대값 high)

2. 조건 함수 정의

• 주어진 값을 만족하는지 판단하는 함수 is_valid(mid)를 정의합니다.
• 예: "길이 mid로 나누어 모두 만족하는가?", "시간 mid 이내에 가능한가?".

3. 이분 탐색 실행

• 조건 함수에 따라 탐색 범위를 줄여가며 답을 찾습니다.

3. 파라메트릭 서치의 일반적인 문제 유형

1. 특정 조건을 만족하는 최대/최소 값 찾기
   • 예: "가능한 가장 긴 랜선 길이", "최대 속도로 도달할 수 있는 거리".
2. 최소 비용/최소 시간 문제
   • 예: "최소 비용으로 특정 작업을 완수하기", "최소 시간 내에 모든 작업 완료".
3. 특정 값을 만족하는 구간 나누기
   • 예: "주어진 배열을 일정한 조건으로 나누었을 때 최대값 최소화".

4. 예제와 풀이

예제 1: 랜선 자르기 문제

문제:

• 길이가 다른 N개의 랜선이 주어지고, 이 랜선으로 K개의 동일한 길이의 랜선을 만들어야 합니다.
• 랜선의 최대 길이를 구하시오.

풀이:

1. 탐색 범위 설정:
   • 랜선의 길이는 최소 1에서 최대 max(랜선의 길이)까지 가능합니다.
2. 조건 함수 정의:
   • is_valid(mid): 길이가 mid인 랜선을 K개 이상 만들 수 있으면 True.
3. 이분 탐색 실행:
   • 탐색 범위를 줄여가며 조건을 만족하는 최대 길이를 찾습니다.

코드 구현

def is_valid(mid, arr, K):
    count = sum(l // mid for l in arr)
    return count >= K

def max_lan_length(arr, K):
    low, high = 1, max(arr)  # 랜선 길이의 최소, 최대 범위
    result = 0

    while low <= high:
        mid = (low + high) // 2
        if is_valid(mid, arr, K):
            result = mid  # 조건 만족 -> 길이를 더 늘려도 되는지 확인
            low = mid + 1
        else:
            high = mid - 1  # 조건 불만족 -> 길이를 줄임

    return result

# 테스트
arr = [802, 743, 457, 539]  # 랜선 길이
K = 11  # 필요한 랜선 개수
print(max_lan_length(arr, K))  # 출력: 200

예제 2: 나무 자르기 문제

문제:

• N개의 나무가 주어지고, M미터 이상의 나무를 가져가기 위해 톱날을 조절해야 합니다.
• 나무를 자를 수 있는 톱날의 최대 높이를 구하시오.

풀이:

1. 탐색 범위 설정:
   • 톱날 높이는 최소 0에서 최대 max(나무 높이)까지 가능합니다.
2. 조건 함수 정의:
   • is_valid(mid): 톱날 높이가 mid일 때, 잘린 나무 길이 합이 M 이상인지 확인.
3. 이분 탐색 실행:
   • 탐색 범위를 줄여가며 조건을 만족하는 최대 톱날 높이를 찾습니다.

코드 구현

def is_valid(mid, trees, M):
    total = sum(max(0, tree - mid) for tree in trees)  # 잘린 나무 길이 합
    return total >= M

def max_saw_height(trees, M):
    low, high = 0, max(trees)
    result = 0

    while low <= high:
        mid = (low + high) // 2
        if is_valid(mid, trees, M):
            result = mid  # 조건 만족 -> 높이를 더 늘려도 되는지 확인
            low = mid + 1
        else:
            high = mid - 1  # 조건 불만족 -> 높이를 줄임

    return result

# 테스트
trees = [20, 15, 10, 17]  # 나무 높이
M = 7  # 필요한 나무 길이
print(max_saw_height(trees, M))  # 출력: 15

5. 복잡도 분석

1. 시간 복잡도:
   • 이분 탐색은 범위를 절반씩 줄이므로 O(log(max_value)).
   • 조건 함수는 배열을 순회하며 계산하므로 O(N).
   • 따라서 전체 복잡도는 O(N × log(max_value)).
2. 공간 복잡도:
   • 조건 함수에서 추가적인 메모리를 사용하지 않으므로 O(1).

6. 정리

1. 파라메트릭 서치의 주요 아이디어:
   • "최적화 문제"를 "결정 문제"로 변환.
   • 조건을 만족하는 값을 이분 탐색으로 탐색.
2. 활용 사례:
   • 최대/최소 값을 찾는 문제.
   • 예: 랜선 자르기, 나무 자르기, 공장 배치, 최소 비용/최소 시간 문제.
3. 구현 단계:
   1. 탐색 범위를 설정.
   2. 조건 함수(is_valid)를 정의.
   3. 이분 탐색을 통해 최적 값을 탐색.