동적 프로그래밍

동적 프로그래밍의 규칙

동적 프로그래밍은 재계산을 피하기 위해 이미 계산된 값들을 저장하고 해당 값들을 사용하는 방법이다. 이 방법은 중복 부분 문제들이 존재하고 최적 부분 구조가 존재하는 문제에만 적용할 수 있다.

중복 부분 문제

동적 프로그래밍은 보통 부분 분제의 해결책을 해시 테이블과 배열, 행렬에 저장하며, 이러한 방식을 메모제이션memozation이라고 부른다. 이러한 예를 피보나치 수열의 재귀 메소드에서 찾아볼 수 있다. 시간 복잡도를 O(2^n)에서 O(n)으로 줄일 수 있다.

var cache = {};

function fiboBest(n) {
    if (n <= 1) return n;
    if (cache[n]) return cache[n];
    return (cache[n] = fiboBest(n - 1) + fiboBest(n - 2));
}
fiboBest(10); // 55

최적 부분 구조

어떤 문제의 최적 해결책을 해당 문제의 부분 문제들의 최적 해결책들을 사용해 찾을 수 있을 때 이를 최적 부분 구조라 한다.

 

ex) 걸음 수를 채우는 방법

function waysToCoverSteps(step) {
    if (step < 0) return 0;
    if (step == 0) return 1;

    return waysToCoverSteps(step - 1) + waysToCoverSteps(step - 2) + waysToCoverSteps(step - 3);
}
waysToCoverSteps(12);

시간 복잡도: O(3^n)

 

캐시에 저장

function waysToCoverStepsDP(step) {
    var cache = {};
    if (step < 0) return 0;
    if (step == 0) return 1;

    // check if exists in cache
    if (cache[step]) {
        return cache[step];
    } else {
        cache[step] = waysToCoverStepsDP(step - 1) + waysToCoverStepsDP(step - 2) + waysToCoverStepsDP(step - 3);
        return cache[step];
    }
}
waysToCoverStepsDP(12);

시간 복잡도: O(n)

대표적인 동적 프로그래밍 예

최장 공통 부분 수열 알고리즘

두 개의 수열이 있을 때 두 수열의 가장 긴 공통 부분 수열의 길이를 찾는다.

 

단순 접근법

function LCSNaive(str1, str2, str1Length, str2Length) {
    if (str1Length == 0 || str2Length == 0) {
        return 0;
    }

    if (str1[str1Length - 1] == str2[str2Length - 1]) {
        return 1 + LCSNaive(str1, str2,
            str1Length - 1,
            str2Length - 1);
    } else {
        return Math.max(
            LCSNaive(str1, str2, str1Length, str2Length - 1),
            LCSNaive(str1, str2, str1Length - 1, str2Length)
        );
    }
}

function LCSNaiveWrapper(str1, str2) {
    return LCSNaive(str1, str2, str1.length, str2.length);
}
LCSNaiveWrapper('AGGTAB', 'GXTXAYB'); // 4

시간 복잡도 : O(2^n)

 

동적 프로그래밍 접근법

function longestCommonSequenceLength(str1, str2) {
	 var rowLength = str1.length,
         colLength = str2.length;

 	let matrix = new Array(str1.length + 1);

    for(let i = 0; i <= str1.length; i++){
        matrix[i] = new Array(str2.length + 1).fill(0);
    }

    for (let row = 1; row <= rowLength; row++) {
        for (let col = 1; col <= colLength; col++) {
           if ( str1[row-1] === str2[col-1] ) {
               	 matrix[row][col] = 1 + matrix[row - 1][col - 1];
           }
		   else {
                 matrix[row][col] = Math.max(matrix[row-1][col], matrix[row][col-1]);
           }
        }
    }
    return  matrix[rowLength][colLength];
}

longestCommonSequenceLength('abcd', 'bc');

?? 이해가 안돼 코드가 아니라 알고리즘이 너무 설명이 부족해 책이

시간 복잡도 : O(m*n)

공간 복잡도 : O(m*n)

 

동전 교환 알고리즘

동전의 금액 종류가 S={S1, S2, ...}으로 M개이고 각 금액의 동전이 무한 개로 제공될 수 있다고 할 때, 금액 n을 동전으로 교환하기 위한 동전의 조합은?? 동전 순서는 무시

ex) N=4, M=3, S={1,2,3}이면 가능한 조합의 개수는 4개

 

최적 부분 구조

1) M번째 동전이 포함되지 않는 해결책

2) M번째 동전이 최소 한 개 포함되는 해결책

 

coinChange(S,M,N)이 가능한 동전 조합 수를 세는 함수인 경우 //근데 S 마지막은 왜 안빼지??

coinChange(S,M,N)=coinChange(S,M-1,N)+coinChange(S,M,N-S[m-1)  (S[m-1]은 마지막 제일 큰 동전금액 빼는거야)

 

단순한 접근법

// Returns the count of ways we can sum coinArr which have 
// index like: [0,...,numCoins]
function countCoinWays(coinArr, numCoins, coinValue) {
    if (coinValue == 0) {
        // if the value reached zero, then only solution is
        // to not include any coin
        return 1;
    }
    if (coinValue < 0 || (numCoins <= 0 && coinValue >= 1)) {
        // value is less than 0 means no solution
        // no coins left but coinValue left also means no solution
        return 0;
    }
    //
    return countCoinWays(coinArr, numCoins - 1, coinValue) +
        countCoinWays(coinArr, numCoins, coinValue - coinArr[numCoins - 1]);
}

function countCoinWaysWrapper(coinArr, coinValue) {
    return countCoinWays(coinArr, coinArr.length, coinValue);
}
countCoinWaysWrapper([1, 2, 3], 4);

시간 복잡도: O(n^m)   (m은 동전의 종류 개수, n은 동전으로 교환하고자 하는 합계 금액

공간 복잡도: O(n)

 

동적 프로그래밍 접근법

function countCoinWaysDP(coinArr, numCoins, coinValue) {
    // creating the matrix
    var dpMatrix = [];

    for (var i = 0; i <= coinValue; i++) {
        dpMatrix[i] = [];
        for (var j = 0; j < numCoins; j++) {
            dpMatrix[i][j] = undefined;
        }
    }

    for (var i = 0; i < numCoins; i++) {
        dpMatrix[0][i] = 1;
    }

    for (var i = 1; i < coinValue + 1; i++) {
        for (var j = 0; j < numCoins; j++) {
            var temp1 = 0,
                temp2 = 0;

            if (i - coinArr[j] >= 0) {
                // solutions including coinArr[j]
                temp1 = dpMatrix[i - coinArr[j]][j];
            }

            if (j >= 1) {
                // solutions excluding coinArr[j]
                temp2 = dpMatrix[i][j - 1];
            }

            dpMatrix[i][j] = temp1 + temp2;
        }
    }
    return dpMatrix[coinValue][numCoins - 1];
}

function countCoinWaysDPWrapper(coinArr, coinValue) {
    return countCoinWaysDP(coinArr, coinArr.length, coinValue);
}
countCoinWaysDPWrapper([1, 2, 3], 4);

시간 복잡도: O(m*n)

공간 복잡도: O(m*n)

책 설명 1도없네..

 

편집 거리 알고리즘

길이 m인 문자열 str1과 길이 n인 문자열 str2가 주어졌을 때 str1을 str2로 변환하기 위한 최소 편집 횟수는 무엇인가?

유효한 연산은 1. 삽입, 2. 제거, 3. 교환

 

최적 부분 구조

문자열 str1과 str2의 각 문자가 한번에 하나씩 처리된다면 다음의 경우가 가능하다.

1. 문자가 동일하다: 아무것도 하지 않는다.

2. 문자가 다르다: 재귀적으로 다음 경우를 고려한다.

  삽입: m과 n-1

  제거: m-1과 n

  교환: m-1과 n-1

 

단순한 접근법

function editDistanceRecursive(str1, str2, length1, length2) {
    // str1 is empty. only option is insert all of str2
    if (length1 == 0) {
        return length2;
    }
    // str2 is empty. only option is insert all of str1
    if (length2 == 0) {
        return length1;
    }

    // last chars are same,
    // ignore last chars and count remaining
    if (str1[length1 - 1] == str2[length2 - 1]) {
        return editDistanceRecursive(str1, str2,
            length1 - 1, length2 - 1);
    }

    // last char is not the same
    // there are three operations: insert, remove, replace
    return 1 + Math.min(
        // insert
        editDistanceRecursive(str1, str2, length1, length2 - 1),
        // remove
        editDistanceRecursive(str1, str2, length1 - 1, length2),
        // replace
        editDistanceRecursive(str1, str2, length1 - 1, length2 - 1)
    );
}

function editDistanceRecursiveWrapper(str1, str2) {
    return editDistanceRecursive(str1, str2, str1.length, str2.length);
}

editDistanceRecursiveWrapper('sammie', 'bae');

시간 복잡도: O(3^m)

 

동적 프로그래밍 접근법

function editDistanceDP(str1, str2, length1, length2) {
    // creating the matrix
    var dpMatrix = [];
    for (var i = 0; i < length1 + 1; i++) {
        dpMatrix[i] = [];
        for (var j = 0; j < length2 + 1; j++) {
            dpMatrix[i][j] = undefined;
        }
    }

    for (var i = 0; i < length1 + 1; i++) {
        for (var j = 0; j < length2 + 1; j++) {
            // if first str1 is empty,
            // have to insert all the chars of str2
            if (i == 0) {
                dpMatrix[i][j] = j;
            } else if (j == 0) {
                dpMatrix[i][j] = i;
            } else if (str1[i - 1] == str2[j - 1]) {
                // if the same, no additional cost
                dpMatrix[i][j] = dpMatrix[i - 1][j - 1];
            } else {
                var insertCost = dpMatrix[i][j - 1],
                    removeCost = dpMatrix[i - 1][j],
                    replaceCost = dpMatrix[i - 1][j - 1];

                dpMatrix[i][j] = 1 + Math.min(insertCost, removeCost, replaceCost);
            }
        }
    }
    return dpMatrix[length1][length2];
}

function editDistanceDPWrapper(str1, str2) {
    return editDistanceDP(str1, str2, str1.length, str2.length);
}

editDistanceDPWrapper('sammie', 'bae');