[C/C++] 이분탐색으로 LIS 구하는 방법

[C/C++] 이분탐색으로 LIS 구하는 방법

혼자서 이분탐색으로 LIS를 구하는 알고리즘을 구현하다가 막혀서 검색을 하게 되었다.

LIS를 이분탐색으로 구하는 방법

LIS배열의 마지막 원소와 비교하였을 때,

1. 증가하는 부분 수열일 경우, LIS 배열의 가장 끝에 추가한다.

2. 증가하는 부분 수열이 아닐 경우, LIS배열을 이분 탐색하여 들어갈 위치를 찾아 값을 대체한다.

LIS 배열의 마지막 원소가 있는 인덱스가 가장 긴 부분 증가 수열의 길이가 된다.

이분탐색을 이용한 LIS 코드 구현 방법

직접 이분탐색을 구현하는 방법과 C++의 라이브러리 lower_bound()를 사용하는 방법이 있다.

1. C로 직접 이분 탐색하여 구현하는 방법

출처 : https://www.crocus.co.kr/583

int _lower_bound(int start, int end, int *arr, int target)
{
    int mid;
    while (end - start > 0)  // 주어진 범위[start,end]에서 탐색하도록 한다. start == end이면 반복 종료
    {
        mid = (start + end) / 2;  // 주어진 범위의 중간 위치를 계산한다
 
        if (arr[mid] < target) // 찾고자 하는 값보다 작으면 오른쪽으로 한 칸만 더 시작 구간 갱신
            start = mid + 1;
 
        else  // 찾고자 하는 값보다 크면 거기까지 끝 구간 갱신
            end = mid;
    }
    return end + 1; // 찾는 구간에 없는 경우 가장 마지막 +1 위치 전달
}
int main()
{
    int i, n, j = 0;
    int cnt = 0;
    int lis[1001];
    int arr[1001];
    
    scanf("%d", &n);
 
    for (i = 0; i<n; ++i)
        scanf("%d", &arr[i]);
    
    i = 0;
    lis[i] = arr[i];
    i++;
 
    while (i < n){
        // lis의 가장 큰 값보다 더 큰값이 들어오면
        if (lis[j] < arr[i]){
            lis[j + 1] = arr[i];
            j++;
        }
        else{
            int ans = _lower_bound(0, j, lis, arr[i]);
            lis[ans - 1] = arr[i];
        }
        i++;
    }
    printf("%d", j + 1);
 
    return 0;
}

2. C++의 lower_bound()를 이용한 방법

출처 : https://jason9319.tistory.com/113

vt.push_back(-INF);
for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    if (vt.back() < x) {
        vt.push_back(x);
           ans++;
    }
    else {
        auto it = lower_bound(vt.begin(), vt.end(), x);
        *it = x;
    }
}

STL algorithm 에 있는 lower_bound 함수는 벡터를 이분탐색하며 주어진 값이 들어가야 할 낮은 위치의 iterator를 반환한다.

아래 예시를 보면 명확히 알 수 있다.

출처 : http://www.cplusplus.com/reference/algorithm/lower_bound/

Example

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// lower_bound/upper_bound example #include <iostream> // std::cout #include <algorithm> // std::lower_bound, std::upper_bound, std::sort #include <vector> // std::vector int main () { int myints[] = {10,20,30,30,20,10,10,20}; std::vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20 std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30 std::vector<int>::iterator low,up; low=std::lower_bound (v.begin(), v.end(), 20); // ^ up= std::upper_bound (v.begin(), v.end(), 20); // ^ std::cout << "lower_bound at position " << (low- v.begin()) << '\n'; std::cout << "upper_bound at position " << (up - v.begin()) << '\n'; return 0; }

Edit & Run

Output:

lower_bound at position 3 upper_bound at position 6