52일차 [자료구조/알고리즘2] 중복순열, 순열, 조합

2021. 10. 07 목요일

1. Today's Key Points!🔑

• 중복순열
• 순열
• 조합

2. 정리해보자!🧹

중복순열부터 익히면 순열과 조합을 이해하는 것이 수월해진다. 수학적인 의미는 알고있는 것으로 하고 코드를 어떻게 작성해줘야 하는지 보자.

1) 중복순열

우선 반복문만을 사용해서 중복순열을 구현해보자.

n개의 아이템이 있을 때, 이 n개의 아이템을 중복해서 나열할 수 있는 모든 경우의 수를 리턴하는 코드를 만들 수 있어야 한다.

let result = [];
let arr = [1, 2, 3]
for(let i = 0; i < arr.length; i++){
  for(let j = 0; j < arr.length; j++){
    for(let k = 0; k < arr.length; k++){
      result.push([arr[i], arr[j], arr[k]]);
    }
  }
}
console.log(result)

반복문만 사용해도 중복순열을 구할 수 있다. 근데 배열에 10개의 요소를 담고있고, 중복가능한 10자리 수를 만든다고 가정하면 10중 반복문을 써야할 것이다. 그래서 이것을 재귀로 만들어 준다면 좀 더 간결하게 만들어 줄 수 있을 뿐만 아니라, 배열과 자릿수가 동적으로 변하는 경우에도 중복순열을 구해낼 수 있을 것이다.

let result = [];

//bucket은 조합을 담아낼 일회성 그릇이라고 생각하면 된다.
function multiPermutation(arr, n, bucket) {
  if(n === 0) { // 탈출조건
    result.push(bucket);
    return;
  }
  for(let i = 0; i < arr.length; i++){
    multiPermutation(arr, n - 1, bucket.concat(arr[i]))
  }
  return result;
}

multiPermutation([1,2,3], 3, []);

반복문안에 재귀를 돌려 몇중 반복이되도 원하는 값을 얻을 수 있다. 물론 여기서 더 재사용성이 가능한 함수로도 만들 수 있다. 그렇게 만드는 것은 조금더 고민을 하면서 만들어 나가야할 것 같다. 위의 코드를 보면 result가 중복순열 함수 바깥에 선언이 되어있고, 함수 안에서 result에 bucket을 추가시키면서 리턴하는 것을 볼 수 있을 것이다. 이렇게 되면 중복 순열 함수가 필요할 때 바깥에 함수를 선언해놓고 가져다 쓰는것이 아니고, 다른 함수를 구현하고 있는 곳 안에서 중복순열 함수를 선언해서 사용해야 할 것이다. 이 부분이 내가 마음에 들지 않기 때문에 완전히 재사용성을 가진 함수를 만들 수 있도록 중복순열을 더 이해하려고 노력할 것이다.

2) 순열

순열은 중복순열에서 한 조건만 추가해주면 구현할 수 있다. 이것도 우선 반복문으로만 구현을 해보자.

let result = [];
let arr = [1, 2, 3]
for(let i = 0; i < arr.length; i++){
  for(let j = 0; j < arr.length; j++){
    for(let k = 0; k < arr.length; k++){
      if(i === j || j ===k || k === i) continue;
      result.push([arr[i], arr[j], arr[k]]);
    }
  }
}
console.log(result)

순열은 중복이 되면 안되기에 i, j, k가 같을 때는 넘기고 진행을 시킨다. 그럼 중복되는 부분이 사라지게 될 것이다. 그럼 이것도 재귀로 다시 구현해보자.

let result = [];
function permutation(arr, n, bucket){
  if(n === 0){
    result.push(bucket);
    return;
  }
  
  for(let i = 0; i < arr.length; i++){
    let rest = arr.slice();
    let pick = rest.splice(i, 1);
    permutation(rest, n - 1, bucket.concat(pick));
  }
  return result
}

permutation([1,2,3], 3, []);

다시 재귀에 넣어서 돌릴 배열을 rest라고 만들어 arr배열을 복사해주고, 거기서 한 요소를 고를 때 rest를 splice해줘서 그 배열에서 pick된 요소를 제거해준다. 그럼 재귀가 돌때 계속 선택된 요소는 빠진 상태인 배열이 인자로 들어가 중복되는 요소가 없는 조합을 만들어내게 된다.

3) 조합

조합은 n개 중에 k개를 뽑아서 조합을 만드는 것이다. 같은 요소가 사용이 되도 안되고 즉, 중복이 되는 것이 안된다. 그리고 순서가 다른것도 같은것으로 취급한다. 예를 들어, 순열에서 [1,2,3]과 [1,3,2]는 다른 것으로 취급하는데 조합은 같은것으로 취급한다. 그렇기 때문에 한번 사용이 된것은 다음번에 사용을 하면 안된다.

let result = [];
let arr = [1,2,3];

for(let i = 0; i < arr.length; i++){
  for(let j = i + 1; j < arr.length; j++){
    result.push([arr[i], arr[j]])
  }
}
console.log(result);

위 코드의 반복문에서 j에 선언을 해준 것을 보면, i에서 사용된 것을 사용하지 않게 하기 위해서 j = i + 1을 해준 것이다. 그럼 이것도 재귀로 구현을 해보자.

let result = [];
function combination(arr, n, bucket){
  if(n === 0){
    result.push(bucket);
    return;
  }
  
  for(let i = 0; i < arr.length; i++){
    let pick = arr[i];
    let rest = arr.slice(i + 1);
    combination(rest, n - 1, bucket.concat(pick));
  }
  return result;
}

combination([1,2,3], 2, []);

조합은 순열과는 다르게 순서가 달라고 같은것이라고 취급하기 때문에 pick된 것만 빼내는것 뿐만 아니라 한번 빼내면 다시 넣지 않아야 한다. 그래서 rest배열을 하나씩 줄여나가 주는 것이다.

3. Coplit 과제 복기!🧐

👉🏻가위바위보(중복순열)

- 문제 : 세 판의 가위바위보 게임을 할 경우, 한 사람은 세 번의 선택(예. 가위, 가위, 보)을 할 수 있습니다. 세 번의 선택으로 가능한 모든 경우의 수를 구하는 함수를 작성합니다. advanced : 세판 한정이 아닌, 라운드 수가 동적으로 변해도 모든 경우의 수를 구하는 함수를 작성합니다.

- 풀이 : 중복순열을 사용해서 모든 경우의 수를 구하면 된다.

function rockPaperScissors (num) {
  let result = [];
  let rps = ['rock', 'paper', 'scissors'];
  num = num || 3;
  
  function recursive(count, arr, bucket){
    if(count === 0){
      result.push(bucket);
      return;
    }
    for(let i = 0; i < arr.length; i++){
      const pick = arr[i];
      recursive(count - 1, arr, bucket.concat(pick));
    }
  }
  
  recursive(num, rps, []);
  return result;
};

중복순열 조합을 만들어주는 함수를 만들고 그 함수는 몇자의 조합으로 할지를 정할 수와, 조합의 요소를 담은 배열, 조합을 담을 버킷을 인자로 받게 한다. 그리고 반복문을 하나 만들어 그 안에 재귀함수를 돌려 다중 반복을 실행시키는 것 처럼 작동하는 함수를 만든다. arr 배열에서 하나를 골라 버킷에 담고 카운트를 하나 내려 재귀를 돌린다. 카운트가 0이 되면 버킷에 담겨있던 것들을 result에다 옮기고, 앞에 남아있는 재귀와 반복문이 돌면서 버킷이 계속 result에다 날라준다. 재귀가 끝나면 result에는 중복순열을 돌린 조합들이 모두 담겨있을 것이다.

👉🏻새로운 치킨 소스 레시피(순열)

 - 문제 : 치킨 소스 레시피의 일부분을 발췌했다는 소문은 다음과 같다.

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

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

- 풀이 : stuffArr를 받으면 일단 신선한 재료로만 골라야하기에 0이 3개 이상들어간 재료를 빼는 작업이 필요하다.

그 다음 순열 함수를 만들어 모든 조합의 경우의 수를 리턴해준다.

function newChickenRecipe(stuffArr, choiceNum) {
  let freshArr = stuffArr.filter(el => {
    let findZero = String(el).match(/0/g)
    if(Array.isArray(findZero) && findZero.length >= 3){
      return false;
    }
    return true;
  });
  let result = [];
  
  function permutation(arr, n, bucket){
    if(n === 0){
      result.push(bucket);
      return;
    }
    
    for(let i = 0; i < arr.length; i++){
      let rest = arr.slice();
      let pick = rest.splice(i, 1);
      permutation(rest, n - 1, bucket.concat(pick));
    }
    return result
  }
  permutation(freshArr, choiceNum, []);
  return result;
}

신선한 재료를 찾는 것을 정규표현식을 이용하여 찾아주었다. Array.isArray로 findZero를 판별해준 이유는 0을 하나도 못찾았을 경우에 null이 나오기 때문이다. 이렇게 찾은 신선한 재료 배열을 순열함수에 넣어서 돌리면 모든 경우의 수를 찾을 수 있다.

👉🏻블랙잭은 지겨워(조합)

- 문제 : 블랙잭이 지겨워져서 새로운 카드 놀이를 한다. 새로운 카드놀이의 룰은 다음과 같습니다.

1. 숫자로 이루어진 카드를 여러 장 받습니다.
2. 3장씩 카드를 고르고, 3장에 적힌 숫자들이 합이 소수인지 확인합니다.
3. 받아든 카드로 만들 수 있는 소수의 개수가 많은 사람이 이기게 됩니다.

여러장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.

- 풀이 : 우선 카드를 받으면 3장의 카드로 만들 수 있는 조합을 구해야 한다. 조합을 구해서 각 조합의 합을 담은 배열을 만든다. 그리고 소수를 판별할 수 있는 함수를 만들어 소수가 맞을 때 마다 카운트를 세어 최종 카운트를 리턴한다.

function boringBlackjack(cards) {
  let result = [];
  function combination(num, arr, bucket){
    if(num === 0){
      result.push(bucket);
      return;
    }
    for(let i = 0; i < arr.length; i++){
      let pick = arr[i];
      let rest = arr.slice(i + 1);
      combination(num - 1, rest, bucket.concat(pick));
    }
    return result;
  }
  
  let possibleCards = combination(3, cards, []);
  let sums = possibleCards.map(el => el.reduce((acc, cur) => acc + cur));

  let count = 0;
  for(let i = 0; i < sums.length; i++){
    if(isPrime(sums[i])){
      count++;
    }
  }
  return count;
}

const isPrime = (num) => {
  if(num % 2 === 0) return false;
  for(let i = 3; i <= Math.sqrt(num); i+=2){
    if(num % i === 0){
      return false;
    }
  }
  return true;
}