[이진탐색] 떡볶이 떡 만들기

알고리즘 스터디

이번엔 이진탐색 챕터를 공부하기로 했다.
4명 중 2명씩 나누어 2번 3번 실전 문제를 풀기로 했다.
나는 3번 문제에 당첨되어 파라메트릭 서치에 대해 배우게 됐다!

---

이진탐색에 대한 간략한 소개

이진탐색이란 이미 정렬되어있는 데이터 안에서 특정 값을 찾아내기 위해 반으로 나눠가며 찾는 탐색 알고리즘이다.

나는 CS50강의에서 전화번호부 찾기에 빗대어 설명하는 것을 들었다.
인덱스만으로 찾고자 하는 값에 금방 접근할 수 있으며,
찾고자 하는 값과 인덱스를 비교하여 앞으로 탐색할지,
뒤로 탐색할지 선택하고 반복하는 것 만으로 정보를 얻을 수 있기 때문이다.

(물론 이진탐색은 기본적으로 중간값을 기준으로 탐색해나가기 때문에 완벽하게 전화번호부 찾기 알고리즘이라고 단정지을 수는 없다.)

이진탐색의 원리

기본 원리는 입력된 정보의 반을 나누어 각각의 절반의 값에 더 근접한 쪽을 찾는 것이다. 즉 시작과 중간과 끝을 계속 바꿔가며 범위를 좁혀나간다.

이진탐색의 구현

1. 배열의 중간 값을 찾는다
2. 찾고자 하는 타겟과 일치한다면 즉시 종료
   2-1. 타겟보다 작다면 중간 값을 끝으로 설정하여 다시 탐색
   2-2. 타겟보다 크다면 중간 값을 시작으로 설정하여 다시 탐색
3. 위 과정을 반복한다

---

파라메트릭 서치에 대한 간략한 소개

이진탐색 중 중 파라메트릭 서치 알고리즘은 최적화 문제를 결정 문제로 바꾸어 해결하는 과정이다. 즉, 많은 데이터를 가지고 최적화가 필요한 문제라면 이 방법을 고려해야한다.

파라메트릭 서치의 원리

1. 구하고자 하는 값을 얻을 때 시도해야하는 방법 정하기
2. 그 값을 변경해가며 최적해인지 확인하기

🌀 뭐라는거야

이건 문제를 보면서 설명하는게 좋을 것 같다.

---

[문제] 떡볶이 떡 만들기

동빈이네 떡볶이 떡은 길이가 일정하지 않다.
대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
손님이 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1000000, 1 <= M <= 2000000000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력조건

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

입력 예시
4 6

출력 예시
19 15 10 17

🌀 풀이

파라메트릭 서치의 원리를 들어 예를 설명해보자면

1. 구하고자 하는 값 : 6cm
2. 떡의 개수 : 4개
3. 시도해야하는 방법 : 절단기 높이 바꾸기

그럼 이걸 가지고 뭘 해야하나?

1. 절단기 높이를 계속 바꿔가며 떡을 자른다.
2. 잘라진 떡의 길이가 6cm인지 확인한다.
   2-1. 6cm보다 크다면? 절단기의 높이를 더 높게 설정
   2-2. 6cm보다 작다면? 절단기의 높이를 더 낮게 설정
3. 위 과정을 반복한다.

이진탐색을 요약한 과정과 유사하다.

코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, target) = (input[0], input[1]) // 떡 개수 : n, 요청한 길이 : m
let array = readLine()!.split(separator: " ").map { Int(String($0))! }

print(parametricSearch(array, target))

func parametricSearch(_ array: [Int], _ target: Int) -> Int {
    var result = 0
    var start = 0
    var end = array.max()!
    
    while start <= end {
        var total = 0
        let mid = (start + end) / 2
        
        for ddeok in array {
            if ddeok > mid { // 떡이 지금 자를 높이보다 크다면
                total += ddeok - mid // 잘라진 떡을 누적한다
            }
        }
        if total < target {     // 누적된 떡의 양이 부족하다면
            end = mid - 1       // 높이를 더 낮게 설정한다 (떡이 더 많이 잘리도록)
        } else {                // 누적된 떡의 양이 충분하다면
            result = mid        // 결과를 초기화하고 (최적해)
            start = mid + 1     // 높이를 더 높게 설정한다 (떡이 덜 잘리도록)
        }
    }
    return result
}