[종만북 문제] 최대 증가 부분 수열 (문제 ID : LIS, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 먼저 완전 탐색부터 시작해보자. 그 후, 전체 답의 점수를 반환하는 것이 아니라 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾸자.

2. 재귀 호출에서 이전의 선택과 관련된 정보는 최대한 줄이자. 그럼으로써, 우리는 최대한 중복되는 문제를 많이 만들어낼 수 있다.

---

[종만북 문제] 최대 증가 부분 수열 (문제 ID : LIS, 난이도 : 하)

일단, 아래와 같이 간단하게 for-loop 으로 풀어볼 수 있다.

#include <iostream>
#include "stdlib.h"
#include <vector>
#include <cmath>

using namespace std;

int N;
int arr[500];
int cache[500];

// cahce[i] : the length of LIS, which contains arr[i] in the subsequence
void sol()
{
	for (int i = 0; i < N; ++i)
	{
		cache[i] = 1;
		for (int j = 0; j <= i; ++j)
		{
			if (arr[j] < arr[i])
			{
				cache[i] = max(cache[i], cache[j] + 1);
			}
		}
	}

	int maxVal = 0;
	for (int i = 0; i < N; ++i)
		maxVal = max(maxVal, cache[i]);
	cout << maxVal << endl;
}

void inputHandler()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
		cache[i] = 0;
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();
		
		sol();
	}

	return 0;
}

 

책에서는 문제를 푸는 순서를 다음과 같이 제시한다 : 완전 탐색 -> DP(1) -> DP(2).

먼저 완전 탐색을 하는 방법부터 살펴보자.

 

그리고 동적 계획법으로 푸는데, 이 때 아래와 같은 아이디어를 적용한다.

이 아이디어를 적용하면, 아래와 같이 lis 함수를 만들 수 있다.

나는 마지막 녀석을 기준점으로 잡았는데, 책은 시작점을 기준으로 잡았다. 🤣 시간 복잡도는 둘 다 O(n^2) 이다.

위의 코드는 결국 cache 를 순회하면서 최댓값을 구해주어야 한다. 그런데 아래 코드의 경우, 그 작업을 생략할 수 있다!

리턴값으로는 lis3(-1) -1 을 해 준다. 왜냐하면 S[-1] 은 우리가 임의로 만든 값이기 때문이다. 😮

이게 왜 잘 작동하는 걸까? 시작지점을 -1 로 잡고, S[-1] = INT_MIN 라고 해 놓으면, 모든 시작 지점을 전부 체크할 것이기 때문이다! 😎

 

사실 O(nlgn) 으로도 구현할 수 있긴 하다. 책에서는 다음과 같이 원리를 소개만 하고 넘어가긴 하지만...

음, 예전에 분명 풀었을 텐데 오랜만에 보니 또 낯설게 느껴진다. 신비하고 아름다운 알고리즘의 세계...