LIS (최장 증가 부분 수열)

 

📍 정의 및 특징

주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제

 

 

📍 LIS 실행 방법

  1) DP 활용             → 시간 복잡도 : O(N^2)

  2) 이분 탐색 활용   → 시간 복잡도 : O(N log N)

 

 

📍 필요 변수

✔ DP / LIS 배열

 

 

🧩 1)  DP를 활용한 LIS 실행 과정 : O(n^2)

1. DP 테이블을 생성하여 각 원소를 마지막으로 하는 LIS의 길이 저장
2. 초기값으로 모든 원소의 LIS 길이를 1로 설정
3. 각 원소 i에 대해, 이전 원소 j(0 <= j < i)를 검사하여 i번째 원소를 j번째 원소 뒤에 붙일 수 있는지 확인. 
   (nums[i] > nums[j]인지로 판단)
4. 만약 nums[i] > nums[j]라면, dp[i] = max(dp[i], dp[j] + 1) 수행 ⇨ i번째 원소를 마지막으로 하는 LIS의 길이 갱신
5. 모든 i에 대해 위 과정을 반복하면, dp 테이블의 가장 큰 값이 LIS의 길이 !

→ 2중 for문으로 각 수 직접 비교하며, 증가하는 부분 수열 크기 카운트

 - i : 1 ~ n - 1

 - j : 0 ~ i - 1

 

🧩 2)  이분 탐색을 활용한 LIS 실행 과정 : O(N log N)

1. 배열 / 리스트를 초기화합니다. (= 현재까지의 증가하는 부분 수열을 저장하는 자료구조로 활용)
2. 주어진 수열의 원소를 순차적으로 탐색 ⇨ 이분 탐색  !
3. 현재 원소를 자료구조에 삽입할 위치를 이분 탐색으로 찾음. 이분 탐색은 자료구조 내에서 현재 원소를 삽입할 수 있는 가장 작은 위치 (마지막 중 최솟값) 를 찾습니다. 이 위치는 자료구조에서 현재 원소보다 큰 값 중 가장 작은 값의 위치입니다.
4. 찾은 위치에 현재 원소를 삽입. 만약 위치가 자료구조의 길이와 같다면, 현재 원소는 현재까지의 가장 긴 증가하는 부분 수열의 뒤에 추가.
5. 자료구조를 유지하면서 삽입 위치를 업데이트하고, 필요에 따라 최적해 갱신
   (= 현재까지의 가장 긴 증가하는 부분 수열 길이 업데이트)
6. 주어진 수열의 모든 원소에 대해 위 과정을 반복하면, 이분 탐색을 활용한 LIS를 구할 수 있음

- 정확한 LIS를 구할 순 없음

- LIS 길이 잴 때 유용

 

 

 

➕ 예제

[백준/JAVA] 11053번: 가장 긴 증가하는 부분 수열

[백준/JAVA] 11054번: 가장 긴 바이토닉 부분 수열

[백준/JAVA] 11055번: 가장 큰 증가하는 부분 수열

[백준/JAVA] 11722번: 가장 긴 감소하는 부분 수열

---

(참고)

- ChatGPT

[JAVA] LIS 알고리즘

[Algorithm] 최장 증가 부분 수열(LIS) 알고리즘 (JAVA로 구현)

[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)