[Swift] 최장 증가 부분 수열 구하기(LIS, 백준 12015)

LIS - Longest Increasing Subsequence
최장 증가 부분수열을 구하는 알고리즘

백준 - 12015 가장 긴 증가하는 부분 수열 2

해당 문제는 단순하게 완전탐색으로 풀면 단순하게 풀리는 문제이다. 하지만 문제점은 역시나 시간 복잡도...
완전 탐색으로 풀게되면 시간 복잡도는 O(n^2)으로 매우매우매우 느린 편이다.

이 방식의 문제를 더 효율적으로 푸는 방법이 두 가지 있는데 하나는 dp를 이용한 방식이고 하나는 이분 탐색을 이용한 방식이다. 나는 여기서 이분 탐색을 이용한 방식을 다뤄보려 한다.

이분 탐색을 이용한 방식의 시간 복잡도는 O(nlogn)이다. 이제 어떤 방식으로 최대 증가 부분수열을 찾는지를 알아보자.
(정확히는 이 방식은 부분수열의 크기만을 찾아내는 알고리즘이다. )

개괄적인 흐름은 다음과 같다.

주어진 배열을 순회한다.( 시간복잡도 - O(n))
순회하면서 배열의 요소를 부분 배열에 추가한다.
부분 배열에 수를 추가할 때 추가할 위치를 이분탐색으로 탐색한다.(O(logn))
추가할 위치에 있는 숫자랑 수를 교체한다. (부분 배열에 있는 숫자들보다 클 경우 마지막 위치에 추가)
순회가 끝나면 최장 부분배열의 크기를 알 수 있다.

예시 진행 방식은 다음과 같다

이 방식의 가장 큰 특징은 부분 배열에 가장 큰 수를 추가할 때가 아니더라도 부분 배열의 크기는 유지하면서 최적화를 이룬다는 것이다.
실제로 이 방식을 보면 기존 부분 배열에 가장 큰 수가 추가될 때만 길이가 증가하고 그 이외의 경우엔 최대한 작은 수로 부분 배열의 수를 교체해 가면서 최적화를 이루고 있다.

자 그럼 알고리즘은 어떻게 작성해야할까?

https://www.acmicpc.net/problem/12015
백준 12015 문제를 기준으로 한 번 작성해보겠다.

이분탐색을 구현한다.

func binarySearch(_ arr: [Int], _ target: Int) -> Int {
 var leftNum: Int = 0
 var rightNum: Int = arr.count - 1

 while leftNum <= rightNum {
     let midNum = (left + right) / 2
     if target <= arr[midNum] {
         rightNum = midNum - 1
     } else {
         leftNum = midNum + 1
     }
 }

 return leftNum
}

이분 탐색을 이용한 방식이기 때문에 간단하게 숫자가 추가될 위치를 반환해주는 이분탐색 함수를 생성한다.

주어진 배열을 순회하면서 부분 배열을 생성할 함수 구현

func lisSearch(nums: [Int]) -> Int {
 var lis: [Int] = []

 for num in nums {
     let pos = binarySearch(lis, num)

     if pos == lis.count {
         lis.append(num)
     } else {
         lis[pos] = num // 기존 값을 더 작은 수로 변환 -> 최적화
     }
 }

 return lis.count
}

1) lis: 부분 배열 상태를 저장할 변수
2) pos: 현재 숫자가 lis 배열에서 어떤 위치에 추가될 수 있는지 표시할 배열 index
3) 만약 pos 변수가 lis의 크기와 같다면(lis에 있는 다른 숫자들 보다 크다면) 그대로 배열에 append 해줌
4) 그 외엔 lis에서 pos위치에 있는 수와 교체함(lis[pos] = num)
5) 순회가 끝나면 lis.count를 반환함

티스토리툴바