개요

다이나믹 프로그래밍(Dynamic Programming)은 문제를 더 작은 문제로 나누어 해결하는 알고리즘 기법 중 하나이다.

다이나믹 알고리즘에 대해 알아보고 코틀린에서 다이나믹 프로그래밍을 구현하는 법에 대해 글을 작성하겠다.

다이나믹프로그래밍이란

다이나믹 프로그래밍의 핵심 아이디어는 큰 문제를 작은 문제로 나누어 해결한다는 것

따라서, 처음에는 작은 문제부터 시작하여 그것들의 해를 구하고, 이를 이용하여 보다 큰 문제들의 해를 구하는 방식으로 전체 문제를 해결

다이나믹 프로그래밍 구현은 다양한 방법으로 해결 가능한데 대표적으로

Memorization, Bottum-Up, Top-Down 등의 방법을 사용하여 해결할 수 있습니다.

• Memorization은 이전에 계산한 값을 저장하고, 이를 다음 계산 시 재사용하는 방식
• Bottum-Up 방식은 작은 문제부터 차근차근 해결하여 전체 문제의 해를 구하는 방식
• Top-Down 방식은 전체 문제를 맨 처음부터 시작하여 작은 문제로 나누어 해결하는 방식

다이나믹프로그래밍을 잘 사용하면 코드의 가독성과 유지보수성이 높아지며, 성능도 개선된다.

하지만 다이나믹 프로그래밍을 적용하기 위해서 필요한 조건이 있는데

1. 최적 부분 구조(Optimal Substructure) 인가?

• 전체 문제의 답을 부분 문제의 답을 이용하여 풀 수 있는 구조인가

1. 중복되는 부분 문제(Overlapping subproblem) 인가?

• 부분 문제들에 중복되는 부분들이 있는 문제

위 조건을 만족하는 문제에서 dp적용이 효율적으로 가능하다.

DP 알고리즘 추천 문제 (Kotlin)

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

fun main() {
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(" ").map { it.toInt() }
    val tmp = (1..n).joinToString("")
    findNew(tmp,"",m)
}

fun findNew(str: String, currentStr: String, m: Int) {
    if (m == 0){
        println(currentStr.trim())
        return
    }
    for ((i,value) in str.withIndex()){
        val remain = str.substring(0,i) + str.substring(i+1)
        findNew(remain, "$currentStr $value", m-1)
    }
}

---

추가예정