[BOJ] 11053 - 가장 긴 증가하는 부분 수열 (LIS; C++)

1. 문제

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

11053번: 가장 긴 증가하는 부분 수열

길이가 n일 수열이 주어질 때, 이 수열에서 가장 긴 증가하는 부분 수열의 길이(연속일 필요는 없지만 증가해야 함)를 구하면 되는 문제이다.

2. 풀이 방법

LIS 문제의 해결법은 이 블로그에 잘 나와 있다.

https://seungkwan.tistory.com/8

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

조금만 설명을 하자면,

기존의 DP 방법으로 풀이를 하면, 각 나오는 숫자마다 이전의 모든 증가수열에 들어가는지 여부를 확인해야 해서 O(N^2)이 걸린다.

LIS는 이진 탐색을 이용해 이 확인 과정을 O(n)에서 O(logn)으로 줄여 총 O(nlogn)만에 문제를 해결할 수 있게 했다.

 

먼저 새로운 배열 L을 만든다.

이 L에는 원소들이 정렬되어 있어 이진 탐색이 가능하다.

L의 각 자리에는 해당 길이를 가지는 증가 수열의 마지막 원소(해당 수열에서 가장 큰 수) 중 가장 작은 원소가 저장된다.

 

그리고 lower bound라는 개념이 새로 나오는데, lower bound란 배열에서 자기 자신보다 큰 최소 숫자를 말한다.

LIS를 찾는 알고리즘에서는 이진 탐색을 통해 lower bound를 찾는다.

 

1. 처음에 L에 배열의 첫 원소를 넣는다.

2. 반복문을 돌면서 L의 맨 마지막 요소와 arr[i]를 비교한다. 만약 arr[i]가L의 마지막 요소보다 크다면, 이는 이제까지 나온 가장 긴 증가수열의 가장 큰 요소보다 arr[i]가 더 크다는 뜻이므로, arr[i]를 LIS의 맨 뒤에 추가하면 LIS의 길이를 하나 더 늘릴 수 있다는 뜻이다.

따라서 L의 마지막에 arr[i]를 추가한다.

3. 만약 L의 마지막 원소 > arr[i]라면 L의 원소중 arr[i]의 lower bound(L[j]라고 하자)를 찾고, 이를 arr[i]로 교체한다. 이를 찾는 이유는 L에서 arr[i]의 lower bound 이전의 수(L[j - 1])는 arr[i]를 마지막으로 가지는 증가 수열이다. 그런데 여기에 arr[i]를 추가해 길이가 j가 된다면, j의 길이를 가지는 증가수열의 마지막 수 중 가장 작은 수는 arr[i]가 되기 때문이다.

 

이를 반복해 주면 결국 L의 길이가 수열에서 LIS의 길이가 된다.

3. 배운 점

탐색 -> 이진탐색 주로 사용

이진 탐색하려면 -> 정렬 내지 정렬된 배열 필요 (정렬을 할 필요가 없을 수도 있다는 뜻)

4. 코드