12일차에서 DP로 풀었던 문제를 이분탐색을 사용해서 시간복잡도를 O(n^2) 에서 O(nlogn)으로 줄어보았다.

문제 : 가장 긴 증가하는 부분 수열
GitHub: 가장 긴 증가하는 부분 수열 구현 (코드보기)

그 전에는 DP를 사용하여 풀었지만, 지금 요구하는 답은 가장 긴 수열의 길이만을 요구했기 때문에, 이진탐색을 이용하여 답을 찾을 수 있다.

아래 예시를 들어보겠다.

Array = [10,20,30,40,10,12,14,16,18]

Array라는 리스트가 하나 있다.

이거를 index 3까지 Stack에 오름차순으로 쌓아보겠다.

Stack = [10,20,30,40]

여기서 다음 10을 만나게되면, 뒤에 추가되지 않고 Stack의 index 0 의 위치에 냅다 넣는 것이다. 이 때 10이 들어갈 index 0 위치를 찾을 때, 이진탐색을 사용하는 것이다.

다음 12를 만나게 되면, 10 <= X <= 40의 값이기 때문에 이진탐색으로 index 1의 들어갈 위치를 찾아내어 집어 넣습니다. 그렇게 되면 현재 Stack 배열은 아래와 같습니다.

Stack = [10,12,30,40]

그리고 14를 만나게 되면, 12 <= X <= 40 의 값이기 때문에 이진탐색으로 index 2의 들어갈 위치를 찾아냈고 집어 넣습니다.

Stack = [10,12,14,40]

그리고 16을 만나게 되면, 14 <= X <= 40 의 값이기 때문에 이진탐색으로 들어갈 index 3의 위치를 찾아냈고 집어넣습니다.

Stack = [10,12,14,16]

그리고 18을 만나게 되면, 16보다 크고, 가장 길었던 4보다 커질 수 있는 상황이기 때문에 16 값 뒤에 이어 붙게 됩니다.

Stack = [10,12,14,16,18]

Stack에 들어갈 때 Stack 배열은 항상 오름차순 정렬된 배열이기 때문에, 이진탐색을 사용할 수 있었고, 그로 인하여 DP를 사용했을 때보다 더 빠른 시간복잡도(NlogN)로 줄일 수 있었다.

이렇게 문제 이해를 잘 하게 되면 더 나은 풀이 방법을 유추할 수 있게 되고, 원하는 정답이 무엇인지를 잘 파악하면 코딩테스트를 풀 때 더 나은 답안을 생각 할 수 있을 것 같다.

🎯 TO DO

• 이진 탐색의 조건에 대해서 좀 더 공부하고, 이분탐색이란? 에 내용을 추가하기