문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
(문제에 풀이에 대한 코드는 제공하지 않습니다.)
https://www.acmicpc.net/problem/11053
문제 풀이
LIS(Longest Increasing Subsequence)는 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 이는 동적 계획법(DP, Dynamic Programming)을 활용하여 효율적으로 해결할 수 있는 대표적인 문제 중 하나입니다.
1. LIS란?
LIS는 배열에서 원소들의 순서를 유지하면서 값이 증가하는 가장 긴 부분 수열의 길이를 의미합니다.
예를 들어, 배열이 [10, 20, 10, 30, 20, 50]이라면:
- 가능한 증가 부분 수열: [10, 20, 30, 50]
- LIS의 길이: 4
2. DP를 활용한 LIS 알고리즘
LIS를 동적 계획법으로 해결하려면 다음과 같은 방식으로 접근합니다.
아이디어
- 각 원소를 끝으로 하는 LIS의 길이를 저장하는 DP 배열을 사용합니다.
- dp[i]는 i번째 원소를 포함한 LIS의 길이를 저장.
- 배열을 순회하면서 이전 값들과 비교해 LIS를 갱신합니다.
점화식
- arr[j] < arr[i]일 때:
- dp[i]=max(dp[i],dp[j]+1)
3. 동작과정 그림 풀이
문제의 케이스를 제가 {10, 50, 20, 30, 40, 60}으로 가정해 보겠습니다.
이때 저는 50을 무시하고 어떻게 뒤에 더 긴 수열이 있다는 것을 판단 할 수 있는지에 대한 생각이 들었습니다.
이 문제 대한 해결 방식은 현재 인덱스 이전의 인덱스 들 중에 가장 부분 수열이 긴 값에 +1을 한 값을 현재 인덱스에 저장하는 것입니다.
과정 1
Arr[0] 에는 1의 값을 고정적으로 지정합니다.
과정2
현재 인덱스 보다 이전 인덱스 중에 현재 인덱스의 값보다 작은 인덱스의 값들 중에 +1한 값의 최대값을 현재 인덱스 dp[]에 저장합니다.
과정3
계속 현재 인덱스 값보다 이전 인덱스들 중에 값이 작은 것들을 대상으로 dp[] + 1 한 값들 중에 가장 큰 값(max)을 현재 인덱스 dp[] 에 저장합니다. 마지막 인덱스 까지 과정을 반복하다 보면 가자 마지막 인덱스 dp[]에는 가장 긴 수열의 값이 저장 되게 됩니다.
4. 다른 테스트 케이스
Arr[] : {10, 50, 10, 30, 20, 40, 70} 이 주어질때 동작과정을 그림으로 나타내 보겠습니다.
정답 후보군이 {10, 50, 70}, {10, 30, 40, 70}, {10, 20, 40, 70} 이렇게 가능한데 가장 긴 수열의 값은 4인것을 구할 수 있습니다.