Data Structures & Algorithms with Javascript : Advanced Algorithms

[이전 글]2024.07.29 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Searching Algorithms

Data Structures & Algorithms with Javascript : Searching Algorithms

🥳 드디어 Data Structures & Algorithms with JavaScript의 마지막 장 직전에 도달했다.
마지막 장에서는 dynamic programming (DP)과 greedy algorithms(탐욕 알고리즘)에 대해 다룬다.

DP는 가끔 재귀와 반대되는 문제해결 방식이라고 여겨진다.
재귀적인 접근은 위에서 아래로 작은 문제들을 문제가 완전히 해결될 때까지 반복적으로 푸는 반면에
DP는 아래에서 위로 작은 문제들을 해결하면 더 큰 문제를 푸는 단서가 되어서 이 누적해들을 합쳐서 큰 문제를 해결한다.

반면 탐욕 알고리즘은 현재 가능한 최선의 해결책(local optima)을 찾아서 해결책을 모색한다.
최선의 답을 찾다보면 결론적으로 최상의 해결책(global optimum)을 찾을 수 있다는 알고리즘이다.
탐욕이라는 말은 현재 해결책 중 가장 완벽한 해결책을 골라서 해결하고자 해서 얻은 이름이다.

아직 두루뭉실한 개념 각 알고리즘들에 대해 자세히 살펴보자! 

Dynamic Programming

재귀적으로 문제를 해결하면 깔끔한 풀이가 가능하지만 비효율적이다.

자바스크립트를 포함한 많은 언어들은 효율적으로 재귀함수를 다루지 못한다.

대신 DP를 활용해 재귀적 풀이를 대체할 수 있다.

DP는 문제를 쪼갠 각 결과 값들을 주로 배열로 된 표로 저장하는 방식으로 풀이를 한다.

 

DP로 문제를 해결하는 예시들을 살펴보자.

피보나치수열 

피보나치수열을 dp로 구하는 방식을 살펴보자.

 

다음과 같은 수를 피보나치 수열이라고 한다. 이전 두 값을 더한 값이 다음 값이 되는 수열이다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

 

재귀적으로 함수를 구한다면 다음과 같다.

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

print(recurFib(10);

 

재귀적으로 피보나치수열을 구하는 건 매우 비효율적이다. 다음은 재귀적으로 피보나치 수열을 구할 때 생성되는 트리 형태다.

같은 값이 여러 번 재연산되어야 한다는 걸 알 수 있다.

 

이미 계산했던 값들은 저장해서 재연산을 피할 수 있다면 좀 더 효율적인 알고리즘이 될 거 같다.

DP에 더 가까운 방식으로 구현해 보자.

 

이전에 말했듯이, DP는 해결 가능한 가장 단순한 sub-problem에서 시작해서 그 해결책으로 더 복잡한 문제들을 풀어가며 정답을 찾는 방식이다. 

function dynFib(n) {
    let val = []; // 중간 중간 결과 값을 저장
    for (let i = 0; i <= n; ++i) {
    	val[i] = 0; // 0부터 시작해서 
        }
    	if (n == 1 || n == 2) { 
        	return 1; // 1이나 2면 0+1 인 경우이므로 이른 종료
    	}
        else {
            val[1] = 1;
            val[2] = 2;
        for (let i = 3; i <= n; ++i) {
             val[i] = val[i-1] + val[i-2]; // 이전 두 값들을 더해줘 현재 위치에 넣어준다.
        }
    	return val[n-1];
    }
}

 

이제 한번 두 알고리즘들의 런타임 비교해 보자. 확실히 20 이상의 피보나치 값을 구하고자 할 때 DP가 더 효율적이다.

let start = new Date().getTime();
print(recurFib(20));
let stop = new Date().getTime();
print("recursive time - " + (stop-start) + "milliseconds"); 
print();
start = new Date().getTime();
print(dynFib(10));
stop = new Date().getTime();
print("dynamic programming time - " + (stop-start) + " milliseconds");

/**

// fib(20)인 경우
6765
recursive time - 1milliseconds

55
dynamic programming time - 1 milliseconds
*/

/**

// fib(30)인 경우
832040
recursive time - 14milliseconds

55
dynamic programming time - 0 milliseconds
*/

 

중간 값을 저장하지 않고도 dp처럼 효율적으로 동작하도록 다음과 같이 구현할 수도 있다.

function iterFib(n) {
    let last = 1;
    ;et nextLast = 1;
    ;et result = 1;
    for (let i = 2; i < n; ++i) {
              result = last + nextLast;
              nextLast = last;
              last = result;
    }
    return result; 
}

문자열의 최대 공통부분 구하기

DP를 활용해 두 문자열이 공통적으로 갖는 문자열을 효율적으로 구할 수 있다.
예를 들어, "raven"과 "havoc"라는 문자열들이 있을 때 공통 문자열 중 가장 긴 부분은 "av"다.

 

DP로 풀이하는 방식을 살펴보기 전에 brute-force로 문제를 해결하는 방식을 살펴보자.

A와 B 문자열이 있다면 A의 첫 요소부터 시작해서 B의 각 요소들과 비교하여 다른 값이 생기면 A의 다음 요소부터 B의 요소들과 다시 비교하면서 살펴보면 된다. for 루프를 도는 횟수가 이미 너무 많을 거라고 예상한다.

 

DP는 이차 배열로 일치하는 값의 개수를 저장하여 계산할 수 있다.

먼저 이차원 배열의 모든 값을 0으로 초기화한다.

같은 값이 발견될 때마다 각 행렬의 값을 1씩 증가시켜 준다. 

 

// 초기화
     a b b c c 
d  0 0 0 0 0
b  0 0 0 0 0
b  0 0 0 0 0
c  0 0 0 0 0
c  0 0 0 0 0

     a b b c c
d  0 0 0 0 0
b  0 1 1 0 0
b  0 1 2 0 0
c  0 0 0 3 1
c  0 0 0 1 4

 

이제 코드로 옮겨보자!

const print = item => console.log(item);

function lcs(word1, word2){
	let max = 0;
    let index = 0;
    let lcsarr = Array.from(word1,(v,i)=>Array.from(word2,()=>0)); // 이차원 배열 0으로 초기화
    
    for(let i=0; i< word1.length; ++i){
    	for(let j=0; j <= word2.length;++j){
        	if(i==0 || j==0){
            	lcsarr[i][j] = 0;
            } else {
            	if(word1[i-1] == word2[j-1]){
                	lcsarr[i][j] = lcsarr[i-1][j-1]+1;
                } else {
                	lcsarr[i][j] = 0;
                }
            }
			if(max<lcsarr[i][j]){
            	max = lcsarr[i][j];
                index = i;
            }
        }
    }
	let str = '';
    if(max == 0){
    	return str;
    } else {
    	for(let i=index-max; i< max;++i){
        	str+=word2[i];
        }
		return str;
    
    }

}

print(lcs('abbcc','dbbcc')); // bb

knapsack 문제

알고리즘 연구에서 자주 등장하는 knapsack 문제는 다음과 같은 문제를 다룬다.

온갖 보물들이 가득 찬 금고를 털 수 있게 되었다고 하자. 근데 이 많은 보물들을 담을 수 있는 건 작은 백팩뿐이다.

각 아이템은 크기와 값이 다르고, 백팩을 채워서 가능한 값어치가 높은 아이템으로 채우고 싶다고 하자.

아이템.  💎    💍      🎮      📺

크기         3     4      7       8        9

값            4     5     10     11     13

백팩의 크기 : 16라고 할 때, 💍 + 📺 = 크기 (7+9), 값(10+13)을 가져가는 게 가장 이익이다.

 

먼저 재귀적으로 해당 알고리즘을 코드로 작성해 보자.

function max(a, b) { 
	return (a > b) ? a : b;
}
function knapsack(capacity, size, value, n) { 
	if (n == 0 || capacity == 0) {
		return 0; 
        }
	if (size[n-1] > capacity) {
		return knapsack(capacity, size, value, n-1);
	} else {
		return max(value[n-1] + knapsack(capacity-size[n-1], size, value, n-1), knapsack(capacity, size, value, n-1));
	} 
}
const value = [4,5,10,11,13];
const size = [3,4,7,8,9];
const capacity = 16;
const n = 5;
print(knapsack(capacity, size, value, n)); // 23

 

재귀적인 해결법은 같은 케이스들을 재방문하기 때문에 비효율적이다. DP로 구현해 보자.

function print(item){
    console.log(item);
}

function max(a, b) { 
    return (a > b) ? a : b;
}


function dKnapsack(capacity, size, value, n) { 
    let K = [];
    for (let i = 0; i <= n; i++) { 
        K[i] = [];
        for (let w = 0; w <= capacity; w++) { 
            if (i == 0 || w == 0) {
                K[i][w] = 0; 
            } else if (size[i-1] <= w) {
                K[i][w] = max(value[i-1] + K[i-1][w-size[i-1]], K[i-1][w]);
            } else {
                K[i][w] = K[i-1][w];
            }

        }
    }
    return K[n][capacity]; 
}

let values = [4,5,10,11,13];
let sizes = [3,4,7,8,9];
let capacity = 16;
let n = values.length;

print(dKnapsack(capacity, sizes, values, n)); // 23

 

Greedy Algorithms

거스름돈 주기

!! 책은 cent로 되어 있습니다. 원화로 변경하여 알고리즘을 구현했습니다!!

 

편의점에서 1230원을 거슬러 받아야 한다고 할 때, 직원은 어떻게 최소한의 동전 개수로 거슬러줄 수 있을까?

10원짜리, 50원짜리, 100원짜리, 500원짜리 중에서 골라서 줄 수 있다고 할 때 다음과 같이 구현할 수 있다.

function print(item){
    console.log(item);
}

function makeChange(origAmt, coins) {
    let remainAmt = 0;

    if (origAmt % 500 < origAmt) {
        coins[3] = parseInt(origAmt / 500);
        remainAmt = origAmt % 500;
        origAmt = remainAmt;
    }
    if (origAmt % 100 < origAmt) {
        coins[2] = parseInt(origAmt / 100);
        remainAmt = origAmt % 100;
        origAmt = remainAmt;
    }
    if (origAmt % 50 < origAmt) {
        coins[1] = parseInt(origAmt / 50);
        remainAmt = origAmt % 50;
        origAmt = remainAmt;
    }
    coins[0] = parseInt(origAmt / 10);
}

function showChange(coins) {
    if (coins[3] > 0) {
        print("Number of 500 Won coins - " + coins[3] + " - " + coins[3] * 500);
    }
    if (coins[2] > 0) {
        print("Number of 100 Won coins - " + coins[2] + " - " + coins[2] * 100);
    }
    if (coins[1] > 0) {
        print("Number of 50 Won coins - " + coins[1] + " - " + coins[1] * 50);
    }
    if (coins[0] > 0) {
        print("Number of 10 Won coins - " + coins[0] + " - " + coins[0] * 10);
    }
}

let origAmt = 1230;
let coins = [];
makeChange(origAmt, coins);
showChange(coins);

/**
Number of 500 Won coins - 2 - 1000
Number of 100 Won coins - 2 - 200
Number of 10 Won coins - 3 - 30

*/

knapsack 문제

이전에는 DP로 knapsack 문제를 해결하는 알고리즘과 재귀적으로 해결하는 알고리즘을 살펴봤다.

이번에는 그리디 알고리즘으로 구현해 보자.

그리디 알고리즘으로 knapsack 문제를 해결하고자 할 때 백팩 안에 넣을 아이템들이 연속적인 데이터라고 가정한다.

예를 들면 천이나 사금처럼 하나하나 셀 수 있는 단위로 나뉘는 게 아니라 전체 면적이나 부피를 구하듯이 다루면 된다.

 

최적의 해는 백팩 공간이 없거나 아이템이 소진될 때까지 가장 높은 값들을 백팩에 넣는 것이다.

그다음에는 가능한 값이 높은 아이템을 넣고, 이 과정을 반복하는 것이다.

연속적인 데이터로 최적의 그리디 해를 구하는 이유는 백팩 안에 텔레비전 반 개를 넣을 수 없고, 아예 아이템을 넣거나 넣을 수 없는 경우로만 나뉜다. 

 

알고리즘의 로직은 다음과 같다.

1. 백팩 용적이 W이고, 아이템이 각각 값어치가 V이고 무게가 w일 경우, v/w 비율(무게 대비 가치, 가성비)로 아이템들을 내림차순 순서대로 정렬하자.

2. 각 아이템을 다시 이 비율로 내림차순으로 정렬하자.

3. 가장 비율이 높은 아이템부터 백팩에 넣고, 완전히 넣을 수 없는 경우에는 가방이 가득 찬 것이다.

코드로 옮기면 다음과 같다.

function ksack(values, weights, capacity) { 
	let load = 0;
    let i = 0;
    let w = 0;
    while (load < capacity && i < 4) {
    	if (weights[i] <= (capacity-load)) {
        	w += values[i];
            load += weights[i];
        } else {
        	let r = (capacity-load)/weights[i]; w += r * values[i];
            load += weights[i];
    	} 
        ++i;
    }
    return w; 
}
    
let items = ["A", "B", "C", "D"];
let values = [50, 140, 60, 60];
let weights = [5, 20, 10, 12];
let capacity = 30;
print(ksack(values, weights, capacity)); // 220

---

🍀 마치면서

오늘은 심화 알고리즘인 dp와 그리디 알고리즘에 대해 살펴봤다.
완독!🥳 

 

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9