[알고리즘] 알고리즘 뽀개기 (2) : 다이나믹프로그래밍

알고리즘 뽀개기 Step 2 : 다이나믹프로그래밍

알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :)

추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다.

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 의미
• 다이나믹 프로그래밍의 조건
  1. Overlapping Subproblem (문제를 작은 문제들로 쪼개어 풀 수 있다)
  2. Optimal Substructure (문제의 정답을 작은 문제들의 정답으로 구할 수 있다)
• 각 작은 문제는 한번만 푼다.
• Optimal Substructure를 만족하기 때문에, 같은 작은 문제일 경우 순서에 상관없이 구할 때 마다 정답이 같다.
  • 구한 특정 작은 문제의 정답을 저장하여 활용한다. (Memoization)
• 푸는 두가지 방법
  • Top-down
  • Bottom-up

Top-down

큰 문제를 작은 문제로 나누며, 재귀 호출을 이용해 문제를 푼다.

1. 문제를 작은 문제로 나눈다.
2. 작은 문제를 푼다.
3. 작은 문제들의 정답으로 문제의 정답을 푼다.

Bottom-up

주어진 밑단부터 접근하기 시작한다.

1. 문제를 크기가 작은 문제부터 차례대로 푼다.
2. 문제의 크기를 조금씩 크게 만들면서 문제의 풀이와 가까워진다.
3. 작은문제를 풀면서 왔기에 큰 문제는 항상 풀 수 있다.

복습 문제

1,2,3 더하기 (9095번)

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

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val T = readLine().toInt()
    var N = 0
    val list = MutableList(11) { i -> i }

    list[1] = 1 //1
    list[2] = 2 //2
    list[3] = 4 //3

    for (iter in 1..T) {
        N = readLine().toInt()
        for (i in 4..N) {
            list[i] = list[i - 3] + list[i - 2] + list[i - 1]
        }
        println(list[N]) //백준 정말 개복치가 따로 없다... line 떼야하는거 때문에 한참 시간썼다...
    }
}