[3745번] 오름세(LIS Algorithm, Lower_Bound)

문제 출처 :

 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 부분 수열 및 부분 증가 수열 이해

2. LIS 알고리즘 ( Longest Increasing Subsequence )

3. 이진 탐색 응용 (Applied Binary Search)

일단 이 문제를 해결하기 위해 부분 증가 수열을 이해 해야한다.

3 1 9 7 4 6 8 5 2 이라는 수를 보자.

연속된 수열중 가장 긴 값은 

:: 4 6 8 이다.

하지만 부분 증가 수열 중 가장 긴 값은

:: 1 4 6 8 이다.

다른 예제를 본다면

1 5 2 5 3 5 4 5 라면

연속된 수열 중 가장 긴 값은

:: 1 5 혹은 2 5 혹은 .. 혹은 4 5 이다.

 

부분 증가 수열 중 가장 긴 값은

:: 1 2 3 4 5 이다.

즉, 차례대로 수를 볼 때 연속되지 않아도 증가한다면 계속 추가 해주는 방식이다.

이것이 이번 문제 해결에 가장 처음이 되고 중요한 내용이고

그다음 이것을 어떻게 표현할까에 대해 생각해본다.

LIS 알고리즘이라는 것이 존재한다.

이 알고리즘의 원칙은 다음과 같다.

1. lis 배열에 아무 값이 없다면 조사 하는 배열(arr)의 첫번째 값을 넣는다.

2. lis 배열의 가장 큰 값(가장 오른쪽에 있는 값) 보다 현재 보고 있는 arr[i] 값이 크다면 lis배열에 arr[i]값을 추가한다.

3. 그 외에는 lower_bound(주어진 집합의 어떤 원소보다 작거나 같은 원소라는 뜻)을 이용하여 그 위치에 값을 넣어준다.

이 게시물에서는 LIS, lower_bound라는 것이 존재한다는 것을 말하고, 다음 게시물에서 하나씩 자세히 설명할 것이다.

이 코드에서는 lower_bound를 C++에 내포된 알고리즘을 이용하지 않고, 직접 구현하여 해결하였다.

소스 코드 : 

#include <stdio.h>
 
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 arr[100001];
    int lis[100001];
    int n, i, j, cnt;
    
    while (scanf("%d", &n) != EOF)
    {
        // 초기화
        for (i = 1; i <= n; i++)
            lis[i] = 0;
 
        j = 0;
        i = 0;
        cnt = 0;
 
        // 값입력
        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++;
        }
 
        for (int t = 0; lis[t] != NULL; t++)
            cnt++;
 
        printf("%d\n", cnt);
    }
 
    return 0;
}
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>