[Data Structure / Algorithms] Parametric Search

전성훈·2023년 11월 2일

Algorithms baekjoon datastructure swift

Data Structure-Algorithm

목록 보기

7/35

주제: 이진탐색의 변형 탐색

파라메트릭 서치란

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 여기서 결정 문제란 "예" 또는 "아니오"로 답하는 문제를 말하며, 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제를 말한다.
파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색을 이용하여 구현합니다.
예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐색을 통해 적합한 해의 범위를 절반씩 좁혀 나갈 수 있습니다.

이진 탐색 vs 파라메트릭 서치

파라메트릭 서치또한 이진 탐색 처럼 입력 데이터가 많거나, 범위의 크기가 매우 넓을 때 효율적으로 문제를 해결할 수 있다.
파라메트릭 서치와 이진 탐색의 차이점은 결정 문제이냐 아니냐로 차이를 나눌 수 있습니다.
파라메트릭 서치는 특정한 조건을 만족하는 해를 찾을 때 결정 문제를 해결해 나갑니다.
즉, 특정 조건을 만족하느냐 혹은 만족하지 못하느냐에 따라 해의 범위를 좁혀 나가는 방법입니다.

시간 복잡도

이진 탐색은 시간, 중간, 끝 인덱스를 활용하며 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(logN) 입니다.
마찬가지로 파라메트릭 서치 역시 O(logN) 의 시간 복잡도를 갖습니다.

예제

1. 랜선 자르기 (백준 1654)

길이가 다른 K개의 랜선을 N개의 같은 길이의 랜선으로 만들어야 합니다. 만들 수 있는 최대 길이를 구하시오.

import Foundation

let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let k = line[0]
let n = line[1]

var array:[Int] = []

for i in 1...k { 
    let line2 = Int(readLine()!)!
    array.append(line2)
}


func binarySearch(_ arr: [Int], _ target: Int) -> Int? {
    var start = 1
    var end = arr.max()!

    while start <= end {
        let mid = (start + end) / 2

        let count = arr.reduce(0, { $0 + $1 / mid })
        if count >= target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    return end
}

print(binarySearch(array,n)!)

우선, 이진 탐색을 수행하기 위해 배열의 시작 인덱스를 left로, 끝 인덱스를 right로 설정합니다. 이진 탐색은 각 단계마다 탐색 범위를 반으로 줄여가면서 찾고자 하는 값을 찾아내는 알고리즘인데, 이를 위해서는 주어진 배열이 정렬되어 있어야 합니다. 따라서, 주어진 배열을 오름차순으로 정렬합니다.
그리고, 이진 탐색을 수행하면서, 중간 값인 mid를 구합니다. 이 때, mid는 탐색 범위의 중간에 위치한 값으로, 배열의 길이가 홀수일 때는 가운데 값, 짝수일 때는 가운데 두 값 중 작은 값을 선택합니다.
그리고 mid 값을 기준으로 배열을 두 부분으로 나누어서, 왼쪽 부분에는 mid보다 작은 값들만, 오른쪽 부분에는 mid보다 큰 값들만 남도록 분할합니다. 이 때, 배열이 오름차순으로 정렬되어 있으므로, 왼쪽 부분의 최대 값은 mid보다 작고, 오른쪽 부분의 최소 값은 mid보다 크게 됩니다.
그리고, 이 중에서 더 작은 값을 다음 단계의 탐색 범위로 설정합니다. 예를 들어, arr[mid]가 왼쪽 부분의 최대 값보다 작은 경우에는, 왼쪽 부분에서 최소값을 찾아야 하므로 right 값을 mid - 1로 설정합니다. 반대로, arr[mid]가 오른쪽 부분의 최소 값보다 큰 경우에는, 오른쪽 부분에서 최소값을 찾아야 하므로 left 값을 mid + 1로 설정합니다. 만약 arr[mid]가 왼쪽 부분의 최대 값이거나 오른쪽 부분의 최소 값과 같은 경우에는, 이 값이 배열의 최소값이므로 mid 값을 반환합니다.
위와 같은 과정을 반복하면서, 배열의 최소값을 찾아낼 수 있습니다.

2. 울타리 자르기

N개의 나무 판자를 사용하여 M미터 길이의 울타리를 만들려고 합니다. 나무 판자를 자를 때, 손실되는 나무의 길이를 최소화하면서 울타리를 만들 수 있는 최대 길이를 구하시오.

func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var start = 1
    var end = arr.max()!

    while start <= end {
        let mid = (start + end) / 2
        let sum = arr.filter { $0 >= mid }.reduce(0, { $0 + $1 - mid })
        if sum >= target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }

    return end
}

let n = 7
let m = 20
let woods = [20, 15, 10, 17, 19, 18, 13]
print(binarySearch(woods, m) // Output: 15