[백준/Swift] 14002: 가장 긴 증가하는 부분 수열4 파해치기 | PS일지.

 

문제

14002번: 가장 긴 증가하는 부분 수열 4

간단한 문제 요약

수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하시오!

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

고려해야 할 사항

• 2차원 dp를 활용한 LIS는 단순 길이 정보를 dp에 저장합니다. 따라서 역추적을 통해 가장 큰 길이부터 이에 관한 값을 얻어야 합니다.

문제 풀이

제가 아는 한에서 두 가지 풀이법이 존재합니다. 첫번째로는 O(n^2) 두번째는 O(nlogn)풀이입니다. (아직 세그먼트 트리는 공부를 안해봐서,,ㅠ) 가장 긴 증가하는 부분 수열은 동적계획법 중 LIS알고리즘을 사용하면 쉽게 풀 수 있는 것 같습니다. 

case 1: 이중 포문 사용

첫번째는 이중 포문을 통해 dp에 긴 수열의 누적 길이를 저장해 가는 방법입니다. 초기 dp table은 1로 초기화 됩니다. 그 이유는 각각의 숫자는 최소 1자리 이상 증가하는 부분 수열이 될 수 있기 때문입니다.

func lis() {
    (1..<n).map{
        for j in 0..<$0 where list[$0] > list[j] {
            dp[$0] = max(dp[$0],dp[j]+1)
        }
    }
}

list에 수열의 정보 [10,20,10,30,20,50] 이 담겼을 때

첫 루프(map)로 두번째 index 부터 마지막 index까지 탐색을 합니다.

두번째 루프로 첫 index부터 map의 index 전까지 탐색을 합니다.

 

 

if 조건을 where 키워드로 선언했습니다. (where 키워드 개념 정리 관련 포스트 알면 편합니다!!)

 

map 안에 있는 포문의 역할은 map의 특정 index가 그 전까지. 처음부터 map의 특정 index 전까지 위치한 원소들 중에서 얼마나 긴지를 dp에 저장해 나가는 것입니다. 근데 dp[$0]에는 max(dp[$0] or dp[j] + 1) 둘 중 하나의 큰 값을 비교합니다.

 

그 이유는

10 35 10 20 30 40 이 수열에서 map의 $0 == 5번째 일 때를 생각해야 합니다.

 

for j in 0..<5 where list[5] > list[j] { ... }인 경우에

j == 0일 때

list[j] = 10. 그리고 list[5]가 더 크기에

dp[5] = 2가 저장됩니다.

 

j== 1일 때 list[5] > list[1] == 40 > 35 이므로

dp[1] == 2.

dp[5] = 3이 저장됩니다. ( 10, 35, 40. LIS길이 3)

 

그리고 j == 2일 때 list[2] = 10. target인 40이 더 큽니다.

dp[5] 현재 LIS 값3. dp[2] + 1 == 2. 의 경우 중 선택을 해야 합니다. 당연히 큰 것이 dp에 저장되야 합니다. 

dp[5] = max(dp[5] , dp[2] + 1) 에서 dp[5]를 선택하게 됩니다.

 

그리고 j ==4일 때 dp[j] == (10, 20, 30의 길이 3이 담겨 있습니다.)

list[5] > list[4]이므로

dp[5] = max(dp[5], dp[4] + 1) // 1을 하는 이유는 dp[4]는 30일 때 가장 긴 증가하는 부분 수열의 기록 10, 20, 30의 길이이기 때문이고 현재 탐색중인 $0==5는 40. list[j(==4)]의 30보다 크기 때문입니다. 한 개 더한다는 것은 큰 원소가 한 개 추가된다는 것입니다.

dp[5] = max(3,4) = 4가 담깁니다.

 

그리고 중요한 것은 backtracking입니다. dp 테이블은 단순히 특정 원소를 기준으로 해당 원소 전까지 원소들 중에서 몇 번째로 큰 지 순위를 저장만 합니다.

 

10 35 10 20 30 40 이 수열에서 dp table의 최종 상태는

1

2

1

2

3

4

이렇게 특정 시점에서 가장 긴 정보만 담고 있습니다. 하지만 문제에선 증가하는 부분 수열 최장 길이 + 그 시점에 각 원소 또한 출력해야 합니다.

 

이때 중요한 것은 답이 여러 개일 수 있다는 것입니다. list index (0,1,4,5) or (2,3,4,5) 그리고 backtracking을 사용할 경우에

dp에 저장된 가장 큰 증가하는길이 4를 기준으로!!!!

역으로 dp.count - 1 ~> 0까지 가장 긴 길이(1일때 까지) 추출하면 

4 (index=5)

3 (index=4)

2 (index=3)

1 (index=2)

0 x. 수열의 모든 글자는 최소 증가 길이 1입니다. 

즉 index 5,4,3,2의 정보를 얻을 수있고 이는 거꾸로 다시 출력을 하면 가장 긴 증가하는 부분 수열 정보를 획득 할 수 있게 됩니다.

코드

//MARK: - Properties
let n = Int(readLine()!)!
let list = readLine()!.split{$0==" "}.map{Int(String($0))!}
var dp = Array(repeating: 1, count: n+1)
var res = [Int]()

//MARK: - Helpers
func lis() {
    (1..<n).map{
        for j in 0..<$0 where list[$0] > list[j] {
            dp[$0] = max(dp[$0],dp[j]+1)
        }
    }
}

func backtracking() {
    var length = dp.max()!
    for i in stride(from: n-1, through: 0, by: -1) where dp[i] == length {
        res.append(list[i])
        length-=1
    }
}
func solution() {
    lis()
    backtracking()
    print(dp.max()!)
    print(res.reversed().map{String($0)}.joined(separator:" "))
}

solution()

case 2: 이분 탐색 사용

저는 원래 LIS를 이분 탐색으로 풀었습니다. O(nlogn)인 효율성에다 이분 탐색만 구현하면 되기 때문입니다. 이 문제를 풀 때 이분 탐색을 통해 풀때 약간 버거웠습니다. 이분 탐색에 의해 선정된 LIS 배열의 길이는 결국 가장 긴 증가하는 부분 수열의 count가 됩니다. 한 가지 고민은 그 안 원소들은 이분 탐색에 의해 편의상 작은 수로 교체된다는 것입니다. ( LIS 개념 정리 관련 포스트 )

 

하지만 장점은 이중 포문O(N^2)을 사용하지 않고 포문을 한 개 + 이분 탐색을 사용O(nlogn)한다는 점입니다. 

 

backtracking의 개념은 동일하게 위의 경우와 마찬가지로 사용됩니다. 

 

func binarySearch(_ seq: inout [Int], _ target: Int) -> Int {
    var left = 0, right = seq.count - 1
    while left < right {
        let mid = (left+right)/2
        if target > seq[mid] {
            left = mid + 1
        }else {
            right = mid
        }
    }
    seq[right] = target
    return right
}

이분 탐색을 구현하기만 한다면

var seq = [list[0]]
var dp = Array(repeating: 1, count: n)
for i in 1..<n {
    if list[i] > seq.last! {
        seq.append(list[i])
        dp[i] = seq.count
    }else {
        let idx = binarySearch(&seq, list[i])
        dp[i] = idx + 1
    }
}
backtracking(dp: dp)
print(dp.max()!)
print(res.reversed().map{String($0)}.joined(separator:" "))

dp에는 위와 마찬가지로 최장 증가 길이가 기록됩니다.