[Algorithm] LIS (Longest Increasing Sequence)

[Algorithm] 최장 증가 수열 (LIS)

최장 증가 수열

• ex) [7, 2, 3, 8, 4, 5] > [2, 3, 4, 5]가 가장 길게 증가하는 수열이다.

---

시간 복잡도

• DP : O(n^2)
• Lower Bound : O(nlogn)
• 즉, n이 크다면 Lower Bound를 활용하는 것이 좋다!

---

구현 내용(DP), 가장 긴 길이 출력

longestIncreasingSequence(int[] arr)

• arrLen = arr.len, dp = new int[arrLen];
• for comp = 0 to arrLen - 1 //비교할 요소(이전) 인덱스
  • for idx = comp + 1 to arrLen //현재 요소 인덱스
    • arr[idx] > arr[comp] ? dp[idx] = max(dp[idx], dp[comp] + 1); //만일 이전 요소보다 지금 요소가 더 크다면 지금 길이와 이전 요소의 길의 + 1 중 더 큰 값으로 교환.
• 만일 해당 array를 반환하라고 한다면 dp를 arrLen의 2차원 배열로 선언.
• 마지막 값이 가장 큰 요소의 값이 변하는 부분의 인덱스 값을 모아 반환하면 될 것 같다!

---

구현 방법(Lower Bound)

• 단순 가장 긴 길이를 출력하는 방법과 가장 긴 배열 출력하는 법 또한 존재한다.

길이 출력

• 아래 배열의 LIS를 구한다고 하자.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	30	40

• 동일한 크기를 가지는 새로운 배열을 만들어 index를 배열 크기만큼 돌며 아래와 같은 순서로 담는다.

LIS 크기 찾기

• lis_size는 1부터 시작한다.
• arr_cnt는 1부터 arr_size - 1까지 돈다.
• 0번째 인덱스를 복사한다.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	10	40
LIS[i]	10

• 만일 A[arr_cnt] 값이 LIS[lis_size - 1]보다 크면 LIS[lis_size++] = A[arr_cnt]로 값을 복사한다.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	10	20

• 만일 A[arr_cnt] 값이 LIS[lis_size - 1]보다 작으면 이진 탐색을 통해 적절한 위치에 A[arr_cnt]값을 LIS 배열에 복제한다.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	20

• 위 과정을 반복하여 LIS 배열의 크기를 찾는다.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10

• LIS[lis_cnt++] = A[arr_cnt]

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	20

• LIS[2] = A[arr_cnt]

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	15

• LIS[lis_cnt++] = A[arr_cnt]

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	15	40

• LIS 배열의 크기는 4이다.

LIS 배열 찾기

• 큰 흐름은 위와 같으나 A[i]가 LIS배열 어디에 저장되는지 기록하는 배열이 하나 더 필요해진다.

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	10
recode[i]	0

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	10	20
recode[i]	0	1

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	20
recode[i]	0	1	0

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10
recode[i]	0	1	0	1

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	20
recode[i]	0	1	0	1	2

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	15
recode[i]	0	1	0	1	2	2

index	0	1	2	3	4	5	6
A[i]	10	20	5	10	20	15	40
LIS[i]	5	10	15	40
recode[i]	0	1	0	1	2	2	3

• recode[i]를 큰 index부터 돌며 recode[i]번째에 A[i]를 기록한다. 이미 값이 들어가 있으면 무시한다.