[이것이 코딩테스트다] 8. 다이나믹 프로그래밍

다이나믹 프로그래밍

메모리공간을 사용하여 연산속도를 비약적으로 증가시킬 수 있는 방법

 

 

다이나믹 프로그래밍을 이용하여 해결할 수 있는 대표적 예시

피보나치 수열(그냥 재귀함수로 풀 수 있으나 시간이 매우 많이 듦 > 때문에 이 기법 사용)

만약 완전탐색 알고리즘으로 풀었을때 너무 오래걸리고, 해결하고자 하는 문제에 중복부분이 있다면 다이나믹 프로그램을 사용하는 것을 생각해볼 수 있음

 

 

사용하기 위한 전제조건

큰 문제를 작은 문제로 나눌 수 있다.

작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

 

탑다운/보텀업 방식

- 탑다운 방식: 재귀함수를 이용한 방법으로 큰 문제를 해결하기 위해 작은 문제를 호출

- 보텀업 방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우로 작은문제부터 차근차근 답을 도출

보텀업이 다이나믹 프로그래밍의 전형적인 형태

 

 

다이나믹 프로그래밍 구현 방법

메모이제이션(=캐싱) : 한번 구한 결과를 메모리공간에 보관하고 같은 식을 호출 시 이 결과를 가져옴

                                  재귀함수로 하면 오버헤드가 발생할 수 있다.

                                  시간복잡도 O(N)

                                  일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다.

let arr = [];    //보관용 arr

function fibo(x) {
    if ((x == 1 ) || ( x == 2)) return 1     
    if (arr[x] != undefined ) return arr[x]   //기존에 작업했으면 그걸 호출
    else {
        arr[x] = fibo(x-1)+fibo(x-2) ;
        return arr[x];                       //보관
    }
}

console.log(fibo(8)) ;     //8번째 수가 무엇인가 반환

---

[예제문제] 1로 만들기

1. X가 5로 나누어떨어지면, 5로 나눈다.
2. X가 3으로 나누어떨어지면, 3으로 나눈다.
3. X가 2로 나누어떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

let input = require('fs').readFileSync('input.txt').toString().trim() ;
let x = +input ; 
let cache = {}
let ret ;

function M(x){
	if (cache.hasOwnProperty('x')) {
		return cache.get(x) ;
	}	
	if (x == 1 ) return 0
	ret = M(x-1)
	if (x % 5 == 0) {
		ret = Math.min(ret, M(x / 5))
	}
	if (x % 3 == 0) {
		ret = Math.min(ret, M(x / 3))
	}
	if (x % 2 == 0) {
		ret = Math.min(ret, M(x / 2))
	}
	
	cache[x] = ret + 1
	return cache[x]
}

console.log(M(x));

---

[예제문제] 개미전사

개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

let input = require('fs').readFileSync('input.txt').toString().trim().split(" ").map(Number) ;
let ret = [input[0], input[1]];

for (let i = 1 ; i < input.length ; i++) {
    if ( i == 1 ) ret[1] = Math.max(input[0],input[1]) ;
    else {
        ret[i] = Math.max(ret[i-2]+input[i],ret[i-1]) ;
    }
}
console.log(ret[ret.length-1]);

---

[예제문제] 바닥공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 한다.

let input = require('fs').readFileSync('input.txt').toString().trim() ;
input = +input ;
let arr = [1, 3]

 for (let i = 2 ; i < input ; i++) {
    arr[i] = arr[i-2]*2 + arr[i-1]
 }

 console.log(arr[arr.length-1]%796796) ;