[DP] LIS(최장 증가 부분 수열)

# DP(Dynamic Programming)

DP는 이해하는데 어려운 개념은 아니다. 문제에 적용하는 방법이나 방식, 점화식을 찾는데 어려움이 있다. 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 궁긍적인 문제를 해결할때 사용하는 문제푸는 방법의 패러다임이라고 볼 수 있다.

 

풀어서 설명하자면, 꺼내서 사용하기 쉬운 자료구조에 작은 문제에 대한 해결값을 담아둔뒤에 그 자료구조에서 꺼내어서 풀고자 하는 문제를 풀어나아가는 것이다.

# LIS(Longest Increasing Subsequence)

DP에서 가장 많이 등장하는 문제로 배열이 주어지면 만들 수 있는 증가하는 가장 긴 수열을 만드는 것이다. 사람의 직관으로 풀면 어렵지 않다. 하지만 컴퓨터는 어떻게 풀어야할까?

 

컴퓨터가 dp를 사용하지 않고 푼다고 생각해보면, 얼마나 시간이 걸리는지 알수 있다.

1. 배열의 1번째 값을 "기준" 으로 Index를 +1해가면서 확인을 한다.
2. 비교하는 값의 조건
   • 내부의 Index 값이 크면 증가를 dp값 + 1을 원래 dp값에 저장한다.

void calLIS() {
	for (int i = 0; i < n; i++) {
		dpLIS[i] = 1;
		for (int j = 0; j < i; j++) {
			if (numArr[i] > numArr[j]) {
				dpLIS[i] = max(dpLIS[i], dpLIS[j] + 1);
			}
		}
	}
}

별로 어렵지 않지만, 문제는 배열의 원소의 갯수가 백만개가 넘어가면 그때부터 문제가 생긴다. 알고리즘을 생각해보면 내부에서 for문이 하나 더 돌기 때문에 N^2의 시간복잡도가 나온다. 효율적인 방법은 아니다.

 

뭐 몇가지 방식으로 시간복잡도를 해결할 수 있다. 알고리즘을 결합이 되니깐, 이분탐색이라던지 여러가지 탐색 방법으로 해결 할 수 있다.

 

사실 이 방법은 len만 구하는 방식이다. 안에 들어가 있는 원소(수열) 구조를 알기 위해서는 자체를 구하기 위해서는 pair 자료구조를 활용하여 들어갈 수 있는 위치에 대한 Index값을 저장해야한다.

 

LIS문제는 정말 다양한 방식으로 풀이 방법이 나온다. 자주 등장하는 문제니 이번에 DP와 이론적인 부분 그리고 어느정도의 포맷을 암기하고 넘어가야했디에 포스팅을 남긴다.