문제 유형 중, DP의 추천문제들을 풀어보려고 합니다. (Dynamic Programming 2)
DP1과 DP2 중 DP2-1부분 입니다. (DP2-2은 여기서 확인할 수 있습니다.)
추천문제 번호 모음은 여기서 확인할 수 있습니다.
문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.05.06업데이트
22.05.12 업데이트
22.05.13 업데이트
22.05.16 업데이트
22.05.21 업데이트
22.05.23 업데이트
22.05.25 업데이트
22.05.26 업데이트
22.05.29 업데이트
22.05.31 업데이트
22.06.01 업데이트
22.06.02 업데이트
22.06.03 업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
https://developer-p.tistory.com/201
DP(1-1) 문제 풀이 모음 | 백준 Swift 2748번, 11051번, 2839번, 1010번, 9655번, 17626번, 1463번, 9095번, 15988번,
문제 유형 중, DP의 추천문제들을 풀어보려고 합니다. (Dynamic Programming 1) DP1과 DP2 중 DP1부터 풀어나가겠습니다. (DP1의 문제양이 많아, DP1-1과 DP1-2로 나눕니다.) 추천문제 번호 모음은 여기서 확인
developer-p.tistory.com
https://developer-p.tistory.com/203
DP(1-2) 문제 풀이 모음 | 백준 Swift 2294번, 11660번, 21317번, 22869번, 1106번, 2293번
백준 Swift 2293번 Eng 백준 Swift 2293번 {"mean":[" swift 미국∙영국[swɪft] (일진행 등이) 신속한[재빠른] (움직임이) 빠른[날랜] 칼새 "," 번 (횟수, 차례, 경우) time, occasion; (시도) try (번호) number..
developer-p.tistory.com
백준 Swift 15724번
문제 유형 : DP(재귀, 반복문)
- 비슷한 문제를 풀었어서 어렵지 않았다. 백준 11660번을 먼저 풀고 오면 쉽다. (풀이도 거의 같다.)
순서 1. 2차원배열의 누적합을 구해 dp배열에 넣는다.
순서 2. 그다음 원하는 직사각형의 범위에 해당하는 값을 구하면 된다.
순서2가 이해가 안된다면 아래 그림을 봐보자.
예를 들어 (2,2) ~ (3,4)를 구해야 한다. 누적합dp배열을 이용해 어떻게 식을 짜면 될까?
D - A - B + C일 것이다.
즉, 전체 D에서 A와 B를 빼주고, 중복으로 뺀 C를 더해주면 흰색부분(구간합)을 구할 수 있다.
이를 식으로 쓰면 dp[3][4] - dp[3][1] - dp[1][4] + dp[1][1]이다.
난이도 : 실버1
반복문(시간 개선 - 2차원 배열 누적합)
// MARK: - 15724번(DP - 반복문 : 시간 개선(2차원배열 누적합))
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var arr: [[Int]] = Array(repeating: [], count: N + 1)
for i in 1...N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
arr[i] = [0] + input
}
arr[0] = Array(repeating: 0, count: M + 1)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: M + 1), count: N + 1)
for i in 1...N {
for j in 1...M {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j]
}
}
let K = Int(readLine()!)!
for _ in 0..<K {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])
let sum: Int = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
print(sum)
}반복문(맞긴 맞으나 오래걸리는 코드 - 1차원배열의 누적합을 누적해서 더함.)
처음 고민.
맞긴 맞았지만 이렇게 풀면 시간이 오래걸린다.
// MARK: - 15724번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var arr: [[Int]] = Array(repeating: [], count: N + 1)
for i in 1...N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
arr[i] = [0] + input
}
arr[0] = Array(repeating: 0, count: M + 1)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: M + 1), count: N + 1)
for i in 1...N {
for j in 1...M {
dp[i][j] = dp[i][j - 1] + arr[i][j]
}
}
let K = Int(readLine()!)!
for _ in 0..<K {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])
var sum: Int = 0
for x in x1...x2 {
sum += dp[x][y2] - dp[x][y1 - 1]
}
print(sum)
}백준 Swift 9084번
문제 유형 : DP(재귀, 반복문)
백준 2293번 문제와 거의 유사하다. (백준 2293번 Swift 풀이 : https://developer-p.tistory.com/203)
처음엔 2차원 배열로 풀고 싶어서 그렇게 작성했는데 50%에서 계속 안됐다.
질문도 남겨놨는데, 추후에 답변이 달린다면 다시 시도해봐야겠다.(https://www.acmicpc.net/board/view/89943)
dp[0] 값을 1로 선언해주는게 핵심이다.
그 다음 안쪽 for문을 돌릴 때 coin...M이 아니라 굳이 stride(from: coin, through: M, by: 1)로 한 게 눈에 띌 것이다.
swift에서 for문을 돌릴 때 lowerBound가 upperBound보다 크게 되면 에러가 발생한다. 아래 이미지 처럼 말이다.
for i in 8...2 {
print(i)
}
하지만 stride를 쓰면 Range 에러 나는 걸 방지할 수 있다. 범위가 안맞게 되면 에러가 발생하는게 아니라 패스하게 된다.
문제에서 주어지는 coin이, 만들어야 하는 금액M보다 큰 경우를 방지하기 위해 이렇게 작성했다.
stride를 안쓰고 작성하면 런타임 에러가 발생한다.
난이도 : 골드5
반례
1
1
10000
9999
반복문
// MARK: - 9084번(DP - 반복문)
let T = Int(readLine()!)!
for _ in 0..<T {
let _ = Int(readLine()!)! // N
let coins: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
let M = Int(readLine()!)!
var dp: [Int] = [1] + Array(repeating: 0, count: M)
for coin in coins {
for i in stride(from: coin, through: M, by: 1) {
dp[i] = dp[i] + dp[i - coin]
}
// for i in coin...M {
// dp[i] = dp[i] + dp[i - coin]
// }
}
print(dp[M])
}
백준 Swift 12865번
문제 유형 : DP(재귀, 반복문)
처음에 풀었을 때, 위에서 푼 9084번 문제와 풀이가 같다고 생각했다. 주어진 TC도 통과했다. 그래서 맞는줄 알았다. 근데 틀렸다.
왜 틀렸는지 모르겠어서 고민했는데, 반례를 보고 내가 짠 코드가 왜 틀렸는지 깨달았다.
물건이 1개씩만 있다는 사실이다. (9084번 문제는 코인이 무제한이였다.)
방금 문장이 굉장히 중요한 힌트다. 이전의 값이 필요하고, 그럼 자연스레 dp배열이 2차원이어야 한다.
그 다음, 반복문에서 bags[i].weight...K만큼은 점화식을 적용해야 하고, 그 외 부분은 dp[i][j] = dp[i - 1][j]로 신경써줘야 한다.
아래 종이에는 적혀 있지 않고, 코드를 보면 알 수 있다.
난이도 : 골드5
반례
3 5
4 2
3 4
1 5
ans => 9가 나와야 함.
참고 자료 : https://cocoon1787.tistory.com/206
반복문
// MARK: - 12865번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var bags: [(weight: Int, value: Int)] = [(0, 0)] // 인덱스0의 값은 0으로 공간메꾸기.
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (W, V) = (input[0], input[1])
bags.append((W, V))
}
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: K + 1), count: N + 1)
for i in 1...N {
// for j in stride(from: bags[i].weight, through: K, by: 1) { // 이렇게만 하면, 다음 행의 나머지 부분들의 값이 계속 유지되는게 아니라 0이 됨.
// dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - bags[i].weight] + bags[i].value)
// }
for j in 1...K { // 1부터 K까지 돌면서,
if j >= bags[i].weight { // j - bags[i].weight가 인덱스의 범위를 벗어나지 않으면,
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - bags[i].weight] + bags[i].value)
}
else { // j - bags[i].weight가 인덱스의 범위를 벗어나면,
dp[i][j] = dp[i - 1][j]
}
}
}
print(dp[N][K])
백준 Swift 9251번
문제 유형 : DP(재귀, 반복문)
LCS문제를 이전에 풀어보긴 했었는데, 그 때 LCS 유형을 다시 풀어본다 했는데 역시나 어렵다.
아예 모르겠어서 다른 블로그를 참고했다.
각 문자열로 이루어진 행렬을 만들고,
문자가 같을 땐 좌상측값 + 1
문자가 다를 땐 max(좌측값, 우측값)
점화식은 아래 사진에서 확인할 수 있다.
난이도 : 골드5
참고 자료 : https://st-lab.tistory.com/139
반복문
// MARK: - 9251번(DP - 반복문)
let str1: [String] = [""] + readLine()!.map{String($0)} // 하단 반복문에서 인덱스 맞추기 위해, 미리 맨 앞에 "" 붙임.
let str2: [String] = [""] + readLine()!.map{String($0)}
let (len1, len2) = (str1.count - 1, str2.count - 1)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: len2 + 1), count: len1 + 1)
for i in 1...len1 {
for j in 1...len2 {
if str1[i] == str2[j] { // 문자가 같을 땐,
dp[i][j] = dp[i - 1][j - 1] + 1
}
else { // 문자가 다를 땐,
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
print(dp[len1][len2])
백준 Swift 2225번
문제 유형 : DP(재귀, 반복문)
처음에 보고 중복조합을 사용하려 했다. 근데 factorial이 숫자가 커지면서 불가능했다.
결국 다른 블로그를 참고했다.
사진 속 좌측 하단의 1번을 보자. (참고 자료 : https://mygumi.tistory.com/135)
dp[K]N]의 뜻은 무엇인가? -> (0~N의 숫자)K개를 더한 합이 N이 되는 경우의 수다.
dp[K][N]
K개의 숫자들 중 가장 마지막의 수를 L이라고 한다면,
K - 1개의 숫자들의 합은 N - L이 된다. => dp[K - 1][N - L]
dp[K - 1][N - L]
K-1개의 숫자들 중 가장 마지막의 수를 L'이라고 한다면,
K-2개의 숫자들의 합은 N - L - L'이 된다. => dp[K - 2][N- L - L']
이런 식으로, dp[K][N]은 Σdp[K-1][N-L] (0 <= L <= N) 이 된다.
사진 속 우측 상단의 2번을 보면, (참고 자료 : https://haesoo9410.tistory.com/249)
낮은 숫자부터 나열하다보면 규칙을 찾을 수 있다.
=> dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
난이도 : 골드5
반복문(1번)
// MARK: - 2225번(DP - 반복문(1))
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: K + 1)
for i in 0...N {
dp[1][i] = 1
}
for i in 1...K {
for j in 0...N {
for l in 0...j {
dp[i][j] += dp[i - 1][j - l]
dp[i][j] %= 1000000000
}
}
}
print(dp[K][N])반복문(2번) - 시간 단축
// MARK: - 2225번(DP - 반복문(2) : 시간 개선)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: K + 1)
for i in 1...K {
dp[i][0] = 1
}
for i in 1...K {
for j in 1...N {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
dp[i][j] %= 1000000000
}
}
print(dp[K][N])
백준 Swift 5557번
문제 유형 : DP(재귀, 반복문)
dp문제일 거라고 생각하고 표를 그리고 규칙을 찾으려고 했는데 모르겠어서 결국 다른 블로그를 참고했다.
dp[i][j]의 의미는,
arr의 i번째 인덱스까지에서, j라는 결과값을 갖는 경우의 수를 의미한다.
따라서 dp의 i는 0부터 N - 1까지 있으면 된다. (중요하진 않아서 난 그냥 N으로 했다.)
따라서 dp의 j는 0 <= j <= 20이 된다.
초기값
dp[0]의 arr[0]은 반드시 식에 포함된다.
즉, dp[0][arr[0]] = 1이다.
이전 인덱스(i - 1)의 값이 j에서 존재한다면 -> j라는 값을 만들 수 있다는 뜻이다.
이전 인덱스(i - 1)의 값이 j에서 존재할 때,
더할 때(+)
j라는 값에서, 이번 인덱스(i)의 값을 더해도 20이 넘지 않는 경우에만 경우의 수를 더해줄 수 있을 것이다.
뺄 때(-)
j라는 값에서, 이번 인덱스(i)의 값을 빼도 음수가 되지 않는 경우에만 경우의 수를 더해줄 수 있을 것이다.
난이도 : 골드5
참고 자료 : https://baby-ohgu.tistory.com/23
반복문
// MARK: - 5557번(DP - 반복문)
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: 21), count: N)
dp[0][arr[0]] = 1 // 가장 첫번째 숫자는 무조건 0~20에 포함됨.
for i in 1...N-2 {
for j in 0...20 {
if dp[i - 1][j] >= 1 {
if j + arr[i] <= 20 { // 더했을 때, 20이하여야 가능.
dp[i][j + arr[i]] += dp[i - 1][j]
}
if j - arr[i] >= 0 { // 뺐을 때, 0이상이어야 가능.
dp[i][j - arr[i]] += dp[i - 1][j]
}
}
}
}
print(dp[N - 2][arr[N - 1]])
백준 Swift 1965번
문제 유형 : DP(재귀, 반복문)
LIS관련 문제다. LIS관련된 문제를 최대한 많이 풀어보면서 공부했다. 누가 이런식으로 LIS활용 문제 번호 모음집이 있으면 좋을 것 같다.
이 문제는 LIS에 대한 언급이 없지만, 결론적으로 백준 11053번 문제와 같다.
LIS를 2중반복문으로 풀면 되는 간단한 문제다.
난이도 : 실버2
반복문
// MARK: - 1965번(DP - 반복문 / LIS - 이중반복문)
let n = Int(readLine()!)!
var arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 1, count: n)
for i in 1..<n {
for j in 0..<i {
if arr[j] < arr[i] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
print(dp.max()!)백준 Swift 12015번, 12738번
문제 유형 : DP(재귀, 반복문)
백준 2631번을 풀다가, LIS에 대해 모른다는 걸 느껴서 LIS를 공부하고 풀었다.
LIS를 dp로 푸는 방법은 2가지가 있다.
방법 1 : 이중 for문 - O(N^2) / 관련 문제 : https://www.acmicpc.net/problem/11053
방법 2 : 이분탐색 활용 - O(NlogN) / 관련 문제 : https://www.acmicpc.net/problem/12015
12015번은 시간초과가 나서 방법 1로는 못푼다.
LIS를 풀 때 방법2의 존재에 대해서 알고는 있었다. 미루다 오늘에서야 공부했다..ㅋㅋ
[풀이 방법]
1. dp배열을 선언한다.
단, dp배열은 부분 수열의 길이를 저장하는 게 아니라, dp배열 자체가 가장 긴 증가하는 부분 수열이 된다.
여기서 주의할 점은, dp배열이 진짜 가장 긴 증가하는 부분 수열은 아니라는 점이다. 길이만 같다.
아래 사진을 보면 이해가 쉽다. [5, 6, 7, 1]의 LIS는 [5, 6, 7]일 것이다.
하지만 이분탐색을 통해 풀면 나오는 값은 [1, 6, 7]이다.
나도 이렇게 풀면, 진짜 LIS는 아닌 거 같은데? 라는 생각으로 고민하다가 알게 됐다.
이와 관련해선 추후에 백준 14002번, 14003번 문제를 풀면 알 수 있을 것이다. (https://yabmoons.tistory.com/561)
2. arr을 돌면서, dp의 가장 마지막 배열과 비교한다.
2-1. 더 큰 수가 들어 온다면, (arr[i] > dp.last!)
-> dp의 끝부분에 이어 붙인다. (dp.append(arr[i]))
2-2. 작거나 같은 수가 들어온다면, (else)
-> 이분탐색을 통해 arr[i]가 들어가야 하는 위치에 대해 찾아낸 뒤, 기존의 값과 교체한다.
더 긴 수열을 만드는 데 있어서, 최대한 작은 수로 교체하는 게 이득이다.
예를 들어, dp 배열이 [3, 7, 12]와 [3, 7, 8]이라고 가정하자.
근데 뒤에 올 숫자가 만약 10이라면, 후자만 더 긴 LIS를 만들 수 있게 된다.
3. dp의 길이를 출력하면 끝이다. (dp.count)
난이도 : 골드2
참고 자료 : https://ttl-blog.tistory.com/486
반복문 - 12015번
// MARK: - 12015번(DP - 반복문) / LIS(이분탐색)
let N = Int(readLine()!)!
var arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = [arr[0]] // 이번 dp배열에선 길이를 저장하는 게 아니라, dp 전체가 가장 긴 증가하는 부분수열이 된다.(길이는 맞지만, 실제의 LIS와는 다르다.)
for i in 1..<N {
if arr[i] > dp.last! { // dp배열의 가장 마지막에 있는 수보다 더 큰 수가 들어온다면,
dp.append(arr[i]) // 그냥 맨 뒤에 이어 붙이면 됨.
}
else { // 하지만 그렇지 않다면, 이분탐색을 통해서 위치를 찾아서 넣어야 함.
let index = binarySearch(arr[i])
dp[index] = arr[i]
}
}
print(dp.count)
func binarySearch(_ target: Int) -> Int { // 이분탐색
var (low, high) = (0, dp.count - 1)
while low <= high {
let middle = (low + high) / 2
if dp[middle] >= target {
high = middle - 1
}
else {
low = middle + 1
}
}
return low
}반복문 - 12738번
// MARK: - 12738번(DP - 반복문 / LIS - 이분탐색)
let N = Int(readLine()!)!
let arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = [arr[0]]
for i in 1..<N {
if arr[i] > dp.last! { // 더 크면 그냥 뒤에 이어 붙이면 됨.
dp.append(arr[i])
}
else {
let index = binarySearch(arr[i])
dp[index] = arr[i]
}
}
print(dp.count)
func binarySearch(_ target: Int) -> Int {
var (low, high) = (0, dp.count - 1)
while low <= high {
let middle = (low + high) / 2
if dp[middle] >= target {
high = middle - 1
}
else {
low = middle + 1
}
}
return low
}백준 Swift 14002번, 14003번
문제 유형 : DP(재귀, 반복문)
[백준 14002번 풀이]
14002번은 반복문을 사용했다. 길이를 구하는 풀이는 11053번 풀이와 같다.
그 다음 각각의 인덱스에서 나올 수 있는 LIS의 길이를 담고 있는 dp배열을 보고, 어떻게 LIS배열을 구해야 할지 생각해야 된다.
이 아이디어를, 전에 이분탐색풀이(12015번)할 때 LIS배열이 이상하게 나와서, 내 생각(이상하게 나오는)이 맞는지 찾아보다가 스포? 당했다.
핵심 : dp배열의 뒤에서부터 반복문을 돌린다.
dp배열의 뒤에서부터 돌면서, dp 중 가장 큰 수를 기준으로 잡고, 기준값을 1씩 줄이면서 같은 값이 나올 때 answer 배열에 넣으면 된다.
끝까지 다 돌았다면, answer배열을 뒤집어서 출력하면 정답이다.
[백준 14003번 풀이]
LIS 문제를 풀면서, 관련 문제를 끝까지 푸는 게 좋을 거 같았다. 플래티넘 문제는 처음 풀어봤다. (무섭ㅋㅋ)
14002번(아이디어)과 12015번(이분탐색)을 활용 +α 해서 풀면 된다.
N의 범위가 매우 크기 때문에 이분탐색을 활용한다.
핵심 : arr의 값이 dp배열에 들어갈 때, 어디에 들어가는지 위치를 저장하는 indexArray를 선언한다.
var indexArray: [Int] = [0] // dp배열에서 arr의 각 값이 몇번째 인덱스에 위치하는지 저장하는 배열.
indexArray배열의 뒤에서부터 돌면서, dp.count - 1를 기준으로 잡고, (인덱스이기 때문에 dp의 전체 갯수 - 1을 해야 끝부터 확인할 수 있다.)
기준값을 1씩 줄이면서 같은 값이 나올 때 answer 배열에 넣으면 된다.
끝까지 다 돌았다면, answer배열을 뒤집어서 출력하면 정답이다.
난이도 : 골드4 / 플래티넘 5
14003번 참고 링크 : https://yabmoons.tistory.com/561
반복문 - 14002번
// MARK: - 14002번(DP - 반복문 / LIS - 이중반복문)
let N = Int(readLine()!)!
var arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = Array(repeating: 1, count: N)
for i in 1..<N {
for j in 0..<i {
if arr[j] < arr[i] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
var standard: Int = dp.max()!
print(standard) // LIS의 길이 출력.
var answer: [Int] = []
for i in stride(from: N - 1, through: 0, by: -1) { // dp를 뒤에서부터 돌면서,
if dp[i] == standard { // 기준 : 최대값부터 1까지
answer.append(arr[i])
standard -= 1
}
}
answer.reverse()
print(answer.map{String($0)}.joined(separator: " "))반복문 - 14003번
// MARK: - 14003번(DP - 반복문 / LIS - 이분탐색)
let N = Int(readLine()!)!
var arr: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = [arr[0]]
var indexArray: [Int] = [0] // dp배열에서 arr의 각 값이 몇번째 인덱스에 위치하는지 저장하는 배열.
for i in 1..<N {
if arr[i] > dp.last! { // dp의 마지막 값보다 크면, 확인할 필요 없이 이어 붙이면 됨.
dp.append(arr[i])
indexArray.append(dp.count - 1) // dp배열에서의 위치(인덱스) 저장.
}
else { // dp의 마지막 값보다 크지 않다면, 이분탐색.
let index = binarySearch(arr[i])
dp[index] = arr[i] // 값 교체.
indexArray.append(index) // dp배열에서의 위치(인덱스) 저장.
}
}
print(dp.count) // LIS의 길이 출력.
var standard: Int = dp.count - 1 // 기준.
var answer: [Int] = []
for i in stride(from: N - 1, through: 0, by: -1) { // indexArray를 뒤에서부터 돌면서,
if indexArray[i] == standard { // 기준값과 같다면,
answer.append(arr[i])
standard -= 1 // 기준값 -1씩.
}
}
answer.reverse()
print(answer.map{String($0)}.joined(separator: " "))
func binarySearch(_ targetNum: Int) -> Int { // 이분탐색
var (low, high) = (0, dp.count - 1)
while low <= high {
let middle = (low + high) / 2
if dp[middle] >= targetNum {
high = middle - 1
}
else {
low = middle + 1
}
}
return low
}백준 Swift 2631번
문제 유형 : DP(재귀, 반복문)
이 문제가 LIS를 전부 공부하게 만든 이유다.
(LIS에 대해선 잘 모르고) LCS만 알고 이 문제를 접근 했을 때, LCS로 풀긴 풀었다. 아래 더보기를 누르면 더 자세한 스토리를 알 수 있다.
백준 Swift 2631번 - LCS 질문 / 스토리
LIS 풀이
1. LIS의 길이를 구한다.
1-1. LIS의 길이를 구할 때 이중반복문(O(N^2)) or 이분탐색(O(NlogN))을 쓸 수 있다.
이 문제에선 N의 범위가 작기 때문에, 간단하게 이중반복문으로 구현하면 된다. (하단 코드에 두 버전 모두 올렸습니다.)
2. answer = N - LIS
우린 최종적으로 증가하는 순서대로 아이들을 배치해야 한다. 테스트케이스를 보면 알 수 있듯이, 기존에 주어지는 순서에서 이미 오름차순인 아이들의 상대위치는 변하지 않는다. (주어진 TC에서 3, 5, 6의 상대적인 순서는 그대로다. 사이에 어떤 수가 끼긴 해도, 3이 제일 앞이고, 5가 중간이고, 6이 마지막이라는 뜻이다.)
LIS는 증가하는 부분 수열이다.
이미 올바르게 서 있는 아이들의 수를 최대(= LIS)로 해야 움직이는 수가 최소가 된다. => 즉, N - LIS
난이도 : 골드5
참고 링크 : https://www.acmicpc.net/board/view/4872
반복문 - 이중반복문
// MARK: - 2631번(DP - 반복문 / LIS - 이중반복문)
let N = Int(readLine()!)!
var arr: [Int] = []
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
var dp = Array(repeating: 1, count: N) // LIS를 저장하는 dp배열.
for i in 1..<N {
for j in 0..<i {
if arr[j] < arr[i] { // 증가하는 배열일 때,
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
let answer: Int = N - dp.max()! // N - LIS
print(answer)반복문 - 이분탐색
// MARK: - 2631번(DP - 반복문 / LIS - 이분탐색)
let N = Int(readLine()!)!
var arr: [Int] = []
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
var dp: [Int] = [arr[0]]
for i in 1..<N {
if arr[i] > dp.last! { // dp의 가장 마지막에 있는 값보다 클 땐,
dp.append(arr[i]) // dp 뒤에 이어붙이면 됨.
}
else { // 그렇지 않다면,
let index = binarySearch(arr[i]) // arr[i]가 들어갈 위치를 찾고,
dp[index] = arr[i] // 기존의 값을 변경.
}
}
let answer: Int = N - dp.count // N - LIS
print(answer)
func binarySearch(_ targetNum: Int) -> Int { // 이분탐색
var (low, high) = (0, dp.count - 1)
while low <= high {
let middle = (low + high) / 2
if dp[middle] >= targetNum {
high = middle - 1
}
else {
low = middle + 1
}
}
return low
}
LCS 관련 풀이
LCS 풀이
// MARK: - 2631번(DP - 반복문)
let N = Int(readLine()!)!
var ans = Array(0...N) // https://stackoverflow.com/questions/34571043/how-to-create-an-array-with-incremented-values-in-swift
var arr: [Int] = [0]
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
for i in 1...N {
for j in 1...N {
if ans[i] == arr[j] { // 숫자가 같으면,
dp[i][j] = dp[i - 1][j - 1] + 1
}
else { // 숫자가 다르면,
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) // 왼쪽과 위쪽 중 큰 값.
}
}
}
let answer: Int = N - dp[N][N] // N - LCS
print(answer)문제 유형 : DP(재귀, 반복문)
뭔가 풀릴 것 같은데 안풀려서 고민했다.
LIS를 활용하면 될 것 같다고 생각했다. 처음엔 각각의 LIS를 구해서 N - 최댓값을 하면 될 것 같았는데 반례가 바로 나왔다.
튜플로 묶은 arr배열을 A기준 오름차순 정렬한다.
그 다음 B를 기준으로 LIS를 구한 뒤, N - LIS를 하면 된다.
난이도 : 골드5
반복문
// MARK: - 2565번(DP - 반복문 / LIS - 이중반복문)
let N = Int(readLine()!)!
var arr: [(A: Int, B: Int)] = []
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
arr.append((input[0], input[1]))
}
arr.sort(by: <) // A기준으로, 오름차순 정렬.
var dp: [Int] = Array(repeating: 1, count: N)
for i in 1..<N {
for j in 0..<i {
if arr[j].B < arr[i].B {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
let answer: Int = N - dp.max()!
print(answer)
문제 유형 : DP(재귀, 반복문)
비슷한 문제를 풀었어서 쉽게 풀 수 있을 거라고 생각했다. 계속 될 거 같은데 안풀렸다. 약 3시간을 고민했는데 결국 모르겠어서 다른 블로그를 참고했다.
근데 머리를 이미 다 썼는지... 모든 글을 찾아봐도 설명이 다 이해가 안됐다. (이 문제에 대해 설명이 있는 글이 별로 없는 것도 한 몫한 것 같다.)
풀이
1. 코인배열을 오름차순으로 정렬한다. (하지 않아도 된다.)
2. 코인(i)을 순차적으로 돌면서,
2-1. 1부터 T까지 도는 j가 currCoin보다 작을 땐 기존의 값(dp[i-1][j])을 그대로 저장한다.
2-2. 2-1에 해당하지 않는다면,
3. 사용가능한 코인 개수(currCnt)를 0개부터 currCnt를 사용한다.
3-1. 코인을 k개(0개, 1개, 2개, ... currCnt개) 썼을 때 인덱스를 벗어나지 않는 경우에만,
이전 코인(i - 1)의 현재코인을 k개 썼을 때의 값을 더한다. ( dp[i][j] += dp[i - 1][j - k * currCoin] )
난이도 : 골드5
참고 자료 : https://ioqoo.tistory.com/16
반복문
// MARK: - 2624번(DP - 반복문)
let T = Int(readLine()!)!
let K = Int(readLine()!)!
var coins: [[Int]] = [[0, 0]] // [0, 0]은 인덱스 채우기용.
for _ in 0..<K {
coins.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
coins.sort{$0[0] < $1[0]} // 동전금액기준 오름차순 정렬. (2차원배열 sort - https://stackoverflow.com/questions/31088974/use-sort-for-multidimensional-array-array-in-array-in-swift)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: T + 1), count: K + 1)
for i in 0...K { // 초기값 세팅.
dp[i][0] = 1 // 0원 만드는 경우는 1가지.
}
for i in 1...K {
let (currCoin, currCnt) = (coins[i][0], coins[i][1]) // (현재 코인, 현재 코인의 사용 가능한 개수)
for j in 1...T {
if j < currCoin { // 현재 비교할 코인보다 작은 인덱스일 땐,
dp[i][j] = dp[i - 1][j] // 지난번 값 그대로 저장.
continue
}
for k in 0...currCnt { // 현재 코인의 사용가능한 개수까지 사용하면서, (현재 코인 | 0개 사용일 때, 1개 사용일 때, ... currCnt개 사용일 때)
if j - k * currCoin >= 0 { // 인덱스를 벗어나지 않는 경우에만,
dp[i][j] += dp[i - 1][j - k * currCoin]
}
}
}
}
print(dp[K][T])
백준 Swift 14567번
문제 유형 : DP(재귀, 반복문) / 위상 정렬(Topology Sort)
DP풀이를 먼저 보고, 위상 정렬풀이를 보면 쉬울 것이다.
DP 풀이
맨 처음엔 그래프문제인 거 같았지 DP문제 같아 보이진 않았다. 근데 종이에 적어보니 느낌이 바로 왔다.
이전과목의 이수학기가 다음과목의 이수학기에 영향을 끼치기 때문이다!
arr에 입력받고, from기준으로 오름차순으로 정렬한다. (선수 과목이 낮은 순서대로 정렬(A과목 기준으로)을 해야 올바르게 모든 과목을 들을 수 있을 것이다!)
arr을 돌면서 max(다음과목의 기존 값, 이전과목의 값 + 1) 중 큰 값을 다음과목의 값에 넣으면 된다.
즉, dp[line.to] = max(dp[line.to], dp[line.from] + 1) 이다.
위상정렬 풀이
우선 DP로 풀고 제출해서 맞았다. 다른 사람들의 풀이가 궁금해서 보니까 큐로 풀었더라..? dp문제인데 왜 큐가 나오지 싶었다.
찾아보니까 백준 14567번 문제가 DP도 가능하고 위상정렬도 가능하다고 한다. 난 사실 위상정렬을 처음 들어봤다.
우선 진입차수(indegree)를 기록한다.
진입차수가 0인 노드들만 큐에 넣는다.
q.popFirst()를 해서 나온 노드(node)와 연결된 노드(nextNode)를 확인 후 answer값을 증가시킨다. (= 현재노드의 다음학기에 수강.)
q.popFirst()를 해서 나온 노드(node)와 연결된 노드(nextNode)의 진입차수를 낮추고, 만약 0이라면 큐에 넣는다.
반복하고 answer를 출력하면 된다.
위상정렬과 관련해서 아래 참고 자료를 확인하길 추천한다.
난이도 : 골드5
참고 자료 : https://m.blog.naver.com/ndb796/221236874984
DP - 반복문
// MARK: - 14567번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var arr: [(from: Int, to: Int)] = []
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
arr.append((input[0], input[1]))
}
arr.sort(by: <) // from기준 오름차순 정렬
var dp: [Int] = Array(repeating: 1, count: N + 1)
dp[0] = 0
for line in arr {
dp[line.to] = max(dp[line.to], dp[line.from] + 1)
}
print(dp[1...N].map{String($0)}.joined(separator: " "))위상정렬 - 큐
// MARK: - 14567번(위상정렬 - 큐)
class Dequeue<T> {
var enQueue: [T]
var deQueue: [T] = []
var count: Int {
return enQueue.count + deQueue.count
}
var isEmpty: Bool {
return enQueue.isEmpty && deQueue.isEmpty
}
init(_ queue: [T]) {
enQueue = queue
}
func pushLast(_ element: T) {
enQueue.append(element)
}
func pushFirst(_ element: T) {
deQueue.append(element)
}
func popLast() -> T {
if enQueue.isEmpty {
enQueue = deQueue.reversed()
deQueue.removeAll()
}
return enQueue.popLast()!
}
func popFirst() -> T {
if deQueue.isEmpty {
deQueue = enQueue.reversed()
enQueue.removeAll()
}
return deQueue.popLast()!
}
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var indegree = Array(repeating: 0, count: N + 1) // 진입차수
var graph: [[Int]] = Array(repeating: [], count: N + 1) // 노드i에서 이동가능한 노드들 모음.
var answerArray: [Int] = Array(repeating: 1, count: N + 1) // 학기 저장 배열.
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (from, to) = (input[0], input[1])
graph[from].append(to)
indegree[to] += 1 // 진입차수 저장.
}
let q: Dequeue<Int> = Dequeue([])
for i in 1...N {
if indegree[i] == 0 { // 진입차수가 0인 것들만 큐에 넣음.
q.pushLast(i)
}
}
while !q.isEmpty { // 큐가 빌 때까지,
let node: Int = q.popFirst()
for nextNode in graph[node] {
answerArray[nextNode] = answerArray[node] + 1 // 현재노드의 다음학기 수강.
indegree[nextNode] -= 1 // 진입차수 감소.
if indegree[nextNode] == 0 { // 만약 진입차수가 0이면, 큐에 넣음.
q.pushLast(nextNode)
}
}
}
print(answerArray[1...N].map{String($0)}.joined(separator: " "))백준 Swift 17485번
이 문제를 봤을 때 DP를 이용해야겠다는 느낌은 들었다.
고민을 하다가 모르겠어서 다른 블로그를 참고했다.
풀이 방법
0) 움직일 수 있는 방향을 0(↙), 1(↓), 2(↘)로 정의한다.
dp를 [y][x]와 [0 or 1 or 2]를 써서 방향을 나타낼 수 있게 3차원배열로 정의한다.
인덱스가 헷갈리지 않게 하기 위해, y와 x가 0일 때는 (최소값을 구할 거기 때문에) Int.max값으로 채워 놓는다. (1...N 과 1...M만 신경쓸 예정.)
1) y를 1...N까지 돌면서, y가 1일 땐(인덱스 0일 땐 메워둠.)
dp[1][x][0], dp[1][x][1], dp[1][x][2]에 각각의 board값을 넣는다.
전제조건 : 같은 방향 2번은 불가능하다.
2) x가 가장 좌측일 땐, 방향0과 방향1만 가능하다. 가장 좌측으로 오기 위해 방향2는 불가능하다.
2-1) 방향0일 때: 전제조건에 의해, (y - 1)행의 (x + 1)열의 방향1와 방향2 중 최소값 + board[y][x] = dp[y][x][0]값이 된다.
2-2) 방향1일 때: 전제조건에 의해, (y - 1)행의 (x)열의 방향0 값 + board[y][x] = dp[y][x][1]값이 된다.
3) x가 가장 우측일 땐, 방향 1과 방향2만 가능하다. 가장 우측으로 오기 위해 방향1은 불가능하다.
3-1) 방향2일 때: 전제조건에 의해, (y - 1)행의 (x - 1)열의 방향0 과 방향1 중 최소값 + board[y][x] = dp[y][x][2]값이 된다.
3-2) 방향1일 때: 전제조건에 의해, (y - 1)행의 (x)열의 방향2 값 + board[y][x] = dp[y][x][2]값이 된다.
4) x가 그 외일 땐, 모든 방향이 가능하다.
4-1) 방향0일 때: 전제조건에 의해, (y - 1)행의 (x + 1)열의 방향1 과 방향2 중 최소값 + board[y][x] = dp[y][x][0]값이 된다.
4-2) 방향1일 때: 전제조건에 의해, (y - 1)행의 (x)열의 방향0 과 방향2 중 최소값 + board[y][x] = dp[y][x][1]값이 된다.
4-3) 방향2일 때: 전제조건에 의해, (y - 1)행의 (x - 1)열의 방향0 과 방향1 중 최소값 + board[y][x] = dp[y][x][2]값이 된다.
5) y가 N일 때, (가장 끝에 왔을 때)
x를 1부터 M까지 돌리면서, 가장 작은 min값을 찾으면 정답이다.
난이도 : 골드5
참고 자료 : https://maeng2world.tistory.com/470
반복문
// MARK: - 17485번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[Int]] = Array(repeating: [], count: N + 1)
board[0] = Array(repeating: 0, count: M + 1)
for i in 1...N {
board[i] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!} // [0]은 인덱스 맞추기 위해.
}
var dp: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: Int.max, count: 3), count: M + 1), count: N + 1) // 0(↙), 1(↓), 2(↘)
for y in 1...N {
if y == 1 { // 가장 첫 스타트일 땐 board값 dp에 저장.
for x in 1...M {
for d in 0..<3 {
dp[y][x][d] = board[y][x]
}
}
}
else { // 2...N
for x in 1...M {
if x == 1 { // 가장 좌측일 때, 방향 0과 1은 가능. 2로 오는건 불가능.
dp[y][x][0] = min(dp[y - 1][x + 1][1], dp[y - 1][x + 1][2]) + board[y][x] // 지난 행, 다음 열의 min(방향1, 방향2)값 + 현재값
dp[y][x][1] = dp[y - 1][x][0] + board[y][x] // 지난 행, 같은 열의 값(방향0) + 현재값
}
else if x == M { // 가장 우측일 때, 방향 1과 2는 가능. 0으로 오는건 불가능.
dp[y][x][2] = min(dp[y - 1][x - 1][0], dp[y - 1][x - 1][1]) + board[y][x] // 지난 행, 지난 열의 min(방향0, 방향1)값 + 현재값
dp[y][x][1] = dp[y - 1][x][2] + board[y][x] // 지난 행, 같은 열의 값(방향2) + 현재값
}
else { // 그 외,
dp[y][x][0] = min(dp[y - 1][x + 1][1], dp[y - 1][x + 1][2]) + board[y][x] // 지난 행, 다음 열의 min(방향1, 방향2)값 + 현재값
dp[y][x][1] = min(dp[y - 1][x][0], dp[y - 1][x][2]) + board[y][x] // 지난 행, 같은 열의 min(방향0, 방향2)값 + 현재값
dp[y][x][2] = min(dp[y - 1][x - 1][0], dp[y - 1][x - 1][1]) + board[y][x] // 지난 행, 지난 열의 min(방향0, 방향1)값 + 현재값
}
}
}
}
var answer: Int = Int.max
for x in 1...M {
answer = min(answer, dp[N][x].min()!)
}
print(answer)백준 Swift 21941번
문제 유형 : DP(재귀, 반복문) / 그리디(X)
어떻게 풀어야할지 고민해봤지만 잘 모르겠었다. 처음엔 DP가 아닌 그리디 풀이법을 생각했다. 그러다 결국 다른 블로그를 참고했다.
문제 푸는 로직은 이해됐는데, 이를 Swift로 구현하려고 하니까 힘들었다...(하단 3-2부분)
그래도 해결했으니 잘 설명해보겠다!
백준 21941번 DP풀이
1. S배열에 [String]으로 저장한다. ["0"]을 맨 앞에 붙여서, 인덱스를 맞춰준다.
2. dp배열을 0부터 S.count만큼 만들고, 1씩 증가하게 값을 저장한다. (사실 그냥 값을 0으로 초기화해도 상관없다.)
1씩 증가하게 저장한 이유는 문자열조건(A)에 해당하는 게 없으면 점수가 1씩 증가하기 때문이다.
3. i를 1부터 sLength만큼 돌면서,
3-1. 우선 기존의 값(dp[i])과 dp[i -1] + 1 중 큰 값을 저장한다. (+1은 문자열조건(A)에 해당하는 게 없으면 1을 더해주는 것이다.)
dp[i] = max(dp[i], dp[i - 1] + 1) // 문자열조건에 해당되는 게 없을 땐 1점만.3-2. [String]의 일부로 String을 만들고, 만든 String이 임의의 String으로 시작하는지 체크하는 게 필요했는데, 여기가 Swift로 구현이 힘들었다.
배열 S 인덱스의 i부터 끝까지로 String을 만든다. = testS
testS를 만든 이유는, condition.str이 문자열조건(A)으로 시작하는지 체크하기 위함이다.
let testS: String = S[i...sLength].joined(separator: "") // S의 i부터 끝까지를 String으로 만든 다음, 그 String이 문자열조건(A)로 시작하는지 체크.
4. 조건들(문자열조건(A), 점수)을 돌면서,
4-1. 만약 testS가 문자열조건(A)으로 시작한다면, (hasPrefix관련 : https://stackoverflow.com/questions/32664543/swift-startswith-method)
4-2. 문자열조건(A)의 길이만큼 인덱스를 옮긴 곳에, max(기존 값, (i - 1)의 dp값 + 조건 점수) 큰 값을 저장한다.
인덱스가 i가 아닌, (i - 1)이어야 str의 길이를 더했을 때 dp의 알맞은 인덱스에 위치하게 된다. 종이 풀이의 좌측 하단 dp표를 참고하면 이해가 쉽다.
for condition in arr { // 조건들(문자열조건(A), 점수)을 돌면서,
if testS.hasPrefix(condition.str) { // testS가 문자열조건(A)으로 시작한다면,
dp[(i - 1) + condition.str.count] = max(dp[(i - 1) + condition.str.count], dp[i - 1] + condition.score) // 문자열조건(A)의 길이만큼 인덱스를 옮겨서, max(기존 값, (i - 1)의 dp값 + 조건 점수) 큰 값을 저장한다.
}
}
5. DP의 가장 끝 값을 출력하면 끝!
백준 21941번 그리디 풀이 - 97%에서 틀림.
풀이 1. 조건들 중, str의길이가 점수(X)보다 작으면 교체하는 게 손해다. 그런 조건은 arr에 넣지 않는다.
풀이 2. arr을 교체효율이 좋은 순으로 정렬한다. str의 길이는 짧을 수록, 점수는 클 수록 이득이다.
arr 정렬 기준 : score / length
풀이 3. 문자열S에 condition.str이 존재한다면,
풀이 3-1. .replacingOccurrences를 통해 "_"로 교체한다. 단점은 몇개가 교체됐는지 한 번에 알 수 없다는 것이다.
풀이 3-2. 단점을 해결하기 위해, countArray를 둬 각 조건에 의해 변경된 개수를 저장한 걸 이용해 nowCount를 구한다.
풀이 4. "_"로 교체되지 않은 나머지(remain)의 개수만큼 더해주면 끝!
풀이가 틀린 게 없는 것 같은데.... 왜 97%에서 틀리는지 모르겠다... 어디가 틀렸는지 아시겠는 분은 꼭 좀 댓글이나 백준답변으로 달아주시면 감사하겠습니다. (백준 질문 글 - https://www.acmicpc.net/board/view/91564 / 백준 반례 글 - https://www.acmicpc.net/board/view/89027)
22.05.31 추가 내용 : 반례 글을 보니까, 제 생각에 이 문제는 그리디로는 불가능 한 것 같습니다..!
난이도 : 골드5
참고 자료 : https://t.ly/DZ29w | https://stackoverflow.com/questions/25827033/how-do-i-convert-a-swift-array-to-a-string | https://t.ly/Yewx
(여기선 결국 필요 없었지만 유용한) 참고 자료 : https://stackoverflow.com/questions/56175794/check-if-a-string-is-substring-of-another-string-using-swift-5
DP - 반복문
// MARK: - 21941번(DP - 반복문)
import Foundation
let S: [String] = ["0"] + readLine()!.map{String($0)} // 0은 인덱스 채우기 용.
let M = Int(readLine()!)!
var arr: [(str: String, score: Int)] = []
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{String($0)}
let (A, X): (String, Int) = (input[0], Int(input[1])!) // 문자열조건, 점수
arr.append((A, X))
}
var dp: [Int] = Array(repeating: 0, count: S.count)
for i in 0..<dp.count {
dp[i] = i
}
let sLength: Int = S.count - 1 // 입력받은 S의 진짜 길이.
for i in 1...sLength {
dp[i] = max(dp[i], dp[i - 1] + 1) // 문자열조건에 해당되는 게 없을 땐 1점만.
let testS: String = S[i...sLength].joined(separator: "") // S의 i부터 끝까지를 String으로 만든 다음, 그 String이 문자열조건(A)로 시작하는지 체크.
for condition in arr { // 조건들(문자열조건(A), 점수)을 돌면서,
if testS.hasPrefix(condition.str) { // testS가 문자열조건(A)으로 시작한다면,
dp[(i - 1) + condition.str.count] = max(dp[(i - 1) + condition.str.count], dp[i - 1] + condition.score) // 문자열조건(A)의 길이만큼 인덱스를 옮겨서, max(기존 값, (i - 1)의 dp값 + 조건 점수) 큰 값을 저장한다.
}
}
// print(dp)
}
print(dp.last!)그리디 - 97%에서 틀림.
// MARK: - 21941번(그리디 - 97%에서 틀림.)
import Foundation
//let S: [String] = readLine()!.map{String($0)}
var S: String = readLine()!
let M = Int(readLine()!)!
var arr: [(str: String, length: Double, score: Double)] = []
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{String($0)}
let (A, X): (String, Double) = (input[0], Double(input[1])!) // 문자열조건, 점수
if X / Double(A.count) > 1 { // 효율이 1이하면 문자열교체하는게 손해임. (교체안하고 그냥 1점씩 받는 게 더 이득.)
arr.append((A, Double(A.count), X))
}
// if A.count < Int(X) { // 위 if문과 같은 의미.
// arr.append((A, Double(A.count), X))
// }
}
arr.sort(by: {($0.score / $0.length) > ($1.score / $1.length)}) // 내림차순 정렬.(효율적인 것부터 앞으로)
var sum: Int = 0
var countArray: [Int] = [0] // 문자열조건에 의해 바뀐 개수 저장하는 배열.
for condition in arr { // 조건을 돌면서,
if S.contains(condition.str) { // S에 문자열조건이 있다면, (check String contain String - https://stackoverflow.com/questions/56175794/check-if-a-string-is-substring-of-another-string-using-swift-5)
S = S.replacingOccurrences(of: condition.str, with: "_") // 문자열을 "_"로 대체.
let totalCount = S.filter{$0 == "_"}.count // 지금까지 문자열조건에 의해 바뀐 총개수 카운트.
let nowCount = totalCount - countArray.reduce(0, +) // 현재 문자열조건에 의해 바뀐 개수.
countArray.append(nowCount)
sum += Int(condition.score) * nowCount
}
}
let remain: Int = S.filter{$0 != "_"}.count // 문자열조건들에 바뀌지 않은, 나머지들.
sum += remain // 나머지들 개수만큼 +1.
print(sum)문제 유형 : DP(재귀, 반복문)
온전히 나의 힘으로 풀었다!! 백준 2624번 문제와 매우 유사하다.
21941번 이후 또다시 Swift기준 최초 풀이 등극했다! 후훗 뭔가 뿌듯하다.
백준 18427번 풀이
풀이 1. 학생들의 블록을 저장한다. [0]은 인덱스 채우기 용.
var studentBlocks: [[Int]] = [[0]] // 학생들 블록 저장하는 배열.
풀이 2. dp를 (N + 1) * (H + 1) 사이즈의 2차원배열을 선언한다.
풀이 2-1. 각 행의 0번째열의 값을 1로 채운다.
풀이 2-2. 1번 학생(1번행)의 블록값(num)과 같은 열의 값을 1로 채운다.
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: H + 1), count: N + 1)
for i in 1...N { // 초기 세팅.
dp[i][0] = 1 // 인덱스 0번째는 1로 채워놓는다.
}
for num in studentBlocks[1] { // 초기 세팅.
dp[1][num] = 1 // 1번학생이 갖고 있는 블록들과 같은 인덱스들의 값을 1로 채워놓는다.
}
풀이 3. 2번째 학생부터 N번째 학생까지 돌면서, (= i를 2...N까지 돌면서,)
풀이 3-1. 1번열부터 H열까지 돌면서,
풀이 3-2. 우선 이전 행의 dp값을 저장한다. dp[i][j] = dp[i-1][j]
풀이 3-3. i번째 학생이 갖고 있는 블록들을 돌면서,
j - num이 인덱스를 벗어나지 않을 때에만 이전 행의 (j-num)열 값들을 더한다.
풀이 4. dp[N][H] % 10007를 출력하면 끝!
Swift 주의사항
계속 100%에서 런타임에러가 떠서 당혹스러웠다.
찾아보니 100%에서 에러가 뜨는거면, 최소값에서 에러가 생기는 확률이 크다고 했다.
아래 반례에서 실제로 에러가 나왔다.
이유는 for문을 2...N으로 돌렸는데, N이 1일 때 문제가 생기는 것이었다.
stride로 for문 돌게 변경해주고 정답!
반례
1 1 1
1
=> 1이 나와야 함.난이도 : 골드4
참고 자료 : https://www.acmicpc.net/board/view/44660
반복문
// MARK: - 18427번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M, H) = (input[0], input[1], input[2])
var studentBlocks: [[Int]] = [[0]] // 학생들 블록 저장하는 배열.
for _ in 0..<N {
studentBlocks.append(readLine()!.split(separator: " ").map{Int(String($0))!}.sorted(by: <)) // 오름차순으로 정렬해서 넣어놓음.
}
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: H + 1), count: N + 1)
for i in 1...N { // 초기 세팅.
dp[i][0] = 1 // 인덱스 0번째는 1로 채워놓는다.
}
for num in studentBlocks[1] { // 초기 세팅.
dp[1][num] = 1 // 1번학생이 갖고 있는 블록들과 같은 인덱스들의 값을 1로 채워놓는다.
}
for i in stride(from: 2, through: N, by: 1) { // 2...N으로 하면 1에서 에러남. (그래서 stride로 함.)
for j in 1...H { // 1번째 열부터 H열까지 돌면서,
dp[i][j] = dp[i - 1][j] % 10007 // 우선 이전 행 dp값 저장.
for num in studentBlocks[i] { // i번째 학생이 갖고 있는 블록들 중,
if j - num >= 0 { // 인덱스를 벗어나지 않을 때에만,
dp[i][j] += (dp[i - 1][j - num]) % 10007 // 이전 행의 (j-num)열 값들을 더함.
}
}
}
}
print(dp[N][H] % 10007)백준 Swift 1915번
문제 유형 : DP(재귀, 반복문)
조금 더 고민했으면 혼자 힘으로 풀 수 있었을 것 같은데 뭔가 아쉽다. 모르겠어서 다른 블로그를 참고했다.
사각형의 우측 하단을 기준으로 dp를 저장해가면 된다.
dp[i][j]는 i행j열 기준으로, 만들 수 있는 최대 정사각형의 한변의 길이다.
풀이 1. 0행이거나 0열이면 dp값은 arr[i][j]의 값이다.
풀이 2. 그 외에서,
풀이 2-1. arr[i][j]값이 0이면 -> dp값은 0이다.
풀이 2-2. arr[i][j]값이 1이면 -> dp값은 ↖, ↑, ← 중 최소값 + 1이다.
풀이 3. dp배열 중 최대값 * 최대값이 정답.
난이도 : 골드4
참고 자료 : https://kyun2da.github.io/2021/04/09/biggestSquare/ | https://t.ly/y8dE
반복문
// MARK: - 1915번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var arr: [[Int]] = []
for _ in 0..<n {
arr.append(readLine()!.map{Int(String($0))!})
}
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
for i in 0..<n { // 초기세팅 - 0열
dp[i][0] = arr[i][0]
}
for j in 0..<m { // 초기세팅 - 0행
dp[0][j] = arr[0][j]
}
for i in 1..<n {
for j in 1..<m {
if arr[i][j] == 0 { // 값이 0이면,
dp[i][j] = 0 // 사각형이 애초에 불가능.
}
else { // 값이 1이면,
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1 // ↖, ↑, ← 중 최소값 + 1
}
}
}
var maxValue: Int = -1
for i in 0..<n { // 각 행을 돌면서,
maxValue = max(maxValue, dp[i].max()!) // 최대값 비교.
}
print(maxValue * maxValue)
백준 Swift 2228번
문제 유형 : DP(재귀, 반복문)
딱 보고 여러가지 테스트케이스를 만들어서 시도해봤으나 규칙이나 감이 전혀 안왔다... 결국 다른 블로그를 참고했는데, 봐도 처음엔 이해가 안됐다.
바텀업 방식으로 보통 DP문제를 풀어 왔는데, 이 문제는 바텀업방식이 되려 복잡하고 이해가 잘 안됐다.
탑다운 방식(재귀)으로 설명을 하겠다.
풀이
풀이 1. (1...N까지의) 각각의 누적합(cumSum)을 구한다. 0번째는 인덱스 채우기 용.
풀이 2. dp는 (N+1)*(M+1)의 사이즈로 구성한다. 각행과 각열의 0번째는 인덱스 채우기 용.
arr의 최대 개수는 100개(N이 최대 100)이고, 수의 최소값은 -32768이다.
따라서, 누적합의 가능한 최소값은 -32768 * 100개일 것이다. dp에 초기값으로 불가능한 값을 넣어놔야 하기 때문에 아래처럼 세팅했다.
let initValue: Int = (-32768 * 100) - 1 // 최소값 -32768 * 최대 100개 -> 가능한 최소 누적합, 거기에 -1을 해야 불가능한 값이 됨.
풀이 3. arr 관련된 그림 - 아래 종이풀이를 확인하자. 경우가 2가지로 나뉜다.
풀이 3-1. (우리에게 필요한) index번째 수가, 구간 section에 속하지 않을 때(X)
: index - 1번째 수의 값과 같을 것이다.
즉, dp[index][section] = solve(index - 1, section)이다.
풀이 3-2. index번째 수가, 구간 section에 속할 때(O)
: 하단 그림을 참고해서 보자.
임의의 수 k부터 n(=index)까지 -> 구간 section에 속한다는 뜻이다.
우리는 가장 끝에 있는 n(=index번째) 수가, 어디부터 시작된 게(=k, k-1, k-2, ...) 구간 section의 최대값인지 알지 못한다.
즉, 구간 section의 최대값을 알기 위해선 다음과 같다.
-> (k - 2번째 수, 구간 section - 1)의 값 + Σarr[k...n] 이다.
Σarr[k...n] = cumSum[n] - cumSum[k-1] 이다.
다시 써보자면,
dp[index][section] = solve(k - 2, section - 1) + (cumSum[n] - cumSum[k-1]) 가 된다.
우린 최대값을 구하는 거니까, 기존의 dp값과 비교를 해주는 부분도 추가되어야 한다.
for k in stride(from: index, through: 1, by: -1) {
dp[index][section] = max(dp[index][section], solve(k - 2, section - 1) + (cumSum[index] - cumSum[k - 1]))
}
재귀함수에서,
범위를 벗어나거나 방문한 적이 있다면 return을 해줘서 빠르게 벗어날 수 있게 한다.
if section == 0 {
return 0
}
if index <= 0 { // index를 벗어날 땐,
return initValue
}
if visited[index][section] { // 방문한 적이 있다면,
return dp[index][section]
}
visited[index][section] = true // 방문 기록.
난이도 : 골드4
재귀 참고자료 : https://loosie.tistory.com/260
반복문 참고자료: https://lotuslee.tistory.com/116 | https://ddiyeon.tistory.com/62
재귀
// MARK: - 2228번(DP - TopDown)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var arr: [Int] = [-32769]
for _ in 0..<N {
arr.append(Int(readLine()!)!)
}
let initValue: Int = (-32768 * 100) - 1 // 최소값 -32768 * 최대 100개 -> 가능한 최소 누적합, 거기에 -1을 해야 불가능한 값이 됨.
var dp: [[Int]] = Array(repeating: Array(repeating: initValue, count: M + 1), count: N + 1)
var cumSum: [Int] = Array(repeating: 0, count: N + 1) // 누적합
for i in 1...N { // 누적합 저장.
cumSum[i] = cumSum[i - 1] + arr[i]
}
//print(cumSum)
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: M + 1), count: N + 1) // 방문체크.
func solve(_ index: Int, _ section: Int) -> Int { // 재귀함수
if section == 0 {
return 0
}
if index <= 0 { // index를 벗어날 땐,
return initValue
}
if visited[index][section] { // 방문한 적이 있다면,
return dp[index][section]
}
visited[index][section] = true // 방문 기록.
dp[index][section] = solve(index - 1, section) // index번째수가 구간section에 속하지 않는 경우.
for k in stride(from: index, through: 1, by: -1) {
dp[index][section] = max(dp[index][section], solve(k - 2, section - 1) + (cumSum[index] - cumSum[k - 1]))
}
return dp[index][section]
}
let answer = solve(N, M)
print(answer)
백준 Swift 2758번
문제 유형 : DP(재귀, 반복문)
dp접근은 맞았다. 지금 다시 생각해보면, 규칙도 거의 찾았는데 끝까지 고민해보지 않은 것 같다. 뭔가 아쉽다. 다른 블로그를 참고했다.
이 문제도 Swift로는 최초 풀이다!
주어진 TC를 아래 종이풀이처럼 써보면 규칙이 보일 것이다.
풀이
풀이 1. i가 1일 땐, 가능한 경우의 수를 미리 저장한다.
풀이 2. i가 2이상일 때,
dp = (같은 행의) 이전 열 값 + (이전 행의) 열/2 값 이다.
즉, 점화식은 다음과 같다.
dp[i][j] = dp[i][j - 1] + dp[i - 1][j / 2] // 이전열 값 + 이전행, 열/2 값
개선 가능성
지금은 새로운 테스트케이스를 돌 때마다 dp를 새로 계산하고 있다.
속도를 더 개선하려면, 미리 n과 m의 최대범위까지 계산 해서 dp배열에 넣고, 각 TC에 맞는 배열값만 출력하게 하면 속도 개선이 될 것이다.
난이도 : 골드4
참고 자료 : https://ddiyeon.tistory.com/65
반복문
// MARK: - 2758번(DP - 반복문)
let T = Int(readLine()!)!
for _ in 0..<T {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
for j in 1...m { // 초기세팅 - 1개 고를 때
dp[1][j] = j
}
for i in stride(from: 2, through: n, by: 1) { // n이 1일 때 error를 방지하기 위해.
for j in 1...m {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j / 2] // 이전열 값 + 이전행, 열/2 값
}
}
print(dp[n][m])
}
백준 Swift 2073번
문제 유형 : DP(재귀, 반복문)
dp의 인덱스를 0...D까지 하면 된다는 것까진 고민 했지만, 그 후에 어떻게 풀면 좋을지 모르겠었다. 결국 다른 블로그를 참고했다.
풀이
이 문제엔 2가지 핵심이 있다.
핵심 1. dp[0]에 0이 아닌 매우 큰 값을 넣어놔야 한다는 것.
핵심 2. dp의 인덱스를 뒤에서부터 돌려야 한다는 것. - 이걸 이해하는 데 애를 먹었다. 아직도 정확히 이해한 거 같지 않다.
수도관의 용량은 각 파이프.capacity들 중 최소값이다.
[for문 안에서 전제조건 : 현재 파이프를 반드시 설치는 한다.]
인덱스를 D에서부터 1까지 거꾸로 돌면서,
1. 현재 파이프의 용량이 더 작은지 VS 2. (현재 파이프) 이전까지의 용량이 더 작은지를 비교한다.
min(pipe.capacity, dp[i - pipe.length])Case1. 2 < 1 : 현재 파이프가 용량이 더 크다는 뜻이다. -> 값은 결국 지금까지의 값(=2)으로 결정된다.
Case2. 1 < 2 : 현재 파이프가 용량이 더 작다는 뜻이다. -> 값이 현재 파이프의 용량 값(=1)으로 결정된다.
위의 순서대로 비교를 할 때, i가 0일 때 dp[0]값이 더 작은 수라면 원하는 결과가 안 나올 것이다.
이를 방지하기 위해 dp[0]에 미리 Int.max를 저장해놓는다.
"우리가 구해야 하는 최종 결론"
해당 i에서의 값(=dp[i])은 최대가 돼야 하기 때문에, max를 써서 매번 더 큰 값을 저장한다.
dp[i] = max(dp[i], min(pipe.capacity, dp[i - pipe.length]))
난이도 : 골드4
참고 자료 : https://kwoncorin.tistory.com/83
반복문
// MARK: - 2073번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (D, P) = (input[0], input[1])
var pipes: [(length: Int, capacity: Int)] = []
for _ in 0..<P {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
pipes.append((input[0], input[1])) // L, C 저장.
}
pipes.sort(by: <) // 오름차순 정렬 - 할 필요는 없음. dp값 확인 용이하게 하려고 정렬.
var dp: [Int] = [Int.max] + Array(repeating: 0, count: D) // dp[0]에 매우 큰 값을 넣어놔야, min비교할 때 정상적으로 작동함. 0이나 음수, 다른 값을 넣으면 꼬임.
for pipe in pipes {
for i in stride(from: D, through: 1, by: -1) {
if i - pipe.length >= 0 {
dp[i] = max(dp[i], min(pipe.capacity, dp[i - pipe.length]))
}
}
// print(dp)
}
print(dp[D])
최근댓글