[Algorithm] 조합 최적화 알고리즘 subsetSum Node.js

조합 최적화 알고리즘은 주어진 배열 내에서 특정 조건을 만족하는 최적의 조합을 찾아내는 문제입니다. 

조합(Combination)이란?

조합은 서로 다른 n개의 원소중에서 순서에 상관없이 r개의 원소를 선택하는 것입니다. 순열(Permutation)은 순서를 가진 조합입니다.

 

 

 

let output = subsetSum([1, 8, 3, 15], 10);
console.log(output); // --> 9 (= 1 + 8)

output = subsetSum([20, 80, 99, 27, 35], 100);
console.log(output); // --> 100 (= 20 + 80)

output = subsetSum([10, 20, 15, 25, 30], 5);
console.log(output); // --> 0

 

 

조합 최적화 알고리즘 풀이

 

예를 들어 서로 다른 4개의 원소 중에서 2개의 원소를 조합해서 출력하는 문제가 있다고 가정합니다.

① 우선 원소를 담을 배열을 생성하고 모든 경우의 수를 탐색할 재귀 함수를 선언합니다.

② 재귀 함수 내에서는 N만큼 순회하는 for 반복문이 돌아가고 백트래킹 알고리즘을 사용해 가능한 모든 경우의 수를 탐색합니다. 

③ 재귀 함수의 탈출 조건은 주어진 인자 n이 R만큼 도달한 경우 입니다.

const combi = (N, R) => {

    const temp = [];

    const recur = (n) => {
        if(n === R){
            console.log(temp.join('-'));
            return;
        }

        for(let i=1; i<=N; i++){
            if(!temp.includes(i)){
                temp.push(i);
                recur(n+1);
                temp.pop();
            }
        }
    }

    return recur(0);
}

 

 

1-2
1-3
1-4
2-1
2-3
2-4
3-1
3-2
3-4
4-1
4-2
4-3

 

 

subsetSum 문제의 경우 조건으로 요소들을 더해 bound 값 이내에 들어오는 경우 해당 조합의 합을 반환하게 되어 있습니다.

①  답을 구하기 위해 주어진 bound 값에서 현재 요소를 마이너스 하면서 0 혹은 -1이 될 때 까지 반복을 진행합니다.

②  현재의 계산값(before)와 추가로 한단계 더 나아가는 before-set[idx] 두개의 경우의 수를 두고 둘 중 큰 값을 찾습니다.

③ 만약 idx가 set 길이 만큼 반복을 완료한 경우 조합(bound-before)을 반환합니다.

const subsetSum_naive = (set, bound) => {
    const N = set.length;

    const recur = (idx, before) => {
        // 현재 까지의 최대합 반환
        if(idx === N) return bound-before;

        // 마이너스가 되는 경우
        if(set[idx] > before) return recur(idx+1, before);
        // 0이 되는 경우
        if(set[idx] === before) return bound;

        return Math.max(
            recur(idx+1, before-set[idx]),
            recur(idx+1, before),
        )
    }
    return recur(0, bound);
}

 

위와 같은 방법으로 특정 조건을 만족하는 조합을 찾을 수 있습니다. 하지만 문제점은 이 경우 모든 경우의 수를 반복해서 구하게 되므로 시간복잡도는 O(2 ^ N)이 됩니다. 찾아야 하는 조건값이 커질 수록 경우의 수도 기하급수적으로 늘어나게 됩니다. 

이 문제를 해결하기 위해 나온 방법이 동적 프로그래밍(Memoization + Tabulation) 입니다.

 

 

 

 

[Algorithm] TSP 알고리즘(해밀턴 경로 방문 판매원 문제) Node.js

 

[Algorithm] 동적 프로그래밍 LIS 문제 (Memoization VS Tabulation)

 

[Algorithm] 기수 정렬 계수 정렬 Node.js