[Swift Algorithm Note] 최장 증가 부분 수열 2 (feat. BS)

저번에는 DP로 최장 증가 부분 수열 (LIS)를 구하는 방법을 알아보았는데,

오늘은 DP보다 훨씬 시간복잡도가 좋은 이분 탐색 (BS)로 구하는 방법을 정리해보려고 한다.

두 가지 방법의 차이점도 알아보고, 이분탐색으로 LIS를 구하는 알고리즘도 구현해보자.

(LIS에 대한 설명, 그리고 DP로 LIS 구하는 알고리즘이 궁금하신분들은 요기👇를 참고해주세요!)

2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP)

[Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP)

 

📎 이분탐색으로 구하는 LIS

LIS를 DP가 아닌 이분탐색으로 구했을 때의 시간복잡도 차이를 알아보고,

이분탐색으로 구현하는 방법에 대해 알아보자.

 

📌 DP와의 시간복잡도 차이

앞서 DP로 LIS를 구하는 알고리즘을 정리한 포스팅에서는 언급하지 않았지만,

DP는 수열의 모든 요소마다 이전 수들을 비교해주어야하므로 시간 복잡도가 O(N^2)이 된다.

따라서 N이 아주 커진다면 급수적으로 커지는 시간 복잡도를 경험할 수 있다,,

입력이 100만개 정도만 되더라도 실행 시간이 10초 이상 걸린다고 한다.

 

하지만 이분 탐색은 O(log n)의 시간 복잡도를 가지므로,

BS를 이용해 구해준다면 LIS를 구하는 시간 복잡도를 O(nlog n)으로 개선할 수 있다.

 

📌 이분탐색으로 구현하기

이분탐색을 이용하여 LIS를 구하는 가장 기본적인 형태를 예제로 작성해보았다.

import Foundation

let permu = [1, 3, 2, 5, 4, 6]
var lis = [Int]()

func BinarySearch(_ start: Int, _ end: Int, _ value: Int) -> Int {
    var s = start // lis의 시작 인덱스
    var e = end // lis의 맨 끝 인덱스
    var m = 0 // s와 m의 중간 인덱스
    
    while s < e {
        m = (s + e) / 2
        if value <= lis[m] { e = m }
        else { s = m + 1 }
    }
    
    return s
}

for i in 0..<permu.count {
    if lis.isEmpty { lis.append(permu[i]) }
    else if lis.last! < permu[i] { lis.append(permu[i]) }
    else { lis[BinarySearch(0, lis.count-1, permu[i])] = permu[i] }
}

print(lis.count)

변수 설명

• permu : 주어진 수열
• lis : 최장 증가 부분 수열을 저장하기 위한 배열

코드 설명

• 아래쪽의 for문을 보면, 순서대로 permu[i]를 넣을 lis의 적절한 자리를 결정하는 역할을 한다.
  if, lis 배열이 비어있을 경우 lis의 마지막에 permu[i]를 추가하도록 해주었다.
  else if, lis의 마지막 요소가 permu[i]보다 작을 경우 마찬가지로 lis 마지막에 permu[i]를 추가했다.
  else, lis 배열이 비어있지도 않고 lis 배열의 마지막 요소가 permu[i]보다 클 경우
  BinarySearch 함수를 사용하여 적절한 인덱스를 찾고, lis의 해당하는 위치 요소를 permu[i]로 갱신했다.
• BinarySearch 함수는 start, end, value를 인자로 필요로 하는데,
  각각 lis의 시작 인덱스, 끝 인덱스, 그리고 permu[i] 값을 의미한다.
•  start와 end는 각각 s와 e 변수에 저장하고, m이라는 변수를 0으로 초기화한다.
  m 변수는 이분탐색을 하며 계속 업데이트 될 s와 e의 중간 값을 저장할 용도이다.
• while 반복을 통해 이분탐색을 하는데, s가 e보다 작을 동안 반복한다.
  s와 e를 더한 후 2로 나누어 중간 값을 찾아 m 초기화, value가 lis[m]보다 작거나 같을 경우
  e를 m으로 초기화했고, value가 클 경우에는 s를 m+1로 초기화했다.

---

👀 정리

이분탐색을 이용하여 LIS를 구하는 알고리즘을 이해하고, 사용 방법을 공부했다.

 

이전에도 문제를 풀면서 이분탐색에 대하여 공부한 적은 있지만,어려운 문제가 닥쳤을 때는 이분탐색을 어떤 식으로 적용해야할지 몰라응용하기가 어려운 것 같다. 연습이 더 필요할 것 같다.