Swift DP

Swift DP

 

미적분이나 기하 및 벡터에 비해서 점화식에 유독 약했는데, DP는 점화식이 베이스.

 

알고리즘은 시험 전에 문제를 많이 풀고 봐야 그 감각이 있어서 쉽게 풀 수 있다고 생각함.

 

 

샘플문제

 

1. 1로 만들기

 

점화식을 이용하던데, 특정한 작은 값을 정해서 직접 그러보면 문제를 만드는데 도움이 많이 된다.

또한, 보텀업 방식으로 계산하는게 조금 더 이득이 있다고 하고, 엄청 어렵지도 않으니까 한번 해보자.

비슷한 문제를 백준에서 찾아 풀어보자.

 

 

//https://www.acmicpc.net/problem/1463
import Foundation

struct b1463 {
    static func run() {
        // DP를 이용하여 풀어야 합니다.
        let input: Int! = Int(readLine()!) // 1..<1000 정수
        var arr: [Int] = [Int](repeating: 0, count: input+1)
        
        for i in 2..<input+1 {
            arr[i] = arr[i-1] + 1

            if i % 3 == 0 {
                arr[i] = min(arr[i], arr[i/3] + 1)
            }

            if i % 2 == 0 {
                arr[i] = min(arr[i], arr[i/2] + 1)
            }
        }

        print(arr[input])
    }
}

 

 

2. 개미 전사

 

개미 전사 문제에서 그동안 내가 엄청 어려워하던 케이스를 발견했다.

알고리즘을 공부하기 전에는 이런 케이스를 풀때, 뒤 케이스에 따라서 어떻게 처리해야할 지 늘 고민했었다.

작은 케이스를 하나 생각하면 i = 3이라고 가정하면 max(i-1, i-2 + k) 값으로 처리할 수 있다.

그러면 앞쪽 값이 무조건 optimal하다고 가정할 수 있으므로, 이를 기반으로 해결한다.

비슷한 문제를 백준에서 찾아 풀어보자.

 

 

 

3. 바닥 공사

 

대표적인 타일링 문제라고 한다.

타일링 문제를 풀때는 생각보다 어려웠는데, 이번에는 전체 방법의 수를 찾아야 하므로 생각보다 어려웠다.

DP를 공부하기 전에는 가로의 길이를 홀짝으로 나눈 후, 처리했다.

홀수의 경우에는 몫을 찾아서 몫 * 3을 한다음에 뭐 이런 로직으로 풀었는데, 이게 정답인지는 모르겠으나 점화식으로 풀어보자.

점화식으로 푸니 더 좋았다고 생각한다. 근데 이걸 생각하기가 조금 어려울 수도 있겠다..?

 

//https://www.acmicpc.net/problem/11726
import Foundation

struct b11726 {
    
    static func run() {
        // DP를 이용하여 풀어야 합니다.
        
        let input: Int! = Int(readLine()!)
        
        var dp: [Int] = [Int](repeating: 0, count: 1001)
        dp[1] = 1
        dp[2] = 2
        
        if input >= 3 {
            for i in 3...input {
                dp[i] = (dp[i-1] % 10007) + (dp[i-2] % 10007)
            }
        }
        
        print(dp[input] % 10007)
    }
}

 

 

4. 효율적인 화폐 구성

 

와 이건 진짜 어려웠다.

과연 내가 이걸 풀 수가 있을까 싶기도 했다. 문제의 해설을 읽어보아도 쉽게 이해가 가지 않는다.

작은 값부터 차례로 값을 정하는데, 이건 직접 문제를 풀면서 이해하는게 좋겠다.

백준에서 비슷한 문제를 풀어보자