[알고리즘] 중복순열, 순열에 대해서 (DFS)

순열 : 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.

 

순열의 개념은 굉장히 쉽습니다. n개에서 -1씩 빼서 r이 될 때까지 그 숫자를 나열해 곱해주면 그 경우의 수가 나온다. 결국 펙토리얼과 같은개념 입니다.

nPn=n(n-1)(n-2)···2·1=n!

 

중복순열로 이어진다면 n의 r 제곱으로 이어 져서 nPr 로 표현이 가능할 것입니다.

 

수학적인 개념도 중요하지만 개념을 하는것과 코딩으로 풀어내는것은 좀 더 높은 수준을 요구 하는 것으로 저에겐 보여집니다.

배우는 것 보다 남에게 누구에게 가르친다는것은 더 많은 것을 알아야 하는 것 처럼

코딩 한다는 것은 어떠한 상황을 컴퓨터에게 가르쳐줘야 하는 것과 같기 때문에 코딩을 하는 것은 더 어려운 것 같습니다.

 

 

중복순열이 중복이 가능하다는 점을 꼽아 더 쉽게 생각할 수 있다고 생각이들어 중복 순열 문제 부터 보겠습니다.

 

중복순열

문제

가위, 바위, 보를 할 때 n게임을 할 때, 낼 수 있는 경우의 수를 모두 구합니다. 우선순위는 바위>가위>보 입니다.

ex) n이 5게임일때 [바위, 바위, 바위, 바위, 바위] , [바위, 바위, 바위, 바위, 가위], [바위, 바위, 바위, 바위, 보] ....

 

해석

판수가 정해져 있다면, 그 판수만큼 for문을 반복하여 충분히 구할 수 있습니다. 어떤 문제든 n이 정해져있다면 그만큼 반복을 하면 됩니다.

하지만 수준이 높은 문제일수록 조건이 까다롭기 때문에 판수는 100판 까지 할 수 있는 경우를 생각하라고 합니다.

 

물론 무지성으로 for문 100번 반복하면 풀긴 풀어질겁니다. 그리고 그 판수가 항상 정해져 있지 않는 변수이니 더 깊게 생각을 해야 합니다.

고등학교때 모르는 수학 문제가 있으면 흔히 노가다를 하면 풀 수 있는 문제가 있는 것 처럼 가능은 하지만 결코 자기 실력은 아닐 테니 방법을 알아야 합니다.

 

결국 코딩을 짜기 위해서는 문법이라는 것을 알아야 하는데 문제는 DFS를 사용해야 합니다. (DFS 링크타고 확인가능)

 

각 숫자(행) 마다 하나를 선택 한다고 보면 됩니다. 5번째 끝에 다다랐을 때에는 5게임만큼 다 채운 것이기 때문에 3의 5제곱 즉 243의 경우의 수가 나와야 함으로, 열이 81개 이고 각 안에 1, 2, 3의 인자가 있으니 총 243으로 3의 5제곱의 갯수와 정확히 일치합니다

 

1. [바위, 가위, 보] 1개

2.  [바위, 가위, 보],[바위, 가위, 보][바위, 가위, 보] 3개

3.  [바위, 가위, 보],[바위, 가위, 보],[바위, 가위, 보]... 9개

4. [바위, 가위, 보],[바위, 가위, 보],[바위, 가위, 보]... 27개

5.  [바위(1) 가위(2) 보(3)],[바위 (4), 가위(5), 보],[바위, 가위, 보],... 81개

 

하나를 고르면 그 다음 선택지가 3개가 있으니 점차 늘어난다는 겁니다.

	1 번째	2 번째	3 번째	4 번째	5 번째..
1	바위	바위	바위	바위	바위
2	바위	바위	바위	바위	바위
3	바위	바위	바위	바위	바위
4	바위	바위	바위	가위	가위
5	바위	가위	보	바위	가위

보라색을 보면 바위 가위 보가 순서대로 입력이 되고, 초록색도 마찬가지로 보라색의 반복을 완료하니 그 상위 부분인 바위 가위 보 순으로 바뀌고 있습니다. 이부분을 재귀로 입력하여 코드를 짜주면 됩니다.

 

 

 function rockPaperScissors (num) {

  if(num === undefined){ // num에 값이 없으면 3을 넣는 내용입니다.
    num = 3
  }   //  rounds = rounds || 3; 코드를 변경하면 간결합니다.
 
 
 
 let array = ['rock', 'scissors', 'paper'];
 let result = [] // 모두 선택을 하여 결과값에 담습니다.

  let game = function(number, body){

    for(let i = 0; i < array.length; i++){  // 가위 바위 보를 반복합니다.
      let rps = array[i]   // rps에 선택한 값을 넣습니다.
      if(number === 0){ // 모든 판수를 채웠을때 재귀를 탈출하는 조건입니다.
        result.push(body) // 탈출 하면서 하고자 하는 판수만큼 선택된 경우의 수중 하나를 결과 값에 넣습니다.
        return // 재귀를 빠져나옵니다.
      }
      game(number - 1, body.concat(rps))   // num 숫자를 카운트 시켜 0일 될때까지 재귀 시키고 body에 선택된 값을 그대로 가져갑니다.
    }
  }

  game(num, [])

  return result // 경우의 수를 모두 넣은 result를 리턴합니다.
};

Reference 코드

const rockPaperScissors = function (rounds) {

  // rounds 매개변수를 임의로 넣습니다.
  // rounds 변수가 있을 경우 그대로 사용하고, 없다면 3(기본)을 사용합니다.
  rounds = rounds || 3;
  const rps = ['rock', 'scissors', 'paper'];

  // 결과를 담을 배열 선언
  const outcomes = [];

  // 재귀를 사용할 함수 선언
  // rounds를 넣을 변수 roundsToGo, 일회용 배열인 playedSoFar 변수를 선언합니다.

  // 재귀를 사용하는 이유는, 배열의 모든 요소의 경우의 수를 훑기 위한 적절한 방법이기 때문입니다.
  // 간단히 말하자면, 이 함수는 rounds 숫자를 기준으로, 일회용 배열에 rps 요소를 rounds 숫자만큼 넣게 됩니다.
  // 이 로직을 잘 이해할 수 있을 때까지 하단의 함수 로직을 연구해야 합니다.
  let permutate = function (roundsToGo, playedSoFar) {

    // rounds가 0일 경우 outcones 배열에 삽입하고, 재귀에서 빠져나옵니다.
    if (roundsToGo === 0) {
      outcomes.push(playedSoFar);
      return;
    }

    // rps 배열을 한 번씩 순회합니다.
    for (let i = 0; i < rps.length; i++) {
      // rps의 i번째 요소를 변수에 담아서
      let currentPlay = rps[i];
      // permutate(본인)에 기존 rounds에서 하나 뺀 숫자와, 일회용 배열 playedSoFar에 currentPlay를 삽입하여 재귀를 실행합니다.
      // rounds에서 하나를 빼는 이유는, 일회용 배열의 크기를 rounds만큼 맞춰주기 위함입니다. [rock, rock, rock]

      // Q. playedSoFar.push(currentPlay)로 할 수 있을 텐데, 왜 concat을 사용할까요?
      permutate(roundsToGo - 1, playedSoFar.concat(currentPlay));
      /**
       * 이 재귀의 로직은 이렇습니다. 처음 실행된 반복문은 rps를 전부 순회해야 끝이 납니다.
       * 그러나 한 번 반복할 때마다 permutate 함수가 실행되고, rounds의 숫자는 짧아지며, playedSoFar에 요소가 계속 쌓일 것입니다.
       * 결국, roundsToGo가 0이 될 때까지 이 반복문은 rps[i]가 0일 것이며, playedSoFar에는 [rock, rock, rock]이 되어 outcones에 Push하고, 종료하게 됩니다.
       * return이 되었으니, 한 번의 재귀 호출이 끝났습니다. 마지막 호출 바로 전으로 돌아가,
       * for문은 i = 1을 가리키게 될 것이고, [rock, rock, paper]을 삽입한 뒤 호출을 하게 됩니다.
       * roundsToGo가 0이 되어, 해당 배열은 outcomes 배열에 삽입됩니다.
       * 이런 식으로 모든 호출의 반복문이 끝날 때까지 반복하며 outcomes에 경우의 수 요소들이 담기게 됩니다.
       */
    }
  };

  // 함수를 실행합니다.
  permutate(rounds, []);

  // outcomes를 반환합니다.
  return outcomes;
};

레퍼런스 코드와 별 차이가 없지만 설명이 자세하여 들고 왔습니다.

 

이처럼 순열의 개념을 아는 것과 풀어내는 것은 조금 별개의 개념이라는 느낌이 들었습니다.

위 문제는 중복이 가능한 중복순열이지만 그 다음은 중복하지 않는 순열입니다. 즉, 중복하면 안된다는 조건! 이라는 것이 포함되었다고 생각하면 됩니다. 조건이 추가 되었으니 조금 더 복잡해졌다고 생각하면 쉽습니다.

 

 

순열

문제

1.  N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.

2.  재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 1로 시작하며 복호화를 할 수 없다.

(단, 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.)

3.  재료의 순서에 따라 맛이 달라지기 때문에, 재료를 넣는 순서가 다르다면 다른 레시피이다.

 

ex) 대입 값[1, 10, 1100, 1111],2);

결과 값 [ [1, 10], [1, 1100], [1, 1111], [10, 1], [10, 1100], [10, 1111], [1111, 1], [1111, 10], [1111, 1100] ]

 

쉽게 말하면 0이 연속해서 3개 붙어있으면 제외하고 그 다음 값 만큼 조합(길이)을 만드는 것입니다.

앞문제와 다른 점은 중복이 되지 않는다는점.

 

 

어쨌든 순열과 중복순열의 차이는 어떠한 요소들이 있으면 중복해서 요소를 사용하느냐 사용하지 않느냐의 차이입니다.

 

코드에서 보자면

코드에서 순열은 선택을 한 부분과 하지 않는 부분을 나누어 재귀를 하고

중복순열은 선택에 제한을 두지 않고(중복하여 선택) 재귀를 합니다.

 

아래의 코드에 for 반복문에서 sliece를 통하여 선택한 부분을 빼 버립니다.

그리고 선택한 요소를 빼 버린 배열을 다음 재귀에서 사용하도록 하는 부분이 중복순열과 다른 점 입니다. 

function newChickenRecipe(stuffArr, choiceNum) {
  // stuffArr에서 0이 3개 이상이라면 전부 필터로 거르는 부분 입니다. 보지않아도 됩니다.
  let freshArr = [];
  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      freshArr.push(stuffArr[i]);
    }
  }
  // 정렬
  freshArr.sort((a, b) => a - b);

  // 재료가 없거나 선택해야하는 숫자보다 작을 경우 조합이 되지 않아빈배열 리턴
  if (freshArr.length === 0 || freshArr.length < choiceNum) return [];


  let result = [];

  // freshArr를 상대로 순열 구하기
  const permutation = (arr, bucket, n) => {
  
    if (n === 0) { // 재귀 탈출 조건
      result.push(bucket); // bucket에 모두 담았으면 result에 푸쉬하고 리턴
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      // 하나를 고르고.
      const choice = arr[i];
 
 	  // arr을 복사해주고
      const sliceArr = arr.slice();
      
      // 초이스 부분을 뺀다.
      sliceArr.splice(i, 1);
      
      // 재귀 sliceArr는 선택하는 바구니(선택 된것은 제외), bucket은 선택된 것을 담는 바구니
      permutation(sliceArr, bucket.concat(choice), n - 1);
    }
    
  };

  // 실행
  permutation(freshArr, [], choiceNum);
  
  // 순열의 길이 반환
  return result;
}