LIS (Longest Increasing Sequence) / 최대 증가 부분수열 알고리즘1

LIS문제를 풀기 위한 알고리즘 사이트 문제들을 다음 링크를 참고하세요

http://www.codeup.kr/JudgeOnline/problem.php?id=3735

https://algospot.com/judge/problem/read/LIS

---

LIS 문제를 해결 하기 위해 제일 많이 쓰이는 기본적인 방법은 

동적계획법일것입니다. 동적계획법을 풀어 내기위해선 재귀적인 방법으로 

부분문제들을 해결해 나가는 방법을 선택해야 합니다.

LIS를 해결하기 위한 기본 개념은 다음과 같습니다.

1. 수열의 집합 S가 모두 순차증가를 이루고 있어야 한다.

2. 수열의 선택의 순서를 정하여 부분 문제의 수를 줄인다. (중복을 제거할 수 있게됨)

3.선택된 수열 S는 이전에 선택한 수열이 무엇이 있는지 알 필요 없다.

1번은 문제에 따라 자명하며

2번은 여러 문제에서 적용할 수 있는 좋은 방법입니다.

LIS문제와 같은경우에는 수열을 괜히 중간에서 선택해서 시작할 필요 없이 왼쪽부터 숫자를 선택해 나간다면

중복을 줄일 수 있어 더 빠른 시간내에 풀 수 있게 됩니다.

이때 왼쪽에서 숫자를 선택하면서 선택된 수보다 큰 수를 다시 부분 수열 S'로 만듭니다.

가령

{1,4,5,3,10} 이라는 수열이 있었다면 1을 시작으로 하여 다음 수열은 {4, 5, 3, 10}을 선택하여 

다시 재귀적으로 문제를 해결해 나가는 것입니다. 

단 이때 순차증가되어야 함은 잊지 말아야죠.

이렇게 재귀적으로 풀게되면 3번 조건을 만족하게 됩니다. 이전의 선택한 숫자는 알 필요가 없는것이죠.

이러한 조건을 만족하며 코드를 작성하면 다음과 같습니다.

물론 제가 온전히 생각해낸 코드가 아니란 점은 아쉽습니다 ㅜㅜ

처음엔 합병정렬처럼 분할정복 기법을 적용하려 했지만 쉽지 않아 포기했죠.

동적계획법에서 중요한 개념은 또 memoization 기법입니다.

메모리 공간을 희생하고 그 대신 속도를 얻어내는 방법이죠. (공짜는 없습니다)

위와 같은 코드를 통하면 의 시간복잡도를 갖게 된다고는 하는데

이 부분이 명확히 이해가 잘 가지 않네요.

n개의 부분문제에 각 문제마다 n번의 반복문을 돈다고 하는데

저로서는 당장 납득이 안가네요 코드 돌아가는건 제대로 이해 했다고 생각하는데....

추후에 알게되면 추가로 작성이 필요할 듯 싶습니다. ㅜㅜㅜ