S4) Unit 11. 알고리즘 문제풀이(순열, 조합, Greedy, 멱집합)

📌  문제

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.
 
예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

• $50 한 장을 훔친다
• $20 두 장, $10 한 장을 훔친다
• $20 한 장, $10 세 장을 훔친다
• $10 다섯 장을 훔친다

훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.
 

✏️  풀이

⁇ 레퍼런스 코드 봐도 모르겠다.
경우의 수를 구하지 않았는데 어떻게 배열에 저장되있는거지..

function ocean(target, type) {
  // bag 이라는 배열에 금액을 만들 수 있는 경우의 수를 기록
  // 각 인덱스 no# = 만드려는 금액 을 의미
  // ex) target = 5, type = [1, 2, 5] 면
  // bag[3] = 2  => 3원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 (1*3, 1 + 2)
  // bag[4] = 3  => 4원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 (1*4, 1*2 + 2, 2*2)
  // bag[5] = 4  => 5원을 만드는 경우의 수 = 1만 사용 & 1,2 함께 사용 & 1, 2, 5 함께 사용 (1*5 , 1*3 + 2, 1 + 2*2, 5*1)
  // 0 을 만들 수 있는 경우는 아무것도 선택하지 않으면 되기 때문에 bag[0] = 1 로 초기값 설정
  let bag = [1];

  // 인덱스 no# = 만드려는 금액 이기 때문에
  // bag 을 target 금액만큼의 길이를 가진 배열을 만들어 주고,
  // 경우의 수를 저장하기 위해 초기값은 모두 0으로 만들어 준다
  for(let i = 1; i <= target; i++)
    bag[i] = 0;
  // 돈의 종류가 담겨있는 배열을 순차적으로 탐색   
  for(let i = 0; i < type.length; i++) {
  // target 금액까지 순차적으로 1씩 증가하면서    
    for(let j = 1; j <= target; j++)
  // bag의 인덱스가 type[i] 보다 큰 구간만
  // (작은 구간은 type[i]로 만들 수 없는 금액이기 때문에 탐색할 필요가 없다)    
      if(type[i] <= j)
  // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다       
        bag[j] += bag[j-type[i]];
        console.log(bag)
  }
  // bag 의 target 인덱스에 target 금액을 훔칠 수 있는 경우의 수가 쌓이므로
  // 해당 값을 리턴해 준다
  return bag[target];
}

---

📌  문제

가위바위보 게임은 2인 이상의 사람이 동시에 '가위, 바위, 보'를 외치고 동시에 가위, 바위 또는 보 중에서 한 가지를 의미하는 손 모양을 내밀어 승부를 결정짓는 게임입니다. 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다.
 

✏️  풀이

💡 중복순열

function rockPaperScissors (n=3) {
  const result = [];
  const arr = [['rock'], ['paper'], ['scissors']];
  if(n===1) return [['rock'], ['paper'], ['scissors']];
  // 재귀가 끝날 수 있는 기준을 만들어주고

  let prev = rockPaperScissors(n - 1);
  // 하나는 뽑았으니 만약 n=3이라면 2개만 더 뽑으면 된다.
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < prev.length; j++) {
      result.push([...arr[i], ...prev[j]]);
      // 뽑아둔 애랑 합쳐준다
    }
  }

  return result;
};

---

📌  문제

개업 이래로 항상 승승장구하는 '승승장구 치킨집'의 비결은 소스에 있다. 수많은 타사 브랜드 치킨집들이 승승장구 치킨집의 소스 비결을 알아내려고 했으나 빈번히 포기했다. 그 이유는 5대째 내려오는 '비밀의 승승장구 치킨 소스 비율 레시피'는 70억 인구 중 사장님만 알고 있기 때문이다. 최근, 누리꾼 사이에서 이 레시피의 일부분을 발췌했다는 소문을 듣게 되었다. 그 소문은 다음과 같다.

1. N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
2. 재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.
   1. 단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.
3. 재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.

이 소문을 참고하여 '비밀의 승승장구 치킨 소스'가 될 수 있는 경우의 수를 모두 반환하는 함수를 작성하세요.
 

✏️  풀이

💡 순열

function newChickenRecipe(stuffArr, choiceNum) {
  const answer = [];
  const grad = zeroThree(stuffArr);

    if(choiceNum === 1) return grad.map((item) => [item]);

    grad.forEach((item, idx, origin) => {
      const remain = [...origin.slice(0, idx), ...origin.slice(idx+1)];
      // 선택한 원소 제외한 나머지 => 순서 신경써줘야한다.
      const rePermutation = newChickenRecipe(remain, choiceNum-1);
      // 제외한 애들 중에서 다시 뽑는데, 아까 하나 뽑았으니까 -1해서 재귀 호출해주기
      const result = rePermutation.map((el) => [item, ...el]);
      // 처음에 뽑아 놓은 애 연결해주기
      answer.push(...result);
    });
    return answer;
  }

function zeroThree(stuffArr){
  // 0이 3개 이상이면 상한 음식이므로 제외해주기
  let zeroThree = /0{3}/;
  let grad = stuffArr.filter((item) => {
    return zeroThree.test(item) === false;
  });
  return grad;
}

---

📌  문제

평범한 블랙잭 게임에서 수시로 패배하자 흥미가 떨어진 김코딩은 박타짜에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다. 새로운 룰은 다음과 같습니다.
 
1. 숫자로 이루어진 카드를 여러 장 받습니다.
2. 3장씩 카드를 고르고, 3장에 적힌 숫자들의 합이 소수인지 확인합니다.
3. 받아든 카드로 만들 수 있는 소수의 개수가 많은 사람이 이기게 됩니다.
 
예로, [1, 2, 3, 4]라는 카드를 받았을 때 만들 수 있는 숫자는 6, 7, 8, 9이고, 소수는 7 하나이기 때문에 가지고 있는 소수의 개수는 1개입니다. [2, 3, 4, 8, 13]라는 카드를 받았을 때 만들 수 있는 숫자는 9, 13, 18, 14, 19, 23, 15, 20, 24, 25이고, 소수는 13, 19, 23 총 3개이기 때문에 가지고 있는 소수의 개수는 3개입니다.
 
게임을 진행하기 전에 소수에 대해 아무런 지식이 없는 박타짜는 게임을 며칠 미룬 뒤, 게임의 룰을 따르는 함수를 만들기로 했습니다. 소수에 약한 박타짜를 도와 여러 장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.
 

✏️  풀이

💡 조합 + 소수 구하기

function boringBlackjack(cards) {
  let answer = 0;
  const permutation = combinations(cards, 3);
  // 조합으로 카드 3장 뽑아주기

  permutation.map((item) => { 
  // 조합 가져와서 각 조합의 합 구하고
    let sum = 0;
    for(let i=0; i<item.length; i++){
      sum += item[i];
    }

    if(isPrime(sum)) answer++;
    // 그 합이 소수인지 확인
  })
  return answer;
}

function combinations(arr, choiceNum){
// 조합 함수
  const answer = [];

    if(choiceNum === 1) return arr.map((item) => [item]);

    arr.forEach((item, idx, origin) => {
      const remain = [ ...origin.slice(idx+1)];
      // 조합은 순서 상관 없으니까 순열과는 다르게 해줘야한다.
      const rePermutation = combinations(remain, choiceNum-1);
      // 제외한 애들 중에서 다시 뽑는데, 아까 하나 뽑았으니까 -1해서 재귀 호출해주기
      const result = rePermutation.map((el) => [item, ...el]);
      // 처음에 뽑아 놓은 애 연결해주기
      answer.push(...result);
    });
    return answer;
}

function isPrime(num){
// 소수 확인 함수
  if(num === 2) return true;
  if(num === 1) return false;

  for(let i=2; i<=Math.ceil(Math.sqrt(num)); i++){
    if(num%i === 0) {
      return false;
    }
  }

  return true;
}

---

📌  문제

김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.
밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.
 

✏️  풀이

💡 멱집합

function missHouseMeal(sideDishes) {
  const result = [];

  function recursion(subset, start) {
    subset.sort();
    // 사전순으로 정렬
    result.push(subset);

    for(let i=start; i<sideDishes.length; i++){
      recursion([...subset, sideDishes[i]], i+1);
      // 부분 집합을 for문 돌면서 계속 늘려간다.
    }
  }
  recursion([], 0);

  result.sort();
  return result;
}