[알고리즘] LIS 알고리즘인데 DP를 이용한

LIS(Longest Increasing Subsequence) 알고리즘

• LIS == 최장 증가 수열로, 임의의 수열이 주어질 때 이 수열의 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 말한다.
• 항상 이전 원소보다 커야하기 때문에 같은 원소가 연속으로 와서는 안된다.
  (ex. [1 1 2]의 수열에서 최장 증가 수열은 [1 1 2]가 아닌 [1 2])

---

✍️ DP를 이용한 LIS 풀이 방법

: DP[n]에는 DATA의 n번째 인덱스까지의 배열 중 최장 증가 수열이 저장된다.

1) DP를 모두 1로 초기화 한다. 이후 DATA의 처음 ~ 끝까지 돌면서 현재 인덱스 이전 인덱스들과 비교

• 현재 인덱스의 DATA가 이전 인덱스의 DATA보다 크고,
• 현재 인덱스의 DP가 이전 인덱스의 DP + 1보다 작을 때

➡️현재 인덱스의 DP를 이전 인덱스의 DP + 1로 갱신한다.

2) DATA[1] 순서일 때

• 이전 인덱스인 DATA[0]과 비교하여 DATA[1] > DATA[0]이고, DP[0] + 1 > DP[1]이므로 DP[1]을 DP[0] + 1로 갱신한다.
  

3) DATA[2] 순서일 때

• 이전 인덱스인 DATA[0]과 비교하여 DATA[2] > DATA[0]이고, DP[0] + 1 > DP[2]이므로 DP[2]을 DP[0] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[0]과 비교하여 DATA[1] > DATA[2]이므로 넘어간다.

4) DATA[3] 순서일 때

• 이전 인덱스인 DATA[0]과 비교하여 DATA[3] > DATA[0]이고, DP[0] + 1 > DP[3]이므로 DP[3]을 DP[0] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[1]과 비교하여 DATA[3] > DATA[1]이고, DP[1] + 1 > DP[3]이므로 DP[3]을 DP[1] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[2]과 비교하여 DP[3] == DP[2] + 1이므로 넘어간다.

5) DATA[4] 순서일 때

• 이전 인덱스들의 DATA가 전부 DATA[4]보다 크기 때문에 넘어간다.

6) DATA[5] 순서일 때

• 이전 인덱스인 DATA[0]과 비교하여 DATA[5] > DATA[0]이고, DP[0] + 1 > DP[5]이므로 DP[5]을 DP[0] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[1]과 비교하여 DATA[5] > DATA[1]이고, DP[1] + 1 > DP[5]이므로 DP[5]을 DP[1] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[2]과 비교하여 DP[5] == DP[2] + 1이므로 넘어간다.

• 이전 인덱스인 DATA[3]과 비교하여 DATA[5] > DATA[3]이고, DP[3] + 1 > DP[5]이므로 DP[5]을 DP[3] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[4]과 비교하여 DP[5] > DP[4] + 1이므로 넘어간다.

7) DATA[6] 순서일 때

• 이전 인덱스인 DATA[0]과 비교하여 DATA[6] > DATA[0]이고, DP[0] + 1 > DP[6]이므로 DP[6]을 DP[0] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[1]과 비교하여 DATA[6] > DATA[1]이고, DP[1] + 1 > DP[6]이므로 DP[6]을 DP[1] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[2]과 비교하여 DP[6] == DP[2] + 1이므로 넘어간다.

• 이전 인덱스인 DATA[3]과 비교하여 DATA[6] > DATA[3]이고, DP[3] + 1 > DP[6]이므로 DP[6]을 DP[3] + 1로 갱신한다.
  

• 이전 인덱스인 DATA[4]과 비교하여 DP[6] > DP[4] + 1이므로 넘어간다.

• 이전 인덱스인 DATA[5]과 비교하여 DATA[5] > DATA[6]이므로 넘어간다.

8) 이렇게 모든 인덱스에 대해 DP를 갱신한 이후, DP에 있는 값 중 가장 큰 값이 최장 증가 수열의 길이가 된다.

---

🖥️ 구현 코드

#include <iostream>
using namespace std;

int datas[7];
int dp[7];

int solution(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (datas[j] < datas[i])
			{
				if (dp[i] < dp[j] + 1)
					dp[i] = dp[j] + 1;
			}
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[i])
			max = dp[i];
	}
	return max;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n = 7;
	datas[0] = 2;
	datas[1] = 4;
	datas[2] = 3;
	datas[3] = 5;
	datas[4] = 1;
	datas[5] = 8;
	datas[6] = 7;

	for (int i = 0; i < n; i++)
		dp[i] = 1;

	cout << solution(n);
}


실행 결과 : 4

---

👁️‍🗨️ 참고
https://source-sc.tistory.com/14
https://blog.naver.com/lgh121546/221872278258