[Swift] 백준 가장 긴 증가하는 부분 수열(LIS), 최장 공통 부분 수열(LCS) 관련 문제풀이

LIS

1. 11053 (가장 긴 증가하는 부분 수열)

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

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

내 풀이

import Foundation
let n = Int(readLine()!)!
let arr = readLine()!.split(separator:" ").map { Int($0)! }
var dp = Array(repeating:1, count:n) // i번째 오기까지의 가장 긴 수열의 길이

for i in 1..<n {
  for j in 0..<i {
    if arr[i] > arr[j] { // 자기보다 더 작은 수 만날때마다 갱신
      dp[i] = max(dp[i], dp[j] + 1)
    }
  }
}

print(dp.max()!)

 

그림으로 원리 이해하기

 

DP[i] = arr[i]를 마지막 원소로 가지고 있을 때, 가장 긴 증가하는 부분 수열의 길이 로 정의하면

반복문을 돌면서 그 이전의 원소가 자기 자신보다 작은 값이 있을 때, 자기 자신이 마지막 원소여야 하므로 그 길이를 구해준다.

 

예를들어 현재 50을 돌고 있는 경우 dp[0]에 1을 더한 값(1+1)과 자기 자신을 비교했을 때 2가 더 크므로 2로 갱신하고,

20을 비교했을 때 dp[1]에 1을 더한 값(2+1)과 자기 자신(2)을 비교했을 때 3이 더 크므로 3으로 갱신하고,

 

(여기서 1을 더하는 이유는 dp는 자기 자신이 마지막 원소일 때 가장 긴 수열의 길이이므로, 자기 자신보다 작은 수까지의 가장 긴 수열의 길이에 1을 더하면 자기 자신을 포함한 수열의 길이가 되기 때문이다.)

 

이런식으로 비교했을 때 4가 가장 크므로 dp 배열의 max값을 구해주면 된다.

 

🚨 주의사항

주의할 내용으로는 나는 처음에 주어지는 수열이 무조건 처음부터 증가하는 수열인줄 알았는데 주어진 수열은 증가하는지 전혀 무관하게 주어지는 것 같다. (ex. 70, 30, 50, 60, 70, 0, 10)

그래서 처음부터 증가한다고 가정하고 dp의 값을 늘려주면 틀리므로 그 이전을 모두 순회하면서 나보다 작은값에 대해서만 비교하는 과정이 있어야한다.

 

2. 11055 (가장 큰 증가하는 부분 수열)

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

11055번: 가장 큰 증가하는 부분 수열

 

내 풀이

import Foundation

let n = Int(readLine()!)!
let arr = readLine()!.split(separator:" ").map { Int($0)! }
var dp = arr // i번째 오기까지의 가장 긴 수열의 길이

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

print(dp.max()!)

 

DP[i] = arr[i]가 마지막 원소일 때 i까지의 증가 수열의 합 이라고 정의하고,

위 문제와 같이 자기 자신보다 작은 수에 해당하는 DP값에 자기 자신을 더하며 최대값을 갱신시킨다.

 

3. 14002 (가장 긴 증가하는 부분 수열 출력하기)

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

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

 

내 풀이

import Foundation

let n = Int(readLine()!)!
let arr = readLine()!.split(separator:" ").map { Int($0)! }
var dp = Array(repeating:1, count:n) // i번째 오기까지의 가장 긴 수열의 길이

for i in 1..<n {
  for j in 0..<i {
    if arr[i] > arr[j] { // 자기보다 더 작은 수 만날때마다 갱신
      dp[i] = max(dp[i], dp[j] + 1)
    }
  }
}

var maxDp = dp.max()!
var maxIdx = dp.firstIndex(of:maxDp)!
var answer: [Int] = []

while maxIdx >= 0 {
    if dp[maxIdx] == maxDp {
        answer.append(arr[maxIdx])
        maxDp -= 1
    }
    maxIdx -= 1
}

print(answer.count)
print(answer.sorted().map { String($0) }.joined(separator:" "))

 

위에서 푼 문제들과 DP 테이블의 정의는 같고, 문제 풀이 원리도 비슷하다.

이제 문제에서 요구하는 배열을 만들 때가 중요한데, 가장 긴 수열의 길이와 이 때의 가장 마지막 원소의 인덱스를 구해 거기서부터 -1을 하며 거슬러 올라간다.

예를들어 array가 10, 20, 10, 30, 20, 50 이고 dp는 1, 2, 1, 3, 2, 4 라면

가장 긴 부분 수열의 길이는 4일것이고, 4에서부터 -1을 해가며 길이가 3, 2, 1, 일때를 만족하는 가장 마지막 원소를 추가해나간다.

 

LCS

1. 9251 (LCS)

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

9251번: LCS

설명 잘되어있는 블로그 링크 : https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

let str1 = ["0"] + readLine()!.map { $0 }
let str2 = ["0"] + readLine()!.map { $0 }
let n = str1.count
let m = str2.count

var dp = Array(repeating: Array(repeating: 0, count: n), count: m)

for i in 1..<m {
    for j in 1..<n {
        if str2[i] != str1[j] {   // 다르면 이전 값 중 최대값 가져오기
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        } else { // 같으면 + 1
            dp[i][j] = dp[i - 1][j - 1] + 1
        }
    }
}

print(dp[m - 1][n - 1])