[99클럽 코테 스터디 27일차 TIL] 가장 긴 감소하는 부분 수열 - 백준 11722

동적 계획법은 아직 미숙하다.

 

https://www.acmicpc.net/problem/11722

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에
가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

[입력]
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

[출력]
첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

풀이 접근

DP Table을 이용한다.

var dp = Array(repeating: 1, count: nums.count)

먼저 각 인덱스마다 최소 길이를 1로 설정한다.

그리고 1부터 순회하면서, dp[i] 에 nums[i]로 끝나는 가장 긴 감소하는 수열의 길이를 저장한다.

for i in 1..<nums.count {
    for j in 0..<i {
        if nums[i] < nums[j] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}

다만 이러한 방식은 O(n)의 시간 복잡도를 갖는다.

 

O(n*logn)으로도 해결이 가능한데, 이진 탐색을 활용하면된다.

array 변수를 하나 저정하고, 이 배열의 마지막 요소는 항상 탐색 범위의 최소 값을 갖게 된다.

var array: [Int] = []

이후 원래 요소들을 탐색하면서 array를 갱신한다.

이때 array는 실제 가장 긴 감소(혹은 증가)하는 수열이 아니고 단순히 그 길이만을 파악하기 위한 배열이다.

for n in nums {
    if array.isEmpty || array.last! > n {
        array.append(n)
    } else {
        var left = 0
        var right = array.count - 1
        while left < right {
            let mid = (left + right) / 2
            if array[mid] > n {
                left = mid + 1
            } else {
                right = mid
            }
        }
        array[left] = n
    }
}

따라서 array 자체가 가장 긴 감소(혹은 증가)하는 수열을 의미하지는 않는다.

최종 코드 O(n) - Swift

_ = readLine()
let nums = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var dp = Array(repeating: 1, count: nums.count)
for i in 1..<nums.count {
    for j in 0..<i {
        if nums[i] < nums[j] {
            dp[i] = max(dp[i], dp[j] + 1)
        }
    }
}
print(dp.max()!)

최종 코드 O(n*logn) - Swift

_ = readLine()
let nums = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var array: [Int] = []
for n in nums {
    if array.isEmpty || array.last! > n {
        array.append(n)
    } else {
        var left = 0
        var right = array.count - 1
        while left < right {
            let mid = (left + right) / 2
            if array[mid] > n {
                left = mid + 1
            } else {
                right = mid
            }
        }
        array[left] = n
    }
}
print(array.count)

Conclusion

사실 가장 긴 증가하는 부분 수열을 풀어본 적이 있어서 비교 연산만 반대로 바꿔서 해결했다.