[Algorithm] subsetSum

Intro

subsetSum 알고리즘에 대해서 학습했다. 요즘은 알고리즘을 풀어내는 것에 만족하는 것이 아닌, 시간복잡도를 다이나믹하게 줄이는 동적 알고리즘 풀이법에 관심이 생겨 dynamic 풀이법을 이해해보려 하는데... 역시 쉽지 않다. 이런 알고리즘은 도대체 어떻게 생각해내는 건지... 😭 똑똑하신 분들이 만들어놓은 기존의 다이나믹 풀이법을 외워서라도 체화하는 것이 도움 될 것이라는 조언과 함께.... 오늘도 코드 풀이에 집중해본다.

subsetSum

subsetSum은 자연수의 집합과 bound를 입력받아 각 집합 요소의 최대 1번씩만을 더해 bound에 가장 가까운 합을 만들어 return 하는 알고리즘이다. 모든 경우의 수를 계산하는 O(2^N) 풀이법과 객체를 활용한 방법이 있지만, dynamic: O(bound * N) 알고리즘을 학습해보자.

이 풀이의 경우 집합의 각 요소들의 합의 조합을 true or false로 나타내는 것이 핵심이다.
코드가 간결하기 때문에 수도 코드로만 작성해둔다.

const subsetSum = function (set, bound) {
  // 각 요소들의 조합 여부를 true or false로 저장하는 cached 배열을 이용한다.
  // cached 배열은 bound의 조건 최대 길이만큼 생성한다. (그 이상은 의미 없으므로)
  // max 값을 저장하기 위해 선언해둔다.
    
  // 집합을 순회한다.
    // 중복 계산을 방지하기 위해 reachables라는 새 배열을 이용한다.
    // 해당 턴의 요소를 기준으로 1부터 (bound - 요소: 최대로 더해봤자 bound 길이를 못 넘게 하기 위함)까지 조회한다.
    // 조합이 가능한 값(true)을 만나면 그 값에 해당 턴의 요소를 더해 reachables라는 배열에 저장한다.
    // 만약 더한 값이 max 값보다 크면 max 값을 해당 값으로 변경한다.
    
    // 완성된 reables를 순회하며 cached에 대응해 true 값으로 변경한다.

    // 중복 방지를 위해 해당 턴의 요소도 cached에서 true 처리를 하고 해당 턴의 요소가 max값 보다 크면 max 값을 변경한다.
    
  // return max 
};