[알고리즘] LIS 최장 증가 부분 수열 파해치기!! with Swift

 

 

• Todo : LIS 최장 증가 부분 수열 파해치기

• LIS개념을 마주한 순간..
• LIS(Longest Increasing Subsequence)란?
• dp를 통해 LIS 길이를 구하는 방법
• 이분 탐색을 통해 LIS길이를 구하는 방법
• 이분탐색 또는 dp를 활용한 문제

 

LIS개념을 마주한 순간..

 

관련 문제 = 14002: 가장 긴 증가하는 부분수열4 ( 포스트 )

 

dynamic programming문제를 한참 공부 했었을 때(지금도 공부중입니다.ㅏ..) 전깃줄 문제를  풀다 LIS라는 개념을 만나게 되었습니다.

당시에 전깃줄 문제를 풀 때 모든 경우의 수를 파악해 가며 완벽히 구현했다고 생각한 코드를 구현했을 때 문제를 풀 수 없었습니다.

그리고 제가 생각한 코드로는 도저히 해결 할 수 없는 반례들이 나타났습니다. "아직 실력이 부족해서 못 푼 문제일거야" 다음에 풀려던 찰나 혹시 다른 분들의 코드가 궁금해 인터넷을 통해 검색을 했는데 그때!! LIS개념을 마주하게 됬습니다.

(한쪽 전봇대를 sort했을 때 다른 전봇대에서 꼬이지 않는 전깃줄을 파악하는 방법은 LIS 길이를 구하는 방법과 같다.....)

LIS(Longest Increasing Subsequence)란?

 

최장 증가 부분 수열 LIS는 예를 들어 수열[3,7,5,2,6,1,4]이 주어졌을 때

[3,7], [2,6],[1,4] 처럼 연속적으로 증가하는 게 아니라 일부 원소들을 제거하고 남은 수열이 Longest Increasing 가장 증가하는 긴 수열일 때를 LIS라고 합니다.

그림1

그림1 처럼 7, 2, 1, 4 원소를 제거했을 때 남은 3, 5, 6 부분 수열을 LIS라고 합니다. 제거한다는 말은 반대로 수열에서 일부 원소 3,5,6을 선택했을 때로 말할 수 있습니다.

 

그렇다면 주어진 수열에서 오름차순으로 증가하는 가장 긴 부분 수열의 길이는 어떤 방법으로 찾을 수 있을까요?

---

• dp를 사용해서 LIS 길이를 구하는 방법이 있습니다.

dp를 사용하게 될 경우 O(N^2) 시간복잡도를 갖습니다. 

• 이분 탐색을 통해 LIS 길이를 구하는 방법이 있습니다.

말 그대로 탐색이기 때문에 이분 탐색의 시간 복잡도는 O(logn)입니다. 그리도 수열의 모든 원소를 훑는 방법은 for in구문을 사용한 O(N)이기에

O(NlogN)의 시간 복잡도를 갖습니다.

dp를 사용해 LIS 길이를 구하는 방법

 

var list = [3,7,5,2,6,1,4]
var dp = Array(repeating: 0, count: n)
for i in 0..<n
{
    dp[i] = 1
    for j in 0..<i
    {
        if list[j] < list[i] && dp[j]+1 > dp[i]
        {
            dp[i] = dp[j] + 1
        }
    }
}

 

수열 var list = [3,7,5,2,6,1,4] 가 주어졌을 때

수열의 크기만큼 dp를 생성합니다. 이제부터 수열을 list라고 부르겠습니다.

var dp = Array(repeating: 0 , count : list.count)

이제 이 dp 배열에는 특정 원소일 때 LIS 길이(== 최대를 갖는 증가하는 부분 수열 개수)가 담길 것입니다.

이 그림에서 빨간색 선을 보시면 list 에서 만들 수 있는 Suqsequence(부분 수열)은

(3) (3,7) (3,5) (3,5,6) (5,6) ...

 

첫번째 포문에서 모든 원소들을 탐색하는데,

특정원소 예를들어 i == 4, list value = 6일때

list의 index 0 ~ 3까지 포문을 돌며 list[4]보다 작은 값(3,5,2가 있네요)이면서!! index 0~3 중 증가하는 수열의 최대 길이(dp[0], dp[1], dp[2], dp[3])에서 + 1을 했을 때(list[i]를 넣었을 때) 원래 dp[i]보다 크다면 이전에 LIS길이에 +1을 한 값을 LIS 길이로 저장합다.

 

dp[4]는 dp[2] + 1(value = 6)이 됩니다.

dp[2]는 dp[0] + 1(value=5)이 됩니다.

dp[0]는 자기자신을 최장 증가 부분수열로 dp[0] = 1(value = 3)이 됩니다.

이렇게 i == 4일 때 dp[4]는 3,5,6 = 3을 LIS길이로 갖습니다.

첫번재 포문으로 특정 원소를 탐색할 때

이전 원소들 중 첫번째 포문의 특정 원소보다 작은 값들 중에서 가장 긴 길이를 저장해 가는 방식입니다.

따라서 시간 복잡도는 O(N^2)가 발생합니다.

 

이렇게 된다면 dp에는 list의 특정 index 당 LIS 길이를 갖는 값들이 저장됩니다.

출력은 이렇게!!

var ans = 0
for i in 0..<n
{
    if ans < dp[i]
    {
        ans = dp[i]
    }
}
print(ans)

 

하지만 문제에서는 O(NlogN)을 갖는 풀이를 원하는 문제가 있기 때문에 이분 탐색을 활용한 LIS 구하는 방법도 알아야 합니다.

이분 탐색을 활용해 LIS길이를 구하는 방법

 

이 방법은 정말 신기한데 위에서 풀이 dp와는 다르게 포문을 2개 중첩으로 사용하지 않고

한개의 포문으로 LIS탐색을 끝냅니다.

하지만 이 포문 과정에서 특정 조건이 맞지 않을 경우 binarySearch(target: seq:)를 사용합니다.

그래서 시간 복잡도는 dp보다 빠릅니다. 

---

마찬가지로

수열 var list = [3,7,5,2,6,1,4] 가 주어졌을 때

수열의 크기만큼 dp를 생성합니다. 이제부터 수열을 list라고 부르겠습니다.

 

LIS의 길이를 구하는 것이 초점이자 포인트입니다.

새로운 배열을 만들어 배열에 있는 마지막 원소보다 값이 클 경우에는 list의 원소를 그대로 새로운 배열에 삽입하고

그게 아닐 경우 LIS길이가 보장 되는 한(새로운 배열은 증가하는 수열들이 담겨있는 것)에서 자신과 같거나 자신보다 큰 원소를 교체함으로 LIS를 유지해 나가는 방식입니다.

 

 위에서 i == 4일때 예를 들었을 때를 가정한다면

이분탐색을 통한LIS와 dp를 했을 때 차이점은 dp[4]는 3.5.6 의 원소 길이 가 들어가지만

새로운 배열에 저장된 LIS는 3.5.6이 맞을수도 아닐수도 있습니다.(거의 아님)

 

이분 탐색을 통한 LIS목적은 증가하는 부분 수열 최대 개수를 구하는 것에 초점을 맞췄기 때문입니다.

---

위에 이미지 처럼 seq에는 우선 list[0]을 넣어주고 포문으로 seq.last원소보다 큰 list[i]면 넣어주고 그게 아닐 경우에는 seq에 자신보다 큰 원소를 찾아 교체해 가는 방식으로 이분탐색을 진행합니다.

결과적으로 seq에는 LIS가 저장되지는 않지만 LIS길이는 저장됩니다!!

 

import Foundation
func binarySearch(_ target: Int, _ seq : inout [Int])
{
    var left = 0, right = seq.count - 1
    while left < right
    {
        let mid = (left+right)/2
        if seq[mid] < target
        {
            left = mid + 1
        }
        else
        {
            right = mid
        }
    }
    seq[right] = target
}
func LIS()
{
    let n    = Int(readLine()!)!
    var list = [Int]()
    for _ in 0..<n
    {
        list.append(Int(readLine()!)!)
    }
    var seq  = [list[0]]
    for i in 1..<n
    {
        if seq.last! < list[i]
        {
            seq.append(list[i])
        }
        else
        {
            binarySearch(list[i], &seq)
        }
    }
    print(seq.count)
}
LIS()

이분 탐색 또는 dp를 활용한 문제

 

 

반도체 설계 , 가장 긴 증가하는 부분 수열2 , 전깃줄 , 줄 세우기 등의 문제를 풀 수있습니다!!

 

LIS 문제 관련 PS 일지 ( 목록 링크 )