DP(2-2) 문제 풀이 모음 | 백준 Swift 1520번, 2056번, 1695번, 21923번,

Swift 5 | 코테/백준 | 골드 - 문제풀이 / / 2022. 6. 3. 22:14

 

 

문제 유형 중, DP의 추천문제들을 풀고 있습니다.

DP2의 문제양이 많아, DP2-1과 DP2-2로 나눕니다. (DP2-1은 여기서 확인할 수 있습니다.)

추천문제 번호 모음은 여기서 확인할 수 있습니다. 골드 문제입니다.

 

DP2-2 추천문제 번호 모음.

문제 풀이를 할 때 마다 계속 추가됩니다.

cmd + F 를 통해 문제번호 찾기를 추천드립니다.

22.06.03 업데이트

22.06.06 업데이트

22.06.07 업데이트

 

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번

developer Eng developer 미국∙영국[dɪˈveləpə(r)] (부동산) 개발업자[개발 회사] (신상품) 개발자[개발 회사] (사진) 현상액 a property developer 부동산 개발 업자[회사] late developer 발육[발달, 성장]..

developer-p.tistory.com

 

백준 Swift 1520번

문제 유형 : DFS + DP

처음에 DFS만으로 푸는 건 풀었다. 혹시나 했지만 역시나 20~30%즈음에서 시간초과...

못풀겠어서 다른 블로그를 찾아보니, DFS와 DP를 합쳐서 푸는 문제였다.

 

보통 DFS를 풀 땐 방문체크를 한다. DP에서 방문체크를 하기 위해선 어떻게 해야 할까?

dp를 -1로 초기화 한 뒤, -1값이라는건 첫방문이라는 뜻이다.

첫방문일 시, dp값을 0으로 바꿔주고, dfs를 다시 시작한다.

첫방문이 아닐 시, 저장된 값을 바로 return해준다. 저장된 값은 몇개의 길이 있는지에 대한 정보를 담고 있다.

 

목적지에 도달했을 때 1값을 return해준다.

하단 그림을 참고하자.

목적지에 도달할 때 1을 리턴해줘서, 탐색하는건 (그림기준) 위에서부터인데, 저장되는건 밑에서부터이다.

출처 - https://wootool.tistory.com/83

난이도 : 골드4

참고 자료 : https://sihyungyou.github.io/baekjoon-1520/ | https://wootool.tistory.com/83

DFS + DP

// MARK: - 1520번(DFS + DP)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])

var arr: [[Int]] = Array(repeating: [], count: M + 1)
arr[0] = Array(repeating: 0, count: N + 1)
for i in 1...M {
    arr[i] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!}
}

var dp: [[Int]] = Array(repeating: Array(repeating: -1, count: N + 1), count: M + 1)

func isValidCoord(_ y: Int, _ x: Int) -> Bool { // 유효범위 체크.
    return (1 <= y && y <= M) && (1 <= x && x <= N)
}

func isEscape(_ y: Int, _ x: Int) -> Bool { // 도착완료 체크.
    return y == M && x == N
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

func dfs(_ y: Int, _ x: Int) -> Int {
//    print(y, x, dp)
    if isEscape(y, x) { // 도착 시,
        return 1
    }
    
//    if dp[y][x] != -1 { // 방문 좌표일 시,
//        return dp[y][x]
//    }
    
    if dp[y][x] == -1 { // 미방문 좌표일 시,
        dp[y][x] = 0 // 우선 값 0으로 초기화.
        for k in 0..<4 {
            let ny = y + dy[k]
            let nx = x + dx[k]
            
            if isValidCoord(ny, nx) && arr[y][x] > arr[ny][nx] { // 유효범위이고, 높이가 낮으면,
                dp[y][x] += dfs(ny, nx)
            }
        }
    }
    
    return dp[y][x] // 방문 좌표일 시,
}

let answer = dfs(1, 1)
print(answer)

Only DFS - 시간초과

 

// MARK: - 1520번(DFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (M, N) = (input[0], input[1])

var arr: [[Int]] = Array(repeating: [], count: M + 1)
arr[0] = Array(repeating: 0, count: N + 1)
for i in 1...M {
    arr[i] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!}
}

//var dp: [[Int]] = Array(repeating: Array(repeating: -1, count: N + 1), count: M + 1)

func isValidCoord(_ y: Int, _ x: Int) -> Bool { // 유효범위 체크.
    return (1 <= y && y <= M) && (1 <= x && x <= N)
}

func isEscape(_ y: Int, _ x: Int) -> Bool { // 도착완료 체크.
    return y == M && x == N
}

let dy = [0, 1, 0, -1]
let dx = [1, 0, -1, 0]

var answer: Int = 0
func dfs(_ y: Int, _ x: Int) {
    if isEscape(y, x) {
        answer += 1
        return
    }
    
    for k in 0..<4 {
        let ny = y + dy[k]
        let nx = x + dx[k]
        
        if isValidCoord(ny, nx) && arr[y][x] > arr[ny][nx] {
            dfs(ny, nx)
        }
    }
}

dfs(1, 1)
print(answer)

 

백준 Swift 2056번

문제 유형 : DP(반복문) / 위상 정렬(Topology Sort)

전에 위상정렬 관련 문제를 풀었었다. 근데 풀이 방법을 잊고 있었다. 위상정렬을 기억하고 있었다면, 이 문제를 보고 바로 알아챌 수 있었을 것 같은데 아쉽다. 결국 다른 블로그를 참고했다.

이 문제는 DP만으로 풀 수 있었고, 위상 정렬을 이용해서도 풀 수 있었다.

 

DP 풀이

미리 받아놓고 나중에 for문을 돌리는 식이 아니다.

1. i번부터 N번까지의 작업을 돌면서,

2. j를 count 개수만큼 선행 관계를 돌면서,

let beforeWorkNum = input[2 + j] // 선행 관계 작업 번호
//  dp[i] = max(dp[i], dp[beforeWorkNum] + time) (ver.1)
dp[i] = max(dp[i], dp[beforeWorkNum]) // (ver.2)

3. 구한 dp값에, i번 작업에 걸리는 시간을 더해주면 된다.

dp[i] += time // i번 작업에 걸리는 시간을 추후에 저장. (ver.2)

4. dp배열의 최대값이 정답이 된다.

위상정렬 풀이

1. 연결된 그래프를 저장한다. 각 작업의 진입차수도 저장한다.

2. 진입차수가 0인 것만 큐에 넣는다.

 

3. 큐가 empty가 될 때까지 돌면서,

3-1. q.popFirst()를 한다. 우선, 해당 작업(node)에 걸리는 시간을 저장한다.

let node = q.popFirst()
completeTimeArray[node] += times[node] // 우선, 해당 작업(현재꺼)에 걸리는 시간 저장.

3-2. 현재 노드(node)와 연결된 노드(nextNode)들을 돌면서,

연결된 노드(nextNode)의 진입차수를 1 감소 시키고,

연결된 노드와 현재 노드의 값중 최대값을 저장한다.

연결된 노드의 진입 차수가 0이라면 큐에 집어 넣는다.

for nextNode in graph[node] { // 현재 노드와 연결된 노드들을 돌면서,
    indegree[nextNode] -= 1 // 연결된 노드의 진입 차수를 -1씩 감소.
    completeTimeArray[nextNode] = max(completeTimeArray[nextNode], completeTimeArray[node]) // 다음꺼 걸리는 시간, 현재꺼 걸리는 시간

    if indegree[nextNode] == 0 { // 진입 차수가 0이라면,
        q.pushLast(nextNode) // 큐에 저장.
    }
}

 

난이도 : 골드5

참고 자료 : https://m.blog.naver.com/ndb796/221236874984 | https://steady-coding.tistory.com/182

큐 - 위상정렬

// MARK: - 2056번(큐 - 위상정렬)
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 N = Int(readLine()!)!
var graph: [[Int]] = Array(repeating: [], count: N + 1)
var times: [Int] = [-1] + Array(repeating: 0, count: N) // 해당 작업에 걸리는 시간들 저장.
var indegree: [Int] = [-1] + Array(repeating: 0, count: N) // 각 작업들의 진입 차수 저장.

for i in 1...N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    times[i] = input[0]
    let count: Int = input[1]
    indegree[i] = count // 진입 차수 저장.
    
    for j in 0..<count {
        let beforeWorkNum = input[2 + j] // 선행 관계 작업 번호
        graph[beforeWorkNum].append(i)
    }
}

let q: Dequeue<Int> = Dequeue([])
for i in 1...N {
    if indegree[i] == 0 {
        q.pushLast(i)
    }
}

var completeTimeArray: [Int] = [-1] + Array(repeating: 0, count: N) // 각 작업을 완료하는데 걸리는 시간.
while !q.isEmpty {
    let node = q.popFirst()
    completeTimeArray[node] += times[node] // 우선, 해당 작업(현재꺼)에 걸리는 시간 저장.
    
    for nextNode in graph[node] { // 현재 노드와 연결된 노드들을 돌면서,
        indegree[nextNode] -= 1 // 연결된 노드의 진입 차수를 -1씩 감소.
        completeTimeArray[nextNode] = max(completeTimeArray[nextNode], completeTimeArray[node]) // 다음꺼 걸리는 시간, 현재꺼 걸리는 시간
        
        if indegree[nextNode] == 0 { // 진입 차수가 0이라면,
            q.pushLast(nextNode) // 큐에 저장.
        }
    }
}

print(completeTimeArray.max()!)

반복문 - DP

// MARK: - 2056번(DP - 반복문)
let N = Int(readLine()!)!
var dp: [Int] = [-1] + Array(repeating: 0, count: N)

for i in 1...N { // 작업을 돌면서,
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let time = input[0] // i번 작업에 걸리는 시간.
    let count: Int = input[1] // 선행 관계에 있는 작업 개수
    
//    dp[i] = time // i번 작업에 걸리는 시간을 우선 저장. (ver.1)
    
    for j in 0..<count { // 선행 관계를 돌면서,
        let beforeWorkNum = input[2 + j] // 선행 관계 작업 번호
//        dp[i] = max(dp[i], dp[beforeWorkNum] + time) (ver.1)
        dp[i] = max(dp[i], dp[beforeWorkNum]) // (ver.2)
    }
    dp[i] += time // i번 작업에 걸리는 시간을 추후에 저장. (ver.2)
}

print(dp.max()!)

 

백준 Swift 1695번

문제 유형 : DP(재귀, 반복문) / LCS(최장 공통 부분 수열)

고민하다보니 LIS가 생각났다. 근데 다시 생각해보니 increase는 전혀 상관이 없었다. 그러다 결국 찾지 못하고 다른 블로그를 참고했다.

 

풀이

arr과 reverseArr의 LCS를 구하면 된다.

숫자가 같다면, dp[i][j] = dp[i - 1][j - 1] + 1

숫자가 다르다면, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) // 이전 행의 같은 열, 같은 행의 이전 열 중 큰 값을 저장.

그 다음, 총 길이 N에서 LCS값인 dp[N][N]을 빼면 된다.

 

백준 Swift 1695번 고민.

 

난이도 : 골드4

참고 자료 : https://ddiyeon.tistory.com/67 | https://t.ly/iQq7 | https://mapocodingpark.blogspot.com/2020/07/1695.html

재귀

// MARK: - 1695번(DP - 재귀함수)
let N = Int(readLine()!)!
var arr: [Int] = [-1] + readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [[Int]] = Array(repeating: Array(repeating: -1, count: N + 1), count: N + 1)

func topDown(_ start: Int, _ end: Int) -> Int {
    if start >= end {
        return 0
    }
    
    if dp[start][end] != -1 {
        return dp[start][end]
    }
    
    if arr[start] == arr[end] { // 시작과 끝 값이 같을 때,
        dp[start][end] = topDown(start + 1, end - 1)
    }
    else { // 다를다면,
        dp[start][end] = min(topDown(start + 1, end), topDown(start, end - 1)) + 1 // min(우측에 좌측값을 넣을 때, 좌측에 우측값을 넣을 때) + 1
    }
    
    
    return dp[start][end]
}

let answer = topDown(1, N)
print(answer)

반복문

// MARK: - 1695번(DP - 반복문)
let N = Int(readLine()!)!
var arr: [Int] = [-1] + readLine()!.split(separator: " ").map{Int(String($0))!}
//var rArr = arr.reversed() // arr을 뒤집음.

var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)

for i in 1...N { // 뒤부터 돈 것(rArr)과,
    for j in 1...N { // 앞부터 돈 것(arr)에서,
        if arr[N + 1 - i] == arr[j] { // 숫자가 같다면,
            dp[i][j] = dp[i - 1][j - 1] + 1
        }
        else { // 숫자가 다르다면,
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) // 이전 행의 같은 열, 같은 행의 이전 열 중 큰 값을 저장.
        }
    }
}

print(N - dp[N][N])

 

 

백준 Swift 21923번

문제 유형 : DP(재귀, 반복문)

- 느낀점, 설명설명~~~

난이도 : 골드4

 

반복문

import Foundation
 
반응형
저작자표시 비영리 변경금지
Swift 5 | 코테/백준 | 골드 - 문제풀이 관련 글
글 더보기

티스토리툴바