동적프로그래밍(Dynamic Programming) 이란?
- 문제를 푸는데 완전 탐색을 적용하면 비효율적인 탐색 속도를 보인다.
- 예로 피보나치수열을 보자, 보통 재귀함수로 많이 풀게된다.
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
private static fibonacci(int n) {
if (n = 0 || n = 1) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
이미 계산한 fibo(3) 이하의 수를 여러번 중복 계산하게 된다.
- 수가 커질수록 중복 계산 수는 기하 급수적으로 늘게 된다.
- 동적 프로그래밍이란 메모이제이션(memoization)을 이용한 기법
- 말이 거창한데 쉽게 말하면 중간 계산결과를 저장해놓고 그 값이 호출되면 그대로 가져다 쓰는 것뿐임
- 문제에서 제시된 범위에 따라 메모이제이션 배열 초기화
- 숫자 범위에 따라 int 혹은 long 배열을 만들어 준다.
- 값이 0 이상이라면 -1 혹은 나올 수 없는 값으로 초기화해서 값이 기록되지 않았음을 표현
- 재귀의 종료 조건에 메모이제이션 조건 추가
- 부분 문제에 대한 답을 구한 후 메모이제이션 배열에 기록
return mem[n] = fibonacci(n-2) + fibonacci(n-1);- 메모이제이션 조건과 기존에 있던 종료 조건의 순서는 문제마다 다르게 적용 가능하다.
- 종료 조건에서 비용이 큰 연산이 있다면 메모이제이션 검사를 우선으로 하는 것이 좋다.
if (mem(n) != -1 ) return mem[n];
if (n == 0 || n == 1 ) return 1;- 동적 계획법으로 피보나치 구현하는 경우
private static final long[] mem = new long[101];
private static long fibonacci(int n) {
if (mem[n] != -1) {
return mem[n];
}
if (n == 0 || n == 1 ) {
return 1;
}
return mem[n] = fibonacci(n-1) + fibonacci(n-2);
}
public static void main(String[] args) {
Arrays.fill(mem, -1);
System.out.println(fibonacci(10));
}
위를 재귀로 푸는경우 n이 50일 때 재귀가 20억 번이 넘거가게된다. 방심하지 말자
- 모든 재귀 문제가 동적 프로그래밍으로 변환되는 것은 아니므로 중복이 발생하지 않는 재귀 문제는 메모이제이션 처리 한다고 하더라도 실제로 재사용되지 않기 떄문에 효율적이지 않다.
- 반드시 중복되는 부분 문제가 많이 발생하는지 따져 보자.
- 방식으로 Top-Down, Bottop-Up 방식 2가지가 있다.
참조
https://code-lab1.tistory.com/7
취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 - 자바편
