개념

1. Binary Search와 유사한 알고리즘
2. 최적화 문제를 결정 문제로 풀 수 있는 기술

최적화 문제는 어떤 알고리즘의 최적의 솔루션(예를 들어, 출구가 있는 미로에서 시작점에서 출구까지의 최단 경로 길이 구하는 문제)을 찾아내는 것이다. 결정 문제는 True or False 형태의 답만 나오는 문제(정해진 영역 내에 특정 수가 존재하는지 유무를 구하는 문제)이다.

이진 탐색과 유사한 점

Binary Search는 정렬된 값들이 주어졌을 때 그 값들 중 원하는 값을 찾는 알고리즘이고 Parametric Search는 주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘이다.

예를 들어, 1부터 20까지 정렬된 배열에서 5라는 값을 찾을 때는 Binary Search을 사용한다.

만약 2부터 20까지 원소가 들어있는 배열에서 5보다 큰 원소(조건) 인 값 중 가장 최소값을 찾아내는 문제는 Parametric Search 알고리즘을 사용해야 한다.

문제 적용 유형

1. 결정 문제
2. 어떤 시점에서 조건 만족하지만, 후로는 만족하지 않을 경우 조건을 만족하는 최대값 찾기

3. 어떤 시점에서 조건이 만족하지 않지만, 후로는 만족할 경우 조건을 만족하는 최소값 찾기

2번과 3번 유형의 핵심은 같기 때문에 편의상, 2번 유형을 기준으로 풀어보자.

예제문제

예제 문제 풀이

위의 문제는 나무 자르기 문제이다. 간략히 정리하면, 주어진 배열의 원소값들을 각각 특정 길이로 뺀 나머지(a)의 합이 원하는 값(b)보다 높을 때의 조건에서 성립되는 a값 들 중 가장 작은 값을 구하는 문제이다.

만약 전체 나무들의 길이 배열이 [20, 15, 10, 17]일 경우 b가 7일 경우 아래와 같이 정리할 수 있다.

간단하게 a가 1일 때는 (20-1) + (15-1) + (10-1) + (17-1) > 7 임으로 조건이 만족한다. 하지만, a가 16일 때 (20-16) + (15 - 16) + (10 -16) + (17 - 16) == 5가 된다. 왜냐하면, 나무의 크기보다 자르려는 길이가 클 경우 나머지가 없기 때문이다. 그럼으로 a가 16일 때 조건이 불만족한다.

위의 조건에서 주어진 조건을 성립하는 최대값을 구해야 하기 때문에, 이를 이진 탐색에 적용시 조건이 성립될 때 START를 mid + 1로 두어야 한다. 그리고 조건이 성립되지 않을 경우 END를 mid - 1로 두어야 한다.

즉, 이를 쉽게 풀어내자면 어떤 위치에서 주어진 조건이 성립될 때 그 위치의 앞쪽은 무조건 조건이 만족될 것이기 때문에 쓸데없는 부분을 넘긴다(우리가 원하는건 별이 있는 위치). 조건이 성립되지 않을 경우 그 위치의 뒤쪽은 무조건 조건 불만족이 될것이기에 end를 수정하여 쓸데없는 부분을 넘긴다.

아래는 위의 방법을 통해 진행되는 결과이다.

예제 코드

import sys


def slicingTree(parm):
    sliced = 0
    for tree in trees:
        if parm < tree:
            sliced += tree - parm
    return sliced


def paramSearch(start, end, target):
    while start <= end:
        mid = (start + end) // 2
        print(start,end,mid)
        if slicingTree(mid) >= target:
            start = mid + 1
        else:
            end = mid - 1
    print(end)


def solution():
    global trees
    input = sys.stdin.readline
    n, m = map(int, input().split())
    trees = list(map(int, input().split()))
    paramSearch(0, max(trees), m)


solution()