(JAVA) 백준 12015번 : 가장 긴 증가하는 부분 수열 2 --- [이분탐색, DP, LIS]

www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

안녕하세요.

 

LIS 알고리즘을 사용하는 문제입니다. (+ DP도)

 

 

그런데 더욱 시간을 줄이기 위해

이분탐색 알고리즘까지 겸비합니다.

 

 

N개의 배열이 있을 때,

 

이분탐색 알고리즘은 시간복잡도가 O(logN) 인데요.

여기에 한 번 배열을 순회하기 때문에 총 O(NlogN) 의 시간복잡도가 생기는 매커니즘으로 해결했습니다.

 

만약, 2중 for문으로 수행했다면 O(N^2) 이 소모되겠죠 ?

 

 

그럼 이분탐색을 어디에 사용하냐?!

 

바로, DP 배열에 사용합니다.

 

여기서 사용하는 DP 배열은, 사실 DP라고도 볼 수 없을 수도 있지만

부분 수열을 가리킵니다.

 

그래서, 왼쪽부터 오른쪽으로 오름차순 정렬되게 넣기 때문에 이분탐색을 사용할 수 있는 겁니다!

 

 

아시겠나욥?

 

 

 

아. 중요한 것은

 

반드시 DP 배열이 가장 긴 증가하는 부분 순열의 순서에 맞지 않다는 것입니다!

즉, 내부 원소가 순서가 뒤바껴있을 수 있죠.

*** 이분탐색으로 원소를 바꾸기 때문에 차이가 있을 수 있다.

 

하지만, 전체 길이를 알 수 있다는 장점이 있기에 길이를 구하는 문제에서 사용하면 될 듯 합니다!

 

 

 

이상입니다.

궁금한 사항이나 도움이 되었다면 댓글 부탁드립니다.

 

 

감사합니다!

 

 

 

 

소스코드

---