소개
동적 프로그래밍 문제를 풀기 전 간단하게 개념에 대해 알아보는 노트이다.
동적 계획법이란?
큰 문제를 작은 문제로 나누어서 푸는 문제를 일컫는 말이다.
분할 정복과 다른점이?
거의 비슷하지만 결정적인 차이가 있다. 바로 작은 문제가 중복이 일어나는지 안일어나는지 이다.
•
분할정복 : 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법 ( 작은 문제의 반복 x )
•
동적 프로프로그래밍 : 작은 부분문제들이 반복되는 것(답이 바뀌지않음) 을 이용해 풀어나감
방법
모든 작은 문제들을 한번만 풀어야한다.
따라서 정답을 구한 작은 문제를 어딘가에 저장하고 큰 문제를 풀 때 그 해답을 다시 이용한다.
조건
•
작은 문제가 반복해서 일어남
•
같은 문제는 구할때 마다 정답이 같음
Memorization
반복되는 결과값이 저장되고 다시 활용하는 방식을 말한다
ex ) 피보나치 수열
•
1, 1, 2, 3, 5, 8 ... 이러한 수열을 이루며 값은 고정되어 있다
•
재귀함수로 간단하게 구할 수 있지만, 값이 커지면 계산 수가 급격하게 늘어나 쉽지않다.
또한 이렇게 fibonacci를 재귀함수로 풀게될 경우, 위의 그림처럼 동일한 작업을 반복해서 하게된다.
위의 문제를 동적 프로그래밍으로 풀면
fun main(){
println(memorization(10))
}
fun memorization(n:Int) : Int{
val list = MutableList<Int>(n+2){i->i}
list[0] = 1
list[1] = 1
if(n < 2) return list[n]
for(i in 2 until n+1) list[i] = list[i-2] + list[i-1]
return list[n]
}
Kotlin
복사
n번째 Fibonacci 수열을 구하는 문제 를 동적 프로그래밍으로 푼 코드입니다.
•
0~1 번째 수열은 항상 1이다.
•
2번째 수열의 결과값을 0~1의 수열로 구하고 값을 저장해 다시 활용한다.
Bottom-up 과 Top-down
1. Bottom-up
•
작은 문제 → 큰 문제 순서로 해결하는 방식
fun bottomUp(n:Int) : Int{
if(n <= 1) return n
var fir = 0
var sec = 1
var next = 0
for( i in 0 until n-1){
next = fir+sec
fir = sec
sec = next
}
return next
}
Kotlin
복사
2. Top-down
•
재귀함수로 자주 사용함
•
큰 문제를 풀 때 작은 문제가 풀리지않았으면 그 때 작은문제를 푼다.
fun topDown(n:Int) : Int{
val list = MutableList<Int>(n+2){i->i}
list[0] = 1
list[1] = 1
if(n < 2) return list[n]
list[n] = topDown(n-1) + topDown(n-2)
return list[n]
}
Kotlin
복사
어떤 방식이 더 좋은가?
정답이 없음
Top-down의 경우 소스의 가독성이 증가하나, 작성이 어려움
Bottom-up의 경우 소스의 가독성이 저하될 수도있음?
어차피 편한방식으로 하면된다