LIS(가장 긴 증가하는 부분수열)

 이름만 봐도 이해하기 힘든 LIS(Longest Increasing Subsequence)는 쉽게 말하자면 나열된 수들 중 오름차순으로 정렬된 가장 긴 부분수열이다.

 

---

이해하기

3

1

4

5

2

7

 위와 같은 수열이 있다고 하자. 이 때 부분수열은 길이가 1인 부분수열도 있을것이고, 2인 부분수열도 있을것이고, 6인 부분수열도 있을것이다.

 제일 앞에 있는 수를 선택할 경우를 생각해보자.

3(★)

1

4

5

2

7

 3까지의 수열을 보면 3 밖에 존재하지 않으므로 길이는 1이다. (이 길이는 나중에 써먹어야 하므로 저장해야 한다.)

3

1(★)

4

5

2

7

 그 다음 1까지의 수열을 보자.

 1까지의 수열([3, 1])에서 부분수열의 최장길이를 구하려면 어떻게 해야 할까? 3과 1을 비교해서 3이 1보다 크므로 3은 부분수열에 들어갈 수 없다. 그렇다면 1만으로 이루어진 부분수열만이 가능하다. 그러므로 최장길이는 1이 된다.

3

1

4(★)

5

2

7

 그 다음 4까지의 수열을 보자. 숫자가 1개 혹은 2개인 경우는 숫자를 비교해서 수열의 길이는 1이거나 2이므로 간단하지만, 이제부터는 헷갈릴 수 있으므로 주의해서 봐야 한다.

 4까지의 수열([3, 1, 4])에서 부분수열의 최장길이를 구하려면 어떻게 해야 할까? 3부터 선택해보고, 그후 1부터 선택하는 경우를 하려고 보니 기시감이 든다. 우리는 이미 이 과정을 거쳤기 때문이다.

 3까지의 수열의 최장길이는 1이었다. 1까지의 수열의 최장길이는 1이었다. 3까지의 수열에서 1까지의 수열로 넘어오는 과정을 잘 살펴 보자.

 3까지의 부분수열의 최장길이가 1인 것은 확실하다. 1까지의 수열을 보면 '오름차순'의 조건을 지키기 위해 3과 1을 비교했다. 그래서 1보다 3이 더 컸기 때문에 최장길이가 1이 되었다. 만약 [1, 2]였다면? 1보다 2가 크므로 '오름차순'의 조건은 지켜지고 최장길이는 2가 된다. 이것은 1까지의 수열의 최장길이(1)에 숫자 2를 포함한 길이와 같다.

 즉, 어떤 수(array[n])까지의 부분수열의 최장길이는 그전 수들 중 array[n]보다 작고, 가장 array[n]과 가까운 위치의 숫자까지의 부분수열의 최장길이에 1을 더한 것(array[n]을 포함하는 것)이다.

 우리의 수열로 살펴보자면, 4까지의 부분수열의 최장길이는 1까지의 부분수열의 최장길이에 1(4를 포함)을 더한 것이다. 2까지의 부분수열의 최장길이는 (2보다 큰 4, 5를 건너뛰어서) 1까지의 부분수열의 최장길이가 된다.

 이 문제를 해결하는 데에 Dynamic Programming을 사용하는 것도 그런 이유에서이다. Dynamic Programming은 어떤 큰 문제를 잘게 쪼개어 해결하는 방법으로, LIS를 해결할 때 가장 작은 수열부터 최장길이를 구해가며(큰 수열을 쪼개서) 원하는 길이까지 부분수열의 최장길이를 구할 수 있다.

 

---

코드로 나타내기

 그렇다면 이제 코드로 나타내보자.

 우리가 이해하기에서 했던 과정을 천천히 생각해보면 아래와 같이 정리된다.

 

1. 숫자를 앞에서부터 하나씩 꺼내서 기준점으로 삼는다.

2. 제일 처음 기준점을 꺼내면 부분수열은 그 기준점 자체와 같으므로 부분수열의 최장길이는 1이 된다.

3. 수열의 길이가 2 이상이 되면 기준점 앞에 있는 수들 중 기준점보다 작고 기준점과 제일 가까운 위치에 있는 수를 찾는다.

4. 3에서 찾은 수까지의 부분수열의 최장길이를 찾아 +1을 해준다.

 

# 파이썬 코드

# 변수 설명
# 1. n : 수열의 크기
# 2. array : 수열
# 3. dp=[0 for i in range(n)] : 수열과 같은 길이의 0으로 초기화된 배열.
# 	각 칸마다 i개짜리 수열의 부분수열 중 가장 긴 부분수열의 길이를 저장한다.
#	그렇기 때문에 기준점의 개수(=수열의 길이)만큼 길이를 만들어준다.

for i in range(len(nums)): # 0, 1, 2, 3, 4, ... 순으로 길이를 바꿔간다.

	for j in range(i) : # 기준점까지의 수열에서 숫자를 하나씩 꺼내서(기준점 직전까지만 꺼내진다.)

	# 1. 기준점보다는 작고
        # 2. 부분수열의 길이가 더 길면
        # 그 길이를 기준점의 부분수열 중 가장 긴 부분수열의 길이로 저장한다.
        
        if array[i]>array[j] and dp[i]<dp[j]:
            
            dp[i]=dp[j]
    
    dp[i]+=1 # 기준점 스스로를 포함해야 하므로 +1을 해준다.

# 위의 for문을 다 돌아서 부분수열들의 길이를 다 모아놓으면
# 그중에서 가장 긴 길이를 출력한다.
print(max(dp))

 

// 자바코드

public class LIS {

	public static void main(String[] args) {
		
		int n=6;
		int[] array= {3, 1, 4, 5, 2, 7};
		int[] dp=new int[n];
		
		/*
		 * 변수 설명
		 * 1. n : 수열의 길이
		 * 2. array : 수열
		 * 3. dp : 수열과 같은 길이의 0으로 초기화된 배열.
		 * 	각 칸마다 i개짜리 수열의 부분수열 중 가장 긴 부분수열의 길이를 저장한다.
		 * 	그렇기 때문에 기준점의 개수(=수열의 길이)만큼 길이를 만들어준다.
		 * 
		 * */
		
		for (int i=0; i<n; i++) {
			
			for (int j=0;j<i;j++) {
				
				if (array[i]>array[j] && dp[i]<dp[j]) {
					
					dp[i]=dp[j];
				
				}
				
			}
			
			dp[i]=dp[i]+1;
		}
		
        	// 결과 출력하기 위해.
		int result=0;
		for (int num:dp) {
			result=Math.max(result, num);
		}
		
		System.out.println(result);

	}

}

---

응용하기

 이제는 배운 LIS 알고리즘을 응용해보자. 아래의 전깃줄 문제는 LIS 알고리즘으로 해결할 수 있다.

---

www.acmicpc.net/problem/2565

2565번: 전깃줄

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

---

 언뜻 보면 이 문제가 왜 LIS문제인지 이해하기 어렵다. 문제를 좀 더 자세히 보자. 전깃줄이 서로 교차하기 않게 해야한다는 조건이 있다. 전깃줄을 교차하지 않게 하려면 어떻게 해야 할까? 바로 한 전봇대의 인덱스가 늘어감에 따라 다른 전봇대의 인덱스도 늘어나면 된다.

 위 그림과 같이 A전봇대의 값이 증가함에 따라 B전봇대의 값도 증가한다면 전깃줄을 겹치지 않고 설치할 수 있다. 하지만 아래 그림처럼 A전봇대의 값이 증가함에도 B전봇대의 값이 변동된다면 전깃줄이 겹칠 수 밖에 없다.

 그렇다면 A전봇대의 값과 B전봇대의 값을 입력받아서 A전봇대의 값을 기준으로 오름차순 정렬하고, B전봇대의 값들만을 따로 모아 LIS알고리즘을 이용한다면 전깃줄을 최대 몇 개까지 설치가능한지를 구할 수 있을 것이다. 이 문제에서 요구하는 것은 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수이므로 전체 전깃줄 개수에서 설치가능한 전깃줄의 최대개수를 빼면 없애야 하는 전깃줄의 최소 개수를 구할 수 있다.

import sys

n=int(sys.stdin.readline()) # 전깃줄의 개수

elec = [] # A전봇대와 B전봇대의 전깃줄 연결 정보
only_b = [] # B전봇대의 연결 정보만 저장하는 배열
dp = [0 for _ in range(n)]

for i in range(n): # 전깃줄 연결 정보를 저장한다.
    elec.append(list(map(int, sys.stdin.readline().split())))

elec.sort(key = lambda x:x[0]) # A전봇대 기준으로 정렬

for i in range(n):
    only_b.append(elec[i][1]) # B전봇대의 연결 정보만 저장한다.

# LIS
for i in range(n):
    for j in range(i):
        if only_b[i] > only_b[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(n - max(dp))

---

가장 긴 증가하는 부분수열을 구하는 더 빠르고 쉬운 방법

백준에 있는 문제를 풀다가 가장 긴 증가하는 부분수열을 구하는 더 빠르고 쉬운 방법을 알게 되어서 추가한다.

from bisect import bisect_left
import sys

n=int(sys.stdin.readline())

a=list(map(int, sys.stdin.readline().split()))

dp=[]

for i in a: # 원래의 수열에서 숫자를 하나씩 꺼내서
    k=bisect_left(dp, i) # dp에서 이 숫자가 들어갈 위치(k)를 찾는다.
    if len(dp)<=k: 만약 들어갈 위치가 새로 추가되어야 하는 위치라면
        dp.append(i) # dp에 그 숫자를 추가한다.
    else: # dp 안에 있는 위치라면
        dp[k]=i # 값을 바꿔준다.

print(len(dp))

# def bisect_left(a: Sequence[_T], x: _T, lo: int=..., hi: int=...)
# Return the index where to insert item x in list a, assuming a is sorted.

# The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. So if x already appears in the list, a.insert(x) will insert just before the leftmost x already there.

# Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.