[PS][Java] java DP

가장 긴 증가하는 부분 수열

틀린 풀이

1. 입력을 받는다.
2. idx 0부터 n-1까지 아래의 과정을 진행한다.
3. 이전 idx까지 가장 큰 값과 그 값까지의 가장 긴 증가하는 부분 수열을 기록한다.
4. 만약 현재의 값이 기록된 가장 큰 값보다 크다면 길이가 1 늘어난다.
5. 아니라면 이전 기록을 그대로 유지한다.

   7 1 4 5 2 3 4 5 의 경우 3을 출력합니다.

   맞는 풀이 : LIS

   • dp[i] = arr[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분수열의 길이

6. LIS는 O(N^2)이다.
7. dp(i)은 1로 초기화
8. dp(i)은 arr(k)보다 arr(i)이 더 클 때는 dp(k)+1로 갱신.(k는 0~i-1)
9. 단 dp(i) < dp(k)+1인 경우만 갱신해야함.

   코드

   java로 구현한 코드는 여기에 있습니다.

가장 긴 감소하는 부분 수열

풀이 : LDS

LIS의 반대로 생각합니다. LIS가 index 0부터 시작했다면 LDS는 idx 마지막부터 시작해야 합니다.

코드

java로 구현한 코드는 여기에 있습니다.

가장 큰 증가하는 부분 수열

풀이 : LBS

LIS와 같은 방법으로 접근한다.

코드

java로 구현한 코드는 여기에 있습니다.

가장 큰 바이토닉 부분 수열

풀이 :

LIS + LDS를 적용한다. 12321의 경우 LIS는 123, LDS는 321이므로 LIS+LDS-1을 출력한다.

코드

java로 구현한 코드는 여기에 있습니다.

가장 큰 증가하는 부분 수열2

풀이 :

이분탐색을 통한 nlogn풀이를 진행한다.

1. 먼저 비어있는 ArrayList arr를 만들고 outofboundException을 막기위해 0을 넣어둔다.
2. 입력되는 값에 대해서 아래의 과정을 진행한다.
3. arr의 마지막 값보다 더 크다면 뒤에 add한다.
4. arr의 마지막 값보다 더 작다면 그 값의 인덱스를 찾아서 대체한다.
5. arr의 마지막 값보다 더 작은데 그 값이 없다면 그 값보다 큰 가장 작은 수의 idx를 찾아서 대체한다.

3
10 5 20 을 입력받으면

1. arraylist를 만들고 {0}를 넣는다.
2. {0,10}
3. 5는 10보다 작고 5가 없기 때문에 5보다 큰 가장 작은 수 10의 인덱스 1을 찾아서 대체한다. {0,10} -> {0,5}
4. {0,5,20}

5
10 50 20 30 40 을 입력받으면

1. {0}
2. {0,10}
3. {0,10, 50}
4. {0,10, 20}
5. {0,10, 20, 30}
6. {0,10, 20, 30, 40}

코드

java로 구현한 코드는 여기에 있습니다.

가장 큰 증가하는 부분 수열3

풀이 :

가장 큰 증가하는 부분 수열2 문제에서 주어지는 초기값을 0이 아닌 -1234567890로 한다. int형은 대략 +-21억까지 들어간다.

코드

java로 구현한 코드는 여기에 있습니다.

가장 큰 증가하는 부분 수열4

가장 큰 증가하는 부분 수열5

풀이

4번 5번 문제 같은 코드로 풀이합니다.

이 문제는 LIS 길이뿐만 아니라, LIS 자체를 요구합니다. 일반적으로 추적은 대부분 인덱스를 활용한다.를 기억하고 설명을 시작하겠습니다.

먼저 LIS는 가장 큰 증가하는 부분 수열2에서 설명한 방법이 정해임을 기억합니다. 매번 새로운 값이 뒤에 추가될 것인지, 중간에 추가될 것인지 판단됩니다. 중간에 추가되는 경우는 LIS의 길이를 바꾸지 않습니다. 이미 값이 존재하면 덮어쓰고, 아니면 값보다 큰 가장 작은 값을 덮어씁니다. 길이는 변화시키지 않지만 구성요소의 값을 낮추어서 LIS가 최대한 길어질 수 있도록 보장합니다.

예를 들어 1 5 10까지만 보면 LIST는 {1,5,10}입니다. 1 5 10 4 6까지만 보면 LIS는 {1,5,10},{1,4,6} 두 가지 경우가 있지만 후자가 LIS가 더 길어질 수 있도록 가능성을 열어둡니다. 1 5 10 4 6 7이나 1 5 10 4 6 11이 오는 경우 모두 LIS를 길이 4로 구할 수 있습니다. 하지만 1 5 10 4까지만 보고 LIS를 출력한다면 {1,4,10}이 출력되는 문제가 있습니다. 이러한 경우 LIS의 길이뿐만 아니라 LIS를 출력해야하는 경우 index를 활용한 추적을 사용합니다.

위에서 설명한 방법대로 {}에 하나의 값을 추가하는 것은 동일합니다. 하지만 값을 추가할 때 값이 추가된 idx를 같이 기록합니다.

tracking배열은 {값이 LIS에 추가된 idx, 추가된 값}의 구조를 가집니다.

• LIS의 마지막 값보다 작은 값이 들어와서 갱신이 일어나는 경우, 첫 번째 요소는 lowerbound를 사용해서 찾은 idx를 의미합니다.
• LIS의 마지막 값보다 큰 값이 들어와서 추가가 일어나는 경우, 첫 번째 요소는 LIS의 가장 큰 idx를 의미합니다.

추가된 값	LIS상태	tracking 상태
10	{10}	{ (0,10) }
20	{10, 20}	{ (0,10), (1,10) }
10	{10, 20}	{ (0,10), (1,10), (0,10) }
30	{10, 20,30}	{ (0,10), (1,10), (0,10), (2,30) }
20	{10, 20,30}	{ (0,10), (1,10), (0,10), (2,30), (1,20) }
50	{10, 20, 30, 50}	{ (0,10), (1,10), (0,10), (2,30), (1,20), (3,50) }

아래와 같이 갱신되는 구조를 표로 나타내면 각 행에 있는 가장 아래 {key,value} pair의 value를 출력하는 것이 LIS임을 알 수 있습니다.

{10,	20,	30,	50 }
(0,10)	(1,10)	(2,30)	(3,50)
(0,10)	(1,20)	-	-

tracking을 나타내는 배열과 LIS의 길이가 있습니다. LIS의 길이 -1 = 마지막에 추가된 값의 idx입니다. 따라서 tracking 배열을 뒤에서부터 앞으로 순회하면서 LIS 배열의 각 index에 가장 늦게 추가된 값을 출력합니다. 위 예에서는 LIS의 길이가 4이므로 인덱스 3일 때는 (3,50), 2일때는 (2,30), 1일 때는 (1,10), 0일 때는 (0,10)을 찾고 이에 해당하는 값을 출력합니다. 값 출력을 stack을 통해서 거꾸로 진행하면 LIS의 요소를 출력할 수 있습니다.

코드

java로 구현한 코드는 여기에 있습니다.

일반적으로 추적은 대부분 인덱스를 활용한다.