[Swift 알고리즘] 백준 BOJ - 11722 가장 긴 감소하는 부분 수열

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 11722 가장 긴 감소하는 부분 수열" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

11722번: 가장 긴 감소하는 부분 수열

 

---

풀이

이번 문제는 DP 중 LIS 유형 문제입니다.

 

바로 직전 포스팅에서 Lower Bound라는 방법을 이용해 O(N^2)보다 더 좋은 O(N log N)을 배웠는데요.

Lower Bound와 똑같은 원리의 Upper Bound라는 방법도 있고 이 문제에서 사용할 수도 있습니다.

 

하지만 그건 가장 긴 감소하는 부분 수열2에서 사용해보기로 하고 이번 문제는 O(N^2)으로 해결해 보았습니다.

(+ 이럴수가... 가장 긴 감소하는 부분 수열2라는 문제는 없네요...! ㅠㅠ UpperBound를 이용한 코드도 추가했습니다.)

 

모든 number에 대하여 각 number가 맨 뒤에 올 수 있는지를 판단하고 뒤에 올 수 있다면 값을 1씩 증가 시킵니다.

모든 number를 판단한 후 가장 긴 값을 출력하면 됩니다.

 

---

전체 코드

O(N^2)

//11722 가장 긴 감소하는 부분 수열
import Foundation

let input = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }

var dp: [Int] = Array(repeating: 1, count: input)
for i in 0..<input {
    for j in 0..<i {
        if numbers[j] > numbers[i] && dp[i] < dp[j]+1 {
            dp[i] = dp[j] + 1
        }
    }
}

print(dp.max()!)

 

O(N log N)

//11722 가장 긴 감소하는 부분 수열
import Foundation

func upperBound(find: Int, numbers: [Int]) -> Int {
    var start: Int = 0
    var end: Int = numbers.count - 1
    var mid: Int = 0
    
    while start < end {
        mid = (start + end) / 2
        if find < numbers[mid] {
            start = mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}

let input = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }

var dp: [Int] = []
for number in numbers {
    if dp.isEmpty {
        dp.append(number)
        continue
    }
    
    if number < dp.last! {
        dp.append(number)
    } else {
        let index = upperBound(find: number, numbers: dp)
        dp[index] = number
    }
}

print(dp.count)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.