최장 증가 부분수열 (Longest Increasing Subsequence)
: 주어진 수열에서 만들 수 있는 오름차순을 만족하는 가장 긴 부분수열을 뜻한다.
1
2
3
ex)
[3, 2, 4, 1, 5]의 LIS는 [2, 4, 5]
[5, 3, 4, 1, 6, 8, 9]의 LIS는 [3, 4, 6, 8, 9]
LIS문제는 dp(Dynamic Programming)기법으로 해결할 수 있다.
수열이 주어졌다면 수열과 같은 길이를 같는 배열을 만들어주자.
1
2
arr = [5, 3, 4, 1, 6, 10, 8, 9]
dp = [0] * len(arr)
dp 배열은 해당 위치까지 만들 수 있는 LIS를 저장해준다.
dp[i]를 갱신해줄 때는 두가지 조건을 갖추어야 한다.
arr[j]<arr[i]: 오름차순을 만족하기 위함len(dp[j]) + 1>len(dp[i]): 순회하면서 조회중인dp[j]의 길이에 나 자신을 포함한 값이 현재dp[i]의 길이보다 길어야 한다.
1
2
3
4
5
for i in range(len(arr)):
dp[i] = [arr[i]]
for j in range(0, i):
if (arr[i] > arr[j]) and ((len(dp[j]) + 1) > len(dp[i])):
dp[i] = dp[j] + [arr[i]]
모든 dp를 갱신해준뒤 출력해보면 아래와 같이 해당 위치까지에서 찾을 수 있는 lis를 저장한 것을 확인할 수 있으며 가장 긴 길이를 가진 [3, 4, 6, 8, 9]를 잘 찾아낸 것을 확인할 수 있다.
1
2
print(dp)
# [[5], [3], [3, 4], [1], [3, 4, 6], [3, 4, 6, 10], [3, 4, 6, 8], [3, 4, 6, 8, 9]]
LIS 알고리즘으로 풀 수 있는 문제
이 문제는 N명의 학생들이 1~n까지의 번호표를 달고 무작위 순서로 줄을 서있을 때 최소한의 횟수로 학생들을 옮겨 번호 순서대로(오름차순) 다시 줄을 세워야 하는 문제이다.
이 문제를 LIS알고리즘을 활용해 해결할 수 있는데 최소한의 횟수만큼만 움직여야 하니까 주어진 배열에서 LIS를 구하면 올바른 위치에 서있는 학생의 수를 구할 수 있게 되고, 그 외의 학생들을 올바른 위치로 옮겨주면 올바르게 줄을 세울 수 있다. 간단히 식으로 구하면 아래와 같다.
1
최소한의 횟수 = (학생들의 수) - (현재 배열에서 구한 LIS의 길이)
식에서 우리가 알고 있는 것은 학생들의 수이므로 구어진 배열에서 LIS의 길이만 구하면 된다. 이 글에서 소개한 방법으로는 LIS자체를 구했는데 조금만 수정해주면 쉽게 LIS의 길이를 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
input = sys.stdin.readline
n = int(input())
arr = []
dp = []
maxValue = 0
for _ in range(n):
arr.append(int(input()))
dp.append(0)
for i in range(n):
dp[i] = 1
for j in range(0, i):
if arr[i] > arr[j] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
if dp[i] > maxValue:
maxValue = dp[i]
print(n-maxValue)