[알고리즘] 탐색 (순차, 이진), 매개변수 탐색(Parametric Search)

탐색 알고리즘

 

주어진 input에서 원하는 data를 찾기 위한 알고리즘.

 

1. Sequential search

 

 리스트에서 저장된 데이터를 차례로 검사한다. 무작위로 저장된 리스트를 탐색할 수 있지만, 최악의 경우(리스트에 찾으려는 데이터가 존재하지 않거나, 리스트의 마지막에 데이터가 존재하는 경우) n개의 input size를 갖는 리스트를 탐색할때 O(n)의 시간복잡도를 가진다.

public int seqSearch(int[] arr, int target) {

        for(int i=0; i<arr.length; i++) {
            if(arr[i]==target)
                return arr[i];
        }
        return -1;
}

 

2. Binary Search

 

 정렬된 리스트의 데이터를 탐색할 수 있다. 매 탐색시마다 찾으려는 데이터의 대소를 비교하여 반으로 나누어 검사하므로, 최악의 경우에도 O(lgn)의 시간복잡도를 갖는다. 

public int binarySearch(int[] arr, int left, int right, int target) {

        if(left<=right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) return mid;
            else if (target < arr[mid])
                return binarySearch(arr, left, mid - 1, target); //mid는 더이상 탐색대상이 아님
            else if (target > arr[mid])
                return binarySearch(arr, mid + 1, right, target); //mid는 더이상 탐색대상이 아님
        }
        return -1;
}

+ 재귀함수꼴에 대한 생각

        if(left<=right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) return mid;
            else if (target < arr[mid])
                binarySearch(arr, left, mid - 1, target); //mid는 더이상 탐색대상이 아님
            else if (target > arr[mid])
                binarySearch(arr, mid + 1, right, target); //mid는 더이상 탐색대상이 아님
        }

재귀함수 호출 후 리턴하지 않고 위와 같이 코드를 짜도 처음 target==arr[mid]조건에 걸려서 mid 인덱스를 리턴하지 않을까라는 생각을 예전에 잠시 한적이 있음.. 결론은 당연히 재귀가 끝나는 마지막 함수에서만 값이 리턴되고 그다음부터는 리턴되지 않고 조건문을 빠져나와서 -1이 빠져나오게 될것이다.

 

+ 경계 설정에 관한 생각

가장 간단한 탐색 알고리즘 중에 하나가 이진탐색이라고들 한다. 그런데 경계를 잘못 설정하게 되면 while을 빠져나오지 못하게 되거나, 제대로 탐색하지 못하는 문제가 생긴다. 호출시 경계값에는 어떻게 수를 넣을지, left와 right, mid와 같은 경계에 +1, -1을 할지, 또 어떤 경계값을 리턴해주어야 할지, 부등호에 =를 붙여주어야 할지 등 생각할것이 많다.

private static int binarySearch(int target, int l, int r) {
    int mid;
    while(l<r) {
        mid = (l+r)/2;
        if(arr[mid]>target)
            r = mid+1;
        else
            l = mid;
    }
    return r;
}

백준 12015번 - 가장 긴 증가하는 부분 수열 2 제출 코드의 일부이다. lis배열에서 N의 범위가 커서 이진탐색을 이용하여 해결하기 위해서, arr이라는 static 배열에서 target을 찾기 위한 이진탐색 코드이다. 하지만 이대로 답을 제출하면 while문을 빠져나오지 못하고 무한루프를 도는 것(=범위가 줄어들지 않는 것)을 볼 수 있다. 

 

 

전제 1. 위에서 작성했던 코드처럼 target이 arr내에 존재한다는 가정하에 찾아나가면, 이와 같이 존재하지 않을 경우 적절한 위치를 찾는 코드는 무한루프를 돌 수 밖에 없다. 그래서 while문을 사용해서 코드를 작성했다.

 

전제 2. l과 r의 의미는 [l,r)의 의미이다. 즉, idx l보다는 크거나 같고, idx r보다는 작거나 같다라는 것이다. 또한 arr이 N의 크기를 가지면(idx 0~ idx N-1), binarySearch(target, 0, N-1)과 같이 호출될 것이다.

 

1. (l+r)/2의 결과가 정수가 아닐 경우 소수점 내림처리가 된다. 경우에 따라 l+1==r이 될 경우 mid=(l+r)/2를 해도 mid의 값이 바뀌지 않을 수 있다. 그렇기 때문에 위와 같이 l = mid를 사용하게 되면 값이 갱신되지 않아 문제가 발생할 수 있다.

 

2. 단, while 조건문에서 등호가 포함되어 있을 경우 l = mid+1, r = mid를 사용하게 되면 l+1==r이 될 경우 역시 무한루프를 돌 수 있다. 따라서 이러한 경우 r = mid-1을 사용한다.

 

3. 이왕이면 템플릿으로 만들어서 기억하자. while조건에는 등호가 들어가지 않은 l<r을 사용하고, l=mid+1, r=mid를 사용한 뒤 r을 리턴해주면 된다.

 

4. target의 존재 여부를 확인해야 한다면 맨 위 코드처럼 깔끔하게 재귀로 mid-1, mid+1과 같이 나눠버리자

 

 

 

 

3. Parametric Search (매개변수 탐색 알고리즘)

 

 매개변수 탐색 알고리즘은 최적화 문제를 결정문제로 바꾸어 푸는 기법이다. 간단하게 말하면 조건을 만족하는 범위 내의 수 중 가장 최소/최고값이 존재한다면 범위 내에서 만족하는 수를 하나씩 찾아가면서 답을 결정하는 방법이다.

 

최적화 문제: 알고리즘의 최적의 풀이 방법을 찾음
결정 문제: 답을 결정해놓고 문제를 푸는 것.

 

이러한 매개변수 탐색 알고리즘을 사용하면, 어떤 시점을 기준으로 조건을 만족할 때 그 최대값을 찾을 수 있다. 매개변수 탐색도 이진 탐색을 사용하는데, 일반적인 이진 탐색의 경우 이분 과정을 통해서 target과 일치하는 값을 찾을 때까지 알고리즘을 진행하지만, 매개변수 탐색은 한계(bound)에 가장 가까운 값을 target으로 두고 그것의 최적값을 갱신해가며 알고리즘을 진행한다.

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

해당 문제를 보면, 필요한 나무(M)보다 많은 나무를 얻을 수 있는 boundary값에 가까운 target을 구해야 한다. 그렇기에 문제를 풀기 위한 코드도 이진탐색과는 약간의 차이를 가진다.

 

 

 

보면 범위를 반씩 잘라가면서 탐색하는 것은 기존의 이진탐색과 동일한데, 기존에 이진 탐색에서 존재했던 if(amount==M)과 같은, 정확한 값을 찾으려는 목표보다 amount<=M이라는 'M과 같은 값이 나오는 mid값이 있으면 좋지만, 아니면 최대한 M에 가까운 mid값을 찾겠다'라는 목표를 가지는 것이 보인다.

 

 

이 문제 역시 이진탐색과 동일하게 범위잡는게 많이 헷갈리는데, while()안에 들어가는 조건과, low와 high값을 어떻게 설정할 지, 마지막으로 어떤 값을 출력할지 많이 헷갈린다. 

이 문제에서는 low는 최종적으로 M에 최대한 가까운 값이 되도록 의도하였고, high는 불가능한 값(최대값+1)이 들어가도록 했다. low<high-1으로 조건을 설정한 이유는 high-1이 가능한 최대값인데, 그것보다는 작도록 설정한 것이다. 그 후 while문을 통해서 low를 bound에 가장 가까운 작은 값으로 설정해주면 된다.

 

 

 

반복문의 템플릿화

 

while(left<=right) { //left==right일때 까지
    mid = (left+right)/2; //새로운 범위 설정을 위한 중간값 계산
    if(...) { // 정답이 포함된 범위 (매개변수 탐색)
        left = mid+1;
        ans = Math.m??(ans, mid); //정답이 포함된 범위 내 최적값 찾기
    } else { // 정답을 제외한 범위
        right = mid-1;
    }
}

 

모든 문제에서 설정을 바꿔가면서 적용하는건 시간도 잡아먹고 실수할 가능성이 많다. 위 템플릿대로 적용하고 조건문을 조절하는 식으로 푸는게 코테라는 목적에 잘 맞을거같음.

 

참고

: https://www.acmicpc.net/blog/view/109

https://blossoming-man.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%EA%B2%BD%EA%B3%84-%EC%84%A4%EC%A0%95%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC-%ED%95%98%EB%8A%94%EA%B0%80