무식하게 풀기 : 모든 후보 검사하기

무식하게 풀기 전략은 완전 탐색(exhaustive search)이라고도 불립니다. 답이 될 수 있는 경우의 수를 모두 탐색하여 답을 알아내는 무식한 방법이죠.

예를 들어 최적 거래 문제를 한 번 봅시다.
일정 기간 동안 금 가격이 주어져 있다. 이 기간 중 한 날짜에는 금을 사고 한 날짜에는 금을 판다. 이윤을 최대화 하는 최적의 두 날짜를 구하라.

문제플 풀기 가장 이상적인 상황은 최저가가 최고가보다 앞선 날짜에 있을 때입니다. 최저가일때 사고 최고가일때 팔면 되기 때문입니다. 하지만 그 외의 경우는 어떨까요? 좋은 방법은 바로 떠오르지 않을 수 있지만 가장 단순한 방법이 하나 떠오릅니다. 모든 날짜상에 대한 이윤을 비교해서 가장 최적의 이윤을 제공하는 날짜쌍을 구하는 거죠. 가령 기간이 총 n일이라 하면 총 (n-1)n/2 개의 날짜쌍을 비교하면 됩니다.
시간복잡도가 O(n^2)이겠군요. 직관적이고 쉽지만 빠르진 못합니다.

javascript로 이 문제를 풀면 다음과 같습니다.

function optimalTradeDays (arr){
    let otd = {
        max : arr[1]-arr[0],
        buyDay : 1,
        sellDay : 2
    }
    for(let i=0;i<arr.length-1;i++){
        for(let j=i+1;j<arr.length;j++){
            if((arr[j]-arr[i])>otd.max){
                otd.buyDay = i+1;
                otd.sellDay= j+1;
                otd.max = arr[j]-arr[i];
            }
        }
    }
    return otd;

다른 문제를 보아볼까요.
한 상인이 상품을 배낭에 담아 팔려고 한다. 각 상품에는 무게와 가격이 존재합니다. 배낭은 무게 제한이 있습니다. 배낭에 담은 상품들의 총 가격을 제일 크게 하려면 어떤 상품을 골라야 할까?

이것 또한 좋은 방법이 있겠지만 무식하게 풀어본다면 상품들의 집합으로 만들 수 있는 멱집합을 만들어 모든 집합들에 대해 배낭 무게제한 통과여부와 가격을 비교해보는 방법이 있습니다. 애초에 멱집합을 만드는 것의 시간복잡도가 (2^n)이니까 엄청나게 비효율적이군요. 이 문제를 javascript로 한 번 풀어볼까요.

알고리즘의 순서는 다음과 같습니다.
0. 최대 이윤과 최대 이윤을 만들어내는 가방에 담을 물건들의 리스트를 담을 객체를 생성합니다.
1. 반복전략에서 만든 멱집합 생성함수로 물건들에 대해 멱집합을 만듭니다.
2. 각 멱집합에 대해서 무게 제한 통과 여부를 파악하고 통과시 총 가격을 max값과 비교합니다. max값보다 해당 멱집합이 큰 경우에는 max값을 갱신하고 itemList도 갱신합니다.
3. 최종적으로 만들어진 itemList를 return합니다.

이것을 javascript로 만들어볼까요

function backPack (items,maxWeight){                        //가방에 담을 최적의 아이템 리스트를 구하는 함수
    const obp = {
        maxValue : 0,
        itemList : new Set()
    }
    const comItems = powerSet(items);
    for(const items of comItems){
      let weight=0, value=0;
      for(const item of items){
        weight=weight+item[2];
        value=value+item[1];
      }
      if(weight<maxWeight&&value>obp.maxValue){
        obp.maxValue=value;
        obp.itemList.clear();
        obp.itemList.add(items);
      }
    }
    return obp;
}

function powerSet(set){                                        //set에 대한 멱집합을 만드는 함수.
  const powS=new Set();
  powS.add(new Set());
  for(let item of set){
      const setClone = cloneSet(powS);
      for(let el of setClone){
          el.add(item);
          powS.add(el);
      }
  }
  return powS;
}


function cloneSet(set) {                                       //set 안의 원소들이 배열일 경우 깊은 복사하는 함수. 
    const clone = new Set();
    for (let item of set) {
      if (Array.isArray(item) && item != null) {
        clone.add(cloneArr(item));
      } else if(typeof item ==="object"){
            clone.add(cloneSet(item));
      }else{
        clone.add(item);
      }
    }
  
    return clone;
}

function cloneArr(arr) {                                      //배열에 대해 깊은 복사하는 함수.
    const arrClone = [];
    for (let item of arr) {
      if (typeof item=== "object" && item != null) {
        arrClone.push(cloneArr(item));
      } else {
        arrClone.push(item);
      }
    }
    return arrClone;
}

참고자료
1. 한 권으로 그리는 컴퓨터 과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루 옮긴이 : 박연오 76P-79P
2. 깊은복사함수
3. 멱집합 함수