[JS] - DP(Dynamic programming) 동적계획법 알고리즘

동적계획법이란

• 큰 문제를 작은문제로 나누어 푸는 방법~!
• 작은 문제가 반복이 일어나는 경우
• 작은 문제의 결과 값이 항상 같다

Memoization(메모이제이션)
한번 계산한 작은 문제를 저장해놓고 다시 사용
속도를 향상시킨다.~!

Dynamic and Conquer(분할정복) 차이점

• 작은문제가 중복 없이 해결

예제 (최대부분증가수열)

• 첫번째 줄에 부분증가수열의 최대 길이를 출력
  원소 2,7,5,8,6,4,7,12,3 가장 길게 증가하도록 원소들을 차례대로
  뽑기 => 2,5,6,7,12

function solution(arr){
            let answer = 0;
            let dy=Array.from({length:arr.length}, ()=>0);
            dy[0] = 1;  //첫번째 1로 초기화 
            for(let i=1; i<arr.length;i++){
                let max = 0;
                for(let j=i-1; j>=0; j--){
                    if(arr[j] < arr[i] && dy[j]>max){
                        max=dy[j];
                    }
                }
                dy[i] = max+1;
                answer = Math.max(answer, dy[i]);
            } 
            return answer;
        }

    let arr = [5, 3, ,7 ,8 ,6,2,9,4];
    console.log(solution(arr));

예제 (동전교환)

function solution(m, coin){
            let answer = 0;
            let dy = Array.from({length:m+1}, ()=>1000);
            dy[0] = 0;
            for(let i=0;i<coin.length; i++){
                for(let j=coin[i]; j<=m; j++){
                    dy[j] = Math.min(dy[j], dy[j-coin[i]]+1);
                }
            } 
            answer=dy[m];
            return answer;
        }

    let arr = [1, 2, 5];
    console.log(solution(15,arr));

예제 (백준 - 성냥개비문제)

문제3687

• dp 문제 해결순서

1. 문제해결 요구에 따라서 dp배열에 담길 컨셉 정하기

2. 초기 조건 구하기

3. 이전의 dp값과 기존의 배열 값을 조합하여 계속 dp값을 구해나가기

• 문제풀이

1. 최소값을 가지는 성냥개비 배열 생성

2. 최대값을 가지는 성냥개비 배열 생성

3. 반복되는 조건 찾기~!
   => 이전의 dp값과 초기조건에 대한 새로운 배열 add!를 활용해 dp값을 찾는다.
   초기조건 = ["1","7","4","2","0","8"]

• 가장 큰 숫자

홀 수 일 때 : 맨 앞은 7, 뒤에 나오는 숫자들은 1
짝수 일 때 : 모두 1

function answer(n,arr){ 
            let num_min = [0,0,1,7,4,2,6,8,10];  //최소값 초기화
            let num = [0, 0, 1, 7, 4, 2, 0, 8, 10];
            let Min_Dp = Array.from({length:101} , () => Infinity);
            let maxDp = Array.from({length:101} , () => "");
            let add = ["1","7","4","2","0","8"];  //최소값에서 사용하는 최소 값을 가지는 성냥개비 숫자
            let add2 = ["0","0","1","7","4","2","6","8"]; //최대값
            //DP 최소값 초기화
            for(let i=0; i<9; i++){
                Min_Dp[i] = num_min[i];
            }  
            //초기값 이후 부터 값 DP실행 
            for(let i=9;i<=100;i++) {
                for(let j=2;j<=7;j++) {
                    let value = Min_Dp[i-j]+add[j-2];  // 글자두개 str로 이어붙이기
                    //console.log("값확인",i,value , i-j);
                    Min_Dp[i] = Math.min(parseFloat(value), Min_Dp[i]);
                }
		    }
            maxDp[2] = "1";
            for(let i=3;i<=100;i++) {
                let line = "";
                if(i%2==0) { //짝수면
                    for(let k=0;k<i/2;k++) {
                        line += "1";
                    }
                } else { 
                    let val = parseInt(i/2-1); 
                    for(let k=0;k<val;k++) {
                        line += "1";
                    }
                    line = add2[i-(val*2)] + "" + line;  
                    //line = "7" + "" + line;
                    console.log("test", add2[i-(val*2)],line)
                    //console.log("홀수", add2[i-(val*2)] , i  ,(val*2));
                }
                maxDp[i] = line;
            }
            for(let i=0;i<n;i++) {
			    M = arr[i];
                console.log(Min_Dp[M] , maxDp[M]); 
		    }  
            for(let i=0;i<11;i++) { 
                console.log(i,Min_Dp[i] , maxDp[i]); 
		    } 
        }