이진 탐색을 공부하며,

1. 재귀를 이용한 이진 탐색

func binarySearch(target: Int, start: inout Int, end: inout Int) -> Int? {

    if start > end {
        return nil
    }
    
    let mid = (start+end)/2
    
    if target == A[mid] {
        return mid
    } else if target > A[mid] {
        start = mid + 1
        return binarySearch(target: target, start: &start, end: &end)
    } else if target < A[mid] {
        end = mid - 1
        return binarySearch(target: target, start: &start, end: &end)
    }
    
    return nil
}

2. 정렬된 데이터에서 사용 가능하다.

이 말은 시간이 가능하다면, 내가 정렬해서 사용해도 된다는 말. Swift 내장 sort를 이용하면 시간복잡도 O(logN)을 보장(퀵+병합정렬)하기 때문에, 이진탐색과 함께 사용한다면 이게 더 효율적일듯!

3. Swift의 firstIndex, lastIndex, contains

위의 함수들은 모든 배열(정렬되지 않은 배열)에서 사용되기 때문에 기본 선형 탐색이다. 이외에도 알게 되면 추가하자. 하지만 배열에 사용되는건 어쩔 수 없이 선형 탐색일 가능성이 크다. 

4. 이진 탐색이 O(logN)이라는 사실은 생각보다 겁나 중요하다.

원하는 값을 찾아내기 위해서 이진 탐색에 익숙해지는건 좋은 일.

5. 파라메트릭 서치

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(true/false)로 바꾸어 푸는 것이다.

현재 파라미터로 조건을 수행하면 만족할 것인가?를 이진탐색으로 확인하면서 답을 찾아나가는 것이다.

 

가장 잘 와닫는 설명,

"예를 들어 당신이 정육점 주인인데, 손님이 고기 200g을 달라고 해서 고기 덩이에서 200g을 잘라내야 한다고 해보자. 첫 번째 방법으로 이를 해결하려면, 고기의 밀도, 지방 비중, 마블링 정도 등을 분석한 뒤 얼마나 잘라야 정확히 200g이 되는지를 계산하여 딱 그만큼 잘라야 한다. 그러나 실제로 이렇게 하기엔 굉장히 어렵다. 따라서 일반적으로는 대략 눈대중으로 어느정도 잘라서 저울에 재본 후, 200g보다 부족하면 조금 더 잘라 넣고 200g을 넘치면 조금 잘라서 때낸 뒤 다시 저울에 재보는 식으로 한다. 즉, 우리는 “고기 200g를 잘라라”라는 문제를 “지금 자른 고기가 200g보다 가벼운가/무거운가”라는 결정문제로 변형을 한 뒤 고기를 조금 추가하거나 덜어내면서 이분탐색을 하는 두 번째 방법으로 문제를 해결한다. 이렇게 원래 주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것을 파라매트릭 서치라고 한다."

 

사용하는 조건에 부합해야 사용할 수 있음,

1) 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제, 혹은 이렇게 변형이 가능한 문제. 위의 문제도 200g 이하의 고기 중 최댓값을 구하여라로 문제를 생각할 수 있다.

2) 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야 한다. 최솟값은 반대다. 그래야 조건을 만족하는 경우 더 큰 값을, 그렇지 않은 경우 더 작은 값을 이분탐색으로 답을 구할 수 있기 때문

3) 답의 범위가 정수와 같이 이산적, 허용 오차 범위가 있어야 한다. 이분탐색은 정답에 한없이 가까워질 수 있지만 정확한 값을 구할 수 없다.

 

아래의 end가 A.count인 이유는 무한 루프에 빠지지 않기 위해서다. 최대값을 구하는 경우 mid는 end쪽에 속해야 한다. (start+end)/2의 경우는 start와 end가 1차이로 붙어있을 때 mid는 mid == start가 되고, (start+end+1)/2의 경우 mid == end가 된다. 만약 전자로 할 경우 조건을 항상 만족해야 하면서 범위에는 변화가 생기지 않아서 무한루프가 된다. 

// 해당하는 조건에 성립하는 값을 처음으로 초과하는 값을 나타낸다.
func upperBound(target: Int) -> Int {
    var start = 0
    var end = A.count
    while start < end {
        let mid = (start+end)/2
        if A[mid] <= target {
            start = mid + 1
        }  else {
            end = mid
        }
    }
    return end
}

// 해당하는 조건에 처음으로 성립하는 값을 나타낸다.
func lowerBound(target: Int) -> Int {
    var start = 0
    var end = A.count
    while start < end {
        let mid = (start+end)/2
        if A[mid] < target {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return end
}

 

4. 백준 랜선문제

1. 조건에 부합하는가?

- 최대값 찾는 문제라서 OK

- 역순(!)이긴 하지만 각 길이에 해당하는 최적의 값이 작은 모든 값도 만족하는, 즉 연결되어있다.

- 정수 조건의 문제

2. 아이디어 (최적의 문제를 결정 문제로!)

- 길이를 탐색하는 거다.

- 각 랜선을 돌면서 해당 길이로 만들 수 있는 랜선이 몇개인지 확인한다. 최대 길이를 찾는 문제 + 해당 길이의 값들은 내림차순이므로 구하고자 하는 갯수와 비교해서 해당 길이의 값이거나 해당 길이의 값보다 더 적은 값인 경우 참으로 인정한다. 

- 참일 경우 계속  result를 mid로 교체. 왜냐하면 우리는 upperBound를 찾는 과정.

3. 굳이 start, end, mid가 인덱스가 아니어도 된다. 길이 자체를 start, end, mid로 놓아라.

4. 무엇을 탐색해야 하는지, 어떤 것을 결정 문제로 할 것인지, 그것을 어떻게 구현할 것인지 고민하는게 필요. 물론 그 전에 파라메트릭 서치로 풀릴 것인지 알아채는게 제일 중요할 것 같다.