동적 계획법(Dynamic Programming, DP) - DP
DP란 무엇일까? 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 해결한 후, 그 결과를 저장하여 전체 문제를 효율적으로 해결하는 방법이다. 예를 들어, 큰 퍼즐을 맞출 때, 각 조각을 따로 기억해둔다면 다시 같은 조각을 찾지 않아도 된다.
DP의 핵심 개념
- 부분 문제(Overlapping Subproblems) : 큰 문제를 해결하는 과정에서 동일한 작은 문제가 여러 번 반복되는 경우가 있다.
- 최적 부분 구조(Optimal Substructure) : 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있을 때, DP를 적용할 수 있다.
대표 문제 : 계단 오르기
- 문제 설명 : 계단이 총 n개 있고, 한 번에 1계단 또는 2계단씩 오를 수 있을 때, 계단을 모두 오르는 방법의 수를 구하시오.
- 예시 : n = 3일때, 가능한 경우는
- 1,1,1
- 1,2
- 2,1
총 3가지 방법
- 문제 해결을 위한 아이디어
- 계단 오르기 문제는 작은 문제(예 : n-1 계단을 오르는 방법, n-2 계단을 오르는 방법)로 나누어 생각할 수 있다.
- 점화식 : n 번째 계단에 도달하는 방법의 수는 dp[n] = dp[n-1] + dp[n-2] 이다. 왜냐하면 마지막에 한 계단을 오르는 경우와 두 계단을 오르는 경우로 나눌 수 있기 때문이다.
- 기본 조건 : dp[0] = 1 (아무 계단도 오르지 않은 경우를 1가지 방법으로 간주) / dp[1] = 1 (첫 번째 계단까지 오르는 방법은 1가지)
1. 반복적(Bottom-Up) 방식으로 DP 구현하기
fun climbStairs(n: Int): Int {
// n이 0 또는 1인 경우 바로 반환
if (n <= 1) return 1
// dp 배열 생성: dp[i]는 i번째 계단까지 도달하는 방법의 수
val dp = IntArray(n + 1)
dp[0] = 1
dp[1] = 1
// 2번째 계단부터 n번째 계단까지 방법의 수를 구함
for (i in 2..n) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
}
fun main() {
val n = 5 // 예를 들어 계단이 5개인 경우
println("계단 $n개를 오르는 방법의 수: ${climbStairs(n)}")
// 출력 예시: 계단 5개를 오르는 방법의 수: 8
}
2. 재귀와 메모이제이션을 활용한 방식
fun climbStairsRecursive(n: Int, memo: MutableMap<Int, Int> = mutableMapOf()): Int {
// n이 0 또는 1이면 바로 반환
if (n <= 1) return 1
// 이미 계산된 값이면 바로 반환
if (memo.containsKey(n)) return memo[n]!!
// 재귀 호출과 메모이제이션
memo[n] = climbStairsRecursive(n - 1, memo) + climbStairsRecursive(n - 2, memo)
return memo[n]!!
}
fun main() {
val n = 5
println("재귀적 접근: 계단 $n개를 오르는 방법의 수: ${climbStairsRecursive(n)}")
// 출력 예시: 재귀적 접근: 계단 5개를 오르는 방법의 수: 8
}
// 같은 계산을 반복하지 않도록, 한 번 계산한 결과를 memo에 저장한다. 이렇게 하면, 재귀 호출의 중복을 피할 수 있다.
'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글
Kotlin 연습하기(10) - 그리디 알고리즘 (2) | 2025.04.14 |
---|---|
Kotiln 연습하기(9) - DFS / BFS (1) | 2025.04.11 |
Kotlin 연습하기(6) - 선형/이진 검색 (0) | 2025.04.04 |
Kotlin 연습하기(5) - 버블정렬 (0) | 2025.04.02 |
Kotlin 연습하기(4)-재귀함수 (0) | 2025.03.31 |