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

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

오늘은 "11053 가장 긴 증가하는 부분 수열" 문제를 풀었습니다.

 

---

Github

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

문제 링크

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

---

풀이

이번 문제는 DP를 이용하는 문제입니다.
오늘 푼 가장 긴 증가하는 부분 수열 문제는 LIS(Longest Increasing Subsequence)라는 DP 문제의 유명한 유형입니다.
LIS 연습 문제 1정도로 생각하면 될 것 같아요.

처음 풀면 낯선 풀이로 당황스러울 수 있는데요. (저도 그랬음)
꽤나 개수가 많아 연습하긴 좋습니다.

첫 번째 연습 문제인 만큼 시간 복잡도에 너그러운 편인데요. O(N^2) 으로 풀었습니다.
index를 하나씩 이동하면서 해당 인덱스의 숫자를 뒤에 붙일 수 있는 가장 긴 부분 수열을 찾습니다.
그 중 max 값을 출력하면 답이 됩니다.

과거의 부분 수열들 중 가장 긴 부분 수열을 찾는 것이므로 DP로 해결할 수 있는 것이지요.

참고로 나무 위키가 생각보다 너무 자세해서 놀랐습니다.
더 다양한 예시를 보고 싶으시다면 한 번 방문해 보세요.
https://namu.wiki/w/최장%20증가%20부분%20수열#toc

---

전체 코드

//11053 가장 긴 증가하는 부분 수열
import Foundation

let input = Int(readLine()!)!
let numbers: [Int] = 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[i] > numbers[j] && dp[i] < dp[j]+1 {
            dp[i] = dp[j] + 1
        }
    }
}

print(dp.max()!)

---

아직은 초보 개발자입니다.
더 효율적인 코드 훈수 환영합니다!
공감과 댓글 부탁드립니다.

Swift, Swift 알고리즘, 스위프트, 알고리즘, 백준, BOJ, 11053, 가장 긴 증가하는 부분 수열