1. 문제
https://www.acmicpc.net/problem/2631
2. 문제 이해
임의의 순서로 수열이 주어질 때, 오름차순으로 정렬하기 위해 움직이는 최소 횟수를 구하는 문제입니다.
움직일 때는 데이터를 정렬할 때처럼 자리를 서로 바꾸는 것이 아니라, 움직이는 수가 두 수 사이로 비집고 들어갑니다.
[3, 7, 5, 2, 6, 1, 4] 가 주어질 때, 아래와 같이 최소 4번으로 정렬을 완성할 수 있습니다.
3. 해결 방법
해를 구하기 위해 두 가지를 살펴봅시다.
가. 한 원소를 여러 번 움직일 필요가 없다.
생각해보면 한 원소를 자리를 두 번 움직일 경우, 그냥 한 번에 최종 위치로 움직이는 것과 다름이 없습니다.
굳이 두 번을 움직일 필요가 없고, 다시 말해 n개의 원소 중에 일부 원소만 선택해 자리를 정해주면 됩니다.
나. 안 움직이는 원소는 이미 정렬되어 있다.
이제 어떤 원소를 움직이고, 어떤 원소를 움직이지 말아야 할지 정해야합니다.
위의 예시에서 안 움직이는 원소에 집중해봅시다.
안 움직이는 원소는 [3, 5, 6] 입니다.
처음 주어진 수열에서 안 움직이는 원소 [3, 5, 6]을 표시하면 위와 같습니다.
그리고 [3, 5, 6]은 이미 순서가 정렬이 되어 있고, 반대로 움직인 [1, 2, 4, 7]은 기준이 되는 [3, 5, 6] 에 대해서 정렬되어 있지 않습니다.
결론적으로 정렬되어 있는 가장 긴 부분 수열(Longest Increasing Subsequence)을 찾아, 나머지 원소들을 한 번 씩만 움직이면 정렬을 완성할 수 있습니다.
다. 최장 증가 부분 수열(LIS) 구하는 방법
1) 동적 프로그래밍
dp[n]을 n번째 원소까지의 LIS의 길이라고 하면, dp[n+1]은 dp[0] ~ dp[n] 중 원소의 크기가 n+1번째 원소보다 작으면서 가장 큰 값에 1을 더한 값이 됩니다.
점화식은 다음과 같습니다.
\( dp[n+1] = \max\limits_{\substack{0 \le k \le n \\ S_{n+1} > S_k}} dp[k] \)
위의 예시로 DP테이블을 만들어 채워가는 모습은 다음과 같습니다.
초기화는 dp[0]값을 0으로 저장합니다.
최종적으로 DP테이블에서 최대값이 LIS의 길이가 됩니다.
DP테이블을 채우는 과정에서 수열의 길이만큼 반복하고, 해당 원소 이전의 모든 DP테이블 값을 확인하므로 시간복잡도는
\(O(n^2)\)이 됩니다.
2) 이분 탐색
DP[i]를 길이가 i인 LIS의 마지막 원소 중 가장 작은 원소라고 합니다.
길이가 짧은 LIS의 마지막 원소보다, 길이가 더 긴 LIS의 마지막 원소가 더 크다는 것이 보장이 됩니다.
따라서 이렇게 DP테이블을 채우면 자연스럽게 오름차순으로 구성이 됩니다.
오름차순으로 구성이 되어 있기 때문에 새로운 원소 값을 DP테이블에 활용할 때 이분 탐색을 사용할 수 있습니다.
이렇게 완성된 DP테이블의 길이가 LIS가 됩니다.
길이 n만큼 반복하면서 n번 이분 탐색을 하기 때문에 시간 복잡도는 \(O(n\log{n})\)으로 더 효율적인 방법입니다.
