- 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 여기서 결정 문제란 "에" 또는 "아니오"로 답하는 문제를 말하며, 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제를 말한다.
- 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색을 이용하여 구현합니다.
- 예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐색을 통해 적합한 해의 범위를 절반씩 좁혀 나갈 수 있습니다.
- 파라메트릭 서치또한 이진 탐색 처럼 입력 데이터가 많거나, 범위의 크기가 매우 넓을 때 효율적으로 문제를 해결할 수 있다.
- 파라메트릭 서치와 이진 탐색의 차이점은 결정 문제이냐 아니냐로 차이를 나눌 수 있습니다.
- 파라메트릭 서치는 특정한 조건을 만족하는 해를 찾을 때 결정 문제를 해결해 나갑니다.
- 즉, 특정 조건을 만족하느냐 혹은 만족하지 못하느냐에 따라 해의 범위를 좁혀 나가는 방법입니다.
- 이진 탐색은 시간, 중간, 끝 인덱스를 활용하며 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(logN) 입니다.
- 마찬가지로 파라메트릭 서치 역시 O(logN) 의 시간 복잡도를 갖습니다.
- 길이가 다른 K개의 랜선을 N개의 같은 길이의 랜선으로 만들어야 합니다. 만들 수 있는 최대 길이를 구하시오.
import Foundation
let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let n = line[0]
let k = line[1]
var array:[Int] = []
for i in 1...n {
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,k)!)
- 우선, 이진 탐색을 수행하기 위해 배열의 시작 인덱스를
left로, 끝 인덱스를 right로 설정합니다. 이진 탐색은 각 단계마다 탐색 범위를 반으로 줄여가면서 찾고자 하는 값을 찾아내는 알고리즘인데, 이를 위해서는 주어진 배열이 정렬되어 있어야 합니다. 따라서, 주어진 배열을 오름차순으로 정렬합니다.
- 그리고, 이진 탐색을 수행하면서, 중간 값인
mid를 구합니다. 이 때, mid는 탐색 범위의 중간에 위치한 값으로, 배열의 길이가 홀수일 때는 가운데 값, 짝수일 때는 가운데 두 값 중 작은 값을 선택합니다.
- 그리고
mid 값을 기준으로 배열을 두 부분으로 나누어서, 왼쪽 부분에는 mid보다 작은 값들만, 오른쪽 부분에는 mid보다 큰 값들만 남도록 분할합니다. 이 때, 배열이 오름차순으로 정렬되어 있으므로, 왼쪽 부분의 최대 값은 mid보다 작고, 오른쪽 부분의 최소 값은 mid보다 크게 됩니다.
- 그리고, 이 중에서 더 작은 값을 다음 단계의 탐색 범위로 설정합니다. 예를 들어,
arr[mid]가 왼쪽 부분의 최대 값보다 작은 경우에는, 왼쪽 부분에서 최소값을 찾아야 하므로 right 값을 mid - 1로 설정합니다. 반대로, arr[mid]가 오른쪽 부분의 최소 값보다 큰 경우에는, 오른쪽 부분에서 최소값을 찾아야 하므로 left 값을 mid + 1로 설정합니다. 만약 arr[mid]가 왼쪽 부분의 최대 값이거나 오른쪽 부분의 최소 값과 같은 경우에는, 이 값이 배열의 최소값이므로 mid 값을 반환합니다.
- 위와 같은 과정을 반복하면서, 배열의 최소값을 찾아낼 수 있습니다.
- 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
- #Algorithm/BinarySearch/ParametricSearch