[이것이 코딩 테스트다] chapter 8. DP

 chapter 8. DP 

 

✅ 다이나믹 프로그래밍(DP)에 대해서 알아보자!

 

DP는 학교 수업시간에 피보나치를 공부하면서 계산한 부분을 계산하지 않는 것으로 배웠는데, 그 당시에는 그게 DP인지 몰랐음

알고리즘을 풀면서 DP와 같은 문제들을 잘 못푸는데, 이번에 공부해 보니까 그 사고를 얻어서 조금 자신감도 생김

수능때도 점화식 문제에 유독 너무나도 약했는데, DP는 점화식이 거의 베이스네..?

아무튼 열심히 해보자.

 

 

✅ 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])
    }
}

 

✅ 개미 전사

 

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

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

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

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

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

 

 

✅ 바닥 공사

 

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

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

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)
    }
}

 

 

✅ 효율적인 화폐 구성

 

와 이건 진짜 어려웠다.

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

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

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