최장 증가 부분 수열 - 나무위키
어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
namu.wiki
1. 최장 증가 부분 수열(LIS)
LIS 문제를 처음 봤을 때 만능 문제해결 툴 브루트포스를 떠올렸는데 당연히 죽음뿐.
LIS 문제의 정해는 보통 두 가지다. O(N2)으로 해결할 수 있는 다이나믹 프로그래밍, O(NlogN)으로 해결할 수 있는 이진 탐색이다. 여기서 또 이진 탐색 해법이 있다는 걸 처음 알았을 때는 "대체 이게 뭔소리냐" 싶었는데 잘 살펴보고 직접 구현해보면 그렇게 어려운 개념은 아니다. 하지만 이 문제를 이미 몇 년 전에 처음 접해서 풀었던 적이 있음에도 단계별로 풀기를 하다가 만난 LIS를 기억하지 못해서 이번엔 글로 정리해본다.
2. 다이나믹 프로그래밍을 이용한 풀이(O(N2))
다이나믹 프로그래밍을 이용한 풀이는 다 듣고보면 "사실상 이게 브루트포스 아니냐" 싶기도 하다.
국룰 배열 DP를 선언해놓고 점화식을 세워보자. 배열 A를 두고 LIS를 찾을 때, i번째 항목까지의 LIS를 찾는다고 생각해보자. 딱 두 가지 경우만 존재한다.
- i번째 항목이 마지막으로 오는 LIS
- i번째 항목이 마지막으로 오지 않는 LIS
DP[i]에는 1번에 해당하는 LIS의 길이를 저장하도록 한다. 2번에 해당하는 LIS는 굳이 DP[i]에 저장하지 않더라도 이미 DP[i]보다 앞선 위치에 저장되어 있기 때문이다. 그럼 1번에 해당하는 LIS는 0≤j<i인 j에 대해 A[j] < A[i]인 DP[j]중 가장 큰 값을 찾아 DP[i] = DP[j] + 1로 해주면 된다. 이는 순차적으로 DP[0]부터 DP[i-1]까지 탐색하면 확인할 수 있다.
이 과정을 N번 반복하면서 가장 컸던 DP[i] 값을 저장해두고 출력하면 LIS의 길이를 얻을 수 있다.
만약 LIS의 길이가 아니라 수열 자체를 얻고자 한다면, 인덱스를 저장할 배열 I를 선언하고 DP[i] 값이 DP[j] + 1로 최신화 될 때 I[i] = j로 최신화 해주면 모든 A[i]에 대해 어떤 A[j]로 연결되어야 LIS가 구성되는지 알 수 있다. 동시에 가장 큰 DP[i]값을 확인할 때 I[i] 도 함께 저장해두면 A[I[i]] → A[I[I[i]]] → ... 와 같은 식으로 추적해나가며 LIS도 얻을 수 있다.
3. 이진탐색을 이용한 풀이(O(NlogN))
"LIS에 이진탐색을 적용해보라"고 하면 설명서 잃어버린 부품 3만개 짜리 레고를 보는 기분이다. 뭘 어디다 끼워야 할지 감이 안온다. 우선 적용되는 부분을 말하자면 이 방법에서는 LIS를 완전한 형태로 관리하지 않고 "겹쳐진 형태"로 관리한다고 볼 수 있다. 그러니까 만약 어떤 A[i]값을 확인했을 때, 이전보다 짧은 LIS를 구성할 수 있게 된다면 이전에 있던 LIS의 중간 부분을 덮어씌워버리는 식이다. 이때 덮어씌울 부분을 찾을 때 이진탐색을 적용한다.
이 방법에서는 새로운 배열 B를 선언해놓고 시작한다. 역시 순차적으로 A[i]를 확인해 나가는데 배열 B에서 A[i]의 값을 이진탐색으로 찾는다. 탐색 결과로 얻은 위치에 A[i] 값을 덮어 씌운다. 여기서 까다로운 점은 배열 B에 A[i]가 존재하지 않는 경우다. 두 가지 경우가 있다.
- 배열 B의 내부에 A[i]를 끼워 넣어야 하는 경우
- 배열 B의 모든 값보다 A[i]가 큰 경우
1의 경우, 어떤 인덱스 k에 대해 B[k-1] < A[i] < B[k]이다. 이 경우에서 B[k]를 A[i]로 덮어 씌운다. 여기서 A[i]가 B[k]와 같은 경우도 동일하게 처리해야 하기 때문에, B[k-1] < A[i] ≤ B[k]인 경우를 모두 이와 같이 처리할 수 있다.
2의 경우, LIS의 길이가 길어진 것으로 볼 수 있다. 그러면 배열 B에 A[i]를 이어 붙인다.
이 과정을 반복하면 배열 B는 LIS로 이루어져있지는 않지만 그 길이는 LIS의 길이와 같다. A={10,20,30,15,60,35,40} 인 경우의 배열 B를 구성해가는 과정을 순서대로 정리해보았다.
빨간색이 배열 B에 새로 추가된 값이다. 추가된 위치를 보면 B[k-1] < A[i] ≤ B[k]인 B[k]에 A[i]를 덮어씌운 것을 볼 수 있다. 결과적으로 만들어진 B = {10,15,30,35,40}은 LIS와는 아무 상관 없는 이상한 수열이지만 그 과정에서 모든 값에 대해 LIS를 이룰 수 있는 위치를 찾아 저장해나간 것이기 때문에 배열 B의 길이가 LIS의 길이와 같다.
여기서 LIS 수열을 얻고 싶다면 역시 배열 B의 값을 변경할 때 한 가지 데이터 처리를 더해주면 된다.
역시 인덱스를 관리할 배열 I를 선언하고 빨간색으로 처리된 10, 20, 30, 15, 60, 35, 40의 값을 각각 끼워넣을 때마다 배열 B상에서 바로 앞에있는 값의 A 인덱스를 저장해주면 된다. 그렇게 해두면 가장 끝에 있는 LIS값의 인덱스로부터 역추적해 LIS 수열까지 얻을 수 있다.
4. 관련문제
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
N이 1000이하로 브루트포스도 가능한 문제다.
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
그냥 거꾸로 푸는 문제
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
N이 커져서 이제 브루트포스, 다이나믹프로그래밍으로는 시간 내에 해결할 수 없다.
12738번: 가장 긴 증가하는 부분 수열 3
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
음수가 등장한다.
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
1000이하의 N에서 역추적을 해야 한다. 다이나믹 프로그래밍으로 풀 수 있다.
14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
N이 크기 때문에 이진탐색을 써야 한다. 역추적도 해줘야 한다. 음수도 나온다.
