Dynamic Programming & Greedy Algorithms

About DP(Dynamic Programming)

 

우선 뭔가 명칭에서 있어 보인다. 역동적인 프로그래밍 이라니..

실제로 고안자인 벨만은 있어보여서 dynamic 이란 단어를 선정 했다고 한다.

저서의 서문을 보면 연구소에서 펀딩을 받기에 좋은 단어라 선택했다고 나온다.

저서에는 다음과 같이 DP 를 정의 하고 있다.

어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고

과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다.

DP는 알고리즘 이라기보단 하나의 방법론에 가까운데 Optimal Substructure 라고

불리는 구조에 DP를 활용해야 좋은 효과를 얻을수 있다.

뭔가 구하기위해서 했던 계산을 계속해서 반복하는류에 문제들이 적용 대상이라

할수있는데 피보나치 수열, 배낭문제, 최단경로찾기등이 이를 적용해보고 테스트

해볼수있는 예시들이다.

fibonacci

피보나치 수열은 재귀를 이용하여 구현할수 있는데 이를 동적 프로그래밍 방법으로

전환하고 성능 테스트를 해보는것이 주된 목적이다.

• 재귀를 DP 방식으로 변환

• 재귀 vs DP 성능 테스트.

재귀는 시간 복잡도가 O(n) 이다. 실제 성능 테스트를 해보면 10~20번째 피보나치 수를

구하는데 걸리는 시간 차이는 미미하지만 30번째로 정도 되면 체감할정도로 성능이 저하되는것을

확인할수 있다.

    function re_fb(n) {
        if (n < 2) {
            return n;
        } else {
            return re_fb(n-1) + re_fb(n-2);
        }
    }

    function dy_fb(n) {
        let val;
        if ((n-2) <= 0) {
            return 1;
        } else {
            val = [1, 1,...new Array(n-2).fill(0)];
                for (let i = 2; i <= n; ++i) {
                    val[i] = val[i-1] + val[i-2];
                }
            return val[n-1];
        }
    }

    function getPerf(method,v) {
        var start = performance.now();
        (method)(v)
        var end   = performance.now();
        return (end - start).toFixed(3);
    }

    function comparePerf(n) {
        var recursion = getPerf(re_fb, n);
        var dynamic   = getPerf(dy_fb, n);
        var str;       

        recursion > dynamic ? 
        str = `dynamic ${dynamic} m/s recursion ${recursion} m/s gap ${(recursion - dynamic).toFixed(3)}` :                    
        str = `recursion ${recursion} m/s dynamic ${dynamic} m/s gap ${(dynamic - recursion).toFixed(3)}` 
        return str;
    }

Memoization vs Dynamic programming

메모이제이션은 Top-down 방식 동적 프로그래밍(DP)은 bottom-up 방식으로 문제를 해결한다.

메모이 제이션은 함수 호출 비용이 드는 반면 DP은 함수 호출이 없다는점이 다르다.

하지만 부분 문제의 해를 배열에 저장하는 아이디어는 본질적으로 같다고 볼수 있다.

메모이제이션은 스택 오버 플로우에 위험이 있지만 DP 는 재귀 만큼에 깊이기때문에

DP에는 이러한 위험이 없다.

메모이제이션은 해시 테이블을 필요로 한다. 그래서 추가 공간이나 일부 조회시간등이 필요

할수 있다.

Time Complexity

시간복잡도의 결과는 예상되는 결과 이기때문에 명확 하지 않다.

시간복잡도는 연산의 실행 횟수를 카운트

연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현된다.

데이터의 크기가 같더라도 실제 데이터에 따라서 달라질수 있다.

점근적 표기법을 사용한다.

n(n - 1) / 2 + 5 시간복잡도가 계산된다고 했을때 빅오 표기법으로

n^2 만 남게 된다.

유일한 분석법도 아니고 가장 좋은 분석법도 아니지만 간단하고

알고리즘의 실행환경에 비의존적이다 보니 광범위하게 많이 사용되는것이

시간 복잡도 개념이다.

case 1

n에 관계없이 상수 시간이 소요된다. 이경우 알고리즘의 시간복잡도는 O(1)

    function get(n) {
        let arr = [];
        return arr[n];
    }

case 2

arr.length가 5라면 즉 n은 5 이다 n번만큼 for문에서 실행되는것이니까. 이경우

알고리즘의 시간복잡도는 O(n) 이다

    function sum() {
        let arr = [1,2,3,4,5];
        let sum = 0;
        for (let i = 0; i < arr.length; i++) {
            sum += arr[i]
        }
    }

case 3

최선 최상 보통의 결과가 존재한다.

이경우 실행횟수는 최악의 경우가 O(n) 이된다.

    //순차 탐색
    function search(v) {
         let arr = [1,2,3,4,5];
         let sum = 0;
        for (let i = 0; i < arr.length; i++) {
            if(arr[i] == v) {
                return i;
            }
        }
        return -1;
    }

case 4

최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는

n(n-1) 에서 차수를 날리고 빅오표기법으로 표시하면 O(n^2) 가 된다

    function is_distinct() {
        let arr = [1,2,3,4,5,5],
            n = arr.length;

        for (let i = 0; i < n-1; i++) {
            for (let j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    return false;
                }
            }
        } 
    }

time complexity Order

1 < log n < n < n log n < n^2 < n^3 <넘사벽< 2^n < n!(팩토리얼)

shortest path

Longest increasing subsequence (가장 긴 증가 수열 문제)

function Lis(arr) {
    let lisArr = new Array(arr.length).fill(0),
        result = -1,
         index = -1,
         i,j;

    for (i = 0; i < arr.length; i++) {
        let seq = -1;
        for (j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                if (seq == -1 || seq < lisArr[j] + 1) { //연속되는지 확인
                    seq = 1 + lisArr[j];  //몇번 연속인지 저장
                }
            }
        }
        if (seq == -1) {
            seq = 1; // 초기값
        }
        lisArr[i] = seq; //해당 위치에 순서를 저장
    }

    //최대 몇까지 증가되었는지의 경우 체크
    for (i = 0; i < lisArr.length; i++) {
        if (result < lisArr[i]) {
            result = lisArr[i];
            index  = i;
        }
    }
    //연속되는 값 추출
    let path = arr[index] + " ";
    let res =  result - 1;
    for (i = index - 1; i >= 0; i--) {
        if (lisArr[i] == res) {
            path = arr[i] + " " + path;
            res--;
        }
    }

    console.log(`lis :${result}`);
    console.log(`elements : ${path}`);

}

Lis([2,10,6,1,21,9,55,34,67,71,89,0]);

//2,6,9,34,67,71,89   lis : 7

About Greedy Algorithm

지금 이 순간에 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다.

그리디 알고리즘은 한번의 선택이 다음 선택에는 전혀 무관한 값이여야하고

매 순간의 최적해가 문제에 대한 최적해여야 한다는것

이2가지 특성을 가지는 문제를 해결하는데 강점이 있다.

또한 최적해를 보장하지않고 어느정도 적당한 수준의 해답을 알려준다.

Coin Chage Problem

거스름돈 문제의 경우 배수관계가 성립할때 가능한데 예를 들어

1원 7원 10원 동전이 있을경우 14원을 만들려면 7원짜리 2개가 있으면 되는데

탐욕알고리즘을 수행하면 10원짜리 1개와 1원짜리 4개인 결과 값을 알려준다.

function CoinChange(cost) {
    let  coin = [100, 50, 10],
        count = [0, 0, 0],
            i = 0,
         flag = false;

        while (i < 3) {
            if (coin[i] > cost) {
                i++;
            } 
            else if (coin[i] < cost) {
                cost -= coin[i];
                count[i]++;
            } 
            else {
                flag = true;
                count[i]++;
                break;
            }
        }
        if (flag) {
        console.log(`${coin[0]}원 동전 ${count[0]} 개 ${coin[1]}원 동전 ${count[1]} 개 ${coin[2]}원 동전 ${count[2]} 개`)
        } 
        else {
            console.log("stop")
                flag = false;
        }
}

Knapsack Problem

class GreedyKnapsack {
    constructor(n) {
        this.profit = Array.from(new Array(n), x => x = Math.round(Math.random() * 48 + 22));
        this.weight = Array.from(new Array(n), x => x = Math.round(Math.random() * 44 + 8));
        this.takeit = new Array(n);
        this.result = [];
    }
    //단가 정렬 - bubble sort;
    unitPriceSort() {
        let profit = this.profit,
            weight = this.weight,
            temp,temp1;

        for (let i = 0; i < profit.length; i++) {
            for (let j = 1; j < (profit.length - 1); j++) {
                let x = profit[j - 1] / weight[j - 1],
                    y = profit[j] / weight[j];

                if (x <= y) {
                             temp = profit[j - 1];
                    profit[j - 1] = profit[j];
                        profit[j] = temp;

                            temp1 = weight[j - 1];
                    weight[j - 1] = weight[j];
                        weight[j] = temp1;
                }
            }
        }
    }
    //배낭 용량
    capacity(m) {
        this.clear();
        this.unitPriceSort();

        let profit = this.profit,
            weight = this.weight,
            j,total;

        this.takeit = new Array(profit.length).fill(0);

        total = m;

        for(j = 0; j < profit.length; j++) {

            if (weight[j] <= total) {
                this.takeit[j] = 1.00;
                total -= weight[j];
            } 
            else {
                break;
            }
        }
        //용량이 맞아떨어지지않으면 소수단위로 나눠담는다.
        if (j < profit.length) {
            this.takeit[j]  = total / weight[j];
        }
    }
    //출력
    toString() {

        for (let i = 0; i < this.profit.length; i++) {
            this.result.push({
                    profit : this.profit[i],
                    weight : this.weight[i],
                    unitPrice : (this.profit[i] / this.weight[i]).toFixed(3),
                    takeit : this.takeit[i]
                });
        }
        return console.table(this.result);
    }
    //결과 누적 초기화
    clear() {
        this.result = [];
    }
}

var g = new GreedyKnapsack(10); // 기본값 설정
g.capacity(50); //배낭 용량 설정
g.toString(); // 결과 테이블 형식
g.capacity(120); 
g.toString();