LIS길이를 이분탐색으로 구해보자(python)

가장 긴 증가하는 부분수열(LIS)의 길이를 이분탐색을 이용해 구해보자

먼저 가장 긴 증가하는 부분 수열이 뭔지 이해해보자

 

수열: 숫자들의 나열
ex) [5,3,8,2]

 

부분수열: 수열안에서 몇몇 숫자들을 골라서 만든 새로운 수열 
ex) [5,8,3,2] => [5,8,2]

 

따라서 수열 [10, 20, 10, 30, 20, 50]이 있을때

따라서 가장 긴 증가하는 부분 수열은  [10, 20, 10, 30, 20, 50]이고 길이는 4이다

 

이분탐색을 이용한 풀이

주어진 수열의 각 원소를 순회하면서 이분탐색을 적용해나간다

따라서 시간복잡도는 O(nlogn) 이된다 

 

세부적인 이진탐색 과정은 아래와 같다

• 현재 원소를 이진 탐색을 통해 LIS 배열에 삽입할 위치를 찾는다 (LIS배열은 항상 정렬된 상태를 유지한다)
• 만약 현재 원소가 LIS 배열의 가장 큰 값보다 크다면, LIS 배열의 끝에 현재 원소를 추가한다
• 그렇지 않다면, 현재원소보다 큰 LIS 배열의 원소중 가장 작은값을 대체한다

 

최종적인 가장 긴 증가하는 부분 수열의 길이는 LIS 배열의 길이와 같다

 

---

 

예시를 들어본다

 

주어진 수열: [2, 9, 100, 3, 1, 5, 6, 4]

 

1. LIS배열 초기화: [2]

2. 순회하며 각 원소를 처리:

• 현재원소: 9
  
  • 업데이트된 LIS 배열: [2, 9]
• 현재원소: 100
  • 업데이트된 LIS 배열: [2, 9, 100]
• 현재원소: 3
  • 업데이트된 LIS 배열: [2, 3]
• 현재원소: 1
  • 업데이트된 LIS 배열: [1, 3]
• 현재원소: 5
  • 업데이트된 LIS 배열: [1, 3, 5]
• 현재원소: 6
  • 업데이트된 LIS 배열: [1, 3, 5, 6]
• 현재원소: 4
  • 업데이트된 LIS 배열: [1, 3, 4, 6]

가장 긴 증가하는 부분 수열의 길이 4

 

실제 가장 긴 증가하는 부분 수열은 [1, 3, 5, 6]이 아니라 [2, 3, 5, 6]이다

LIS배열이 실제 가장 긴 증가하는 부분 수열과 언제나 일치하지않음에 주의해야한다

 

그렇다면 왜 이방법으로 LIS의 길이를 찾을수 있는걸까

후보값 교체의 타당성이 있다는점이다

LIS배열에 [2, 9, 100] 이 있을때 3을 이분탐색으로 적절한 자리에 넣는다

그러면 LIS배열은 [2,3,100]이된다

 

1. 3은 기존에 있던 2보다 늦게나왔으며
2. 동시에 2보다 크다 

따라서 2-3은 이어질수있다

동시에 2-3-.... 으로 이어질수있는 새로운 루트의 가능성을 열어두었다

 

실제 LIS가 [2, 3, 100]이라는 말이 아니다

다시한번 말하지만 LIS배열이 실제 LIS배열과 다르다는것을 이해하는것이 중요하다

 

코드로 구현

N=int(input())
array=list(map(int,input().split()))

lis=[array[0]] # LIS배열

for i in array: # 모든 원소들을 대상으로 순회
    if lis[-1]<i: # 만약 LIS배열의 마지막 요소가 현재 원소보다 작다면
        lis.append(i)
    else: # 이분탐색 시작
        start=0
        end=len(lis)-1
        while start<end:
            mid=(start+end)//2
            if i>lis[mid]: #
                start=mid+1
            else:
                end=mid
        
        lis[start]=i
    
print(len(lis))