[알고리즘] Algorithm with Math...

오랜만에 만난 수학으로 많이 꺾인 마음으로... 알고리즘 문제들 복습 시~작~

중복순열 : rockPaperScissors

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

advanced : 가위바위보 게임의 수가 세 판으로 정해진 것이 아니라 rounds라는 인자로 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 반환하도록 함수를 작성하라.

• 최종적으로 리턴되는 배열의 순서는 가중치 적용 정렬(Weighted Sort)을 따릅니다.
• 중요도는 'rock', 'paper', 'scissors' 순으로 높습니다.
• 쉽게 생각해 올림픽 순위 결정 방식을 참고하면 됩니다.
  금메달('rock')이 은메달('paper')보다 우선하고, 은메달('paper')이 동메달('scissors')보다 우선합니다.

만약 advanced를 포함하지 않고 구현한다면 삼중 반복문을 이용해서 풀 수 있다.

function rockPaperScissors () {

  let options = ["rock","paper","scissors"];
  let result = [];
  
 //rps를 순회하는 삼중 for문을 만든다
 //각 for문 마다 arr의 0, 1, 2 번째 index 에 바위, 보 , 가위를 순서대로 담아준다.
  for(let i=0;i<options.length;i++){
    	let choice1 = options[i]
    for(let j=0;j<options.length;j++){
      	let choice2 = options[j]
      for(let k=0;k<options.length;k++){
        let choice3 = options[k]
        result.push([choice1,choice2,choice3])
      }
    }
  }
  return result;
}

advanced까지 구현하면 아래와 같다.
rounds 인자의 등장으로 반복문이 몇 개가 나올지 확신할 수 없으므로 재귀로 푼다.

function rockPaperScissors (rounds) {

  rounds = rounds || 3 //rounds는 전달 받을 수도 있고, 아닐 수도 있으므로 단축평가로 기본값 지정
  let options = ["rock", "paper", "scissors"];//순열 요소들을 담은 배열 만들어줌
  let result = [];//각 경우들이 담길 결과 배열 

 //재귀함수
let permutate = function (roundsNum, playedSoFar){
  //탈출 조건 : roundsNum은게임 횟수를 받는 인자인데, roundsNum이 0이 되면 탈출한다.(초기값은 rounds가 될 것이며 재귀가 반복됨에 따라 1씩 감소할 것임) 
  //탈출할 때는 playSoFar 배열을 result에 push함 
  //playedSoFar배열은 현재까지 진행된 게임시 낸 패가 담긴 배열이다.
  if(roundsNum === 0){
  result.push(playedSoFar);
  return;
  }

  //탈출조건에 걸리지 않았을 때는 반복문을 돌리게 된다. 
  //0부터 반복문을 돌린다 
  for(let i=0;i<options.length;i++){
    //currnetPlay에 options의 i번째 요소를 할당한다
    let currentPlay = options[i];
 
 //재귀 : roundsNum 에 1을 뺀 수와 playedSoFar 배열에 currentPlay 변수를 합친 것을 PlaySoFar로 재귀 함수에 전달한다. 
  permutate(roundsNum - 1, playedSoFar.concat(currentPlay));
  }
}

//맨 처음에는 재귀 함수에 rounds와 빈 배열을 전달한다.
//만약 rounds가 5라고 할 때 
//재귀 반복문 안에서 각자 rock/paper/scissors가 각각 currentPlay가 될 것이고 
//이 currentPlay는 premutate가 전달받은 빈 배열 속에 concat되어 각각 [rock]/[paper]/[scissors]가 되어서 재귀 함수 두번째 인자로 전달될 것.
//그렇게 전달된 것 중 permutate(4, [rock])인 경우를 추적해보면
//탈출조건에는 아직 걸리지 않고 반복문 내부에서 다시 currentPlay에서는 rock/paper/scissors가 할당된다.
//이 각각의 currentPlay들은 재귀함수에 전달될 때 permutate(3,[rock,rock])/permutate(3,[rock,paper])/permutate(3,[rock,scissors])와 같이 전달됨.
//반복문의 순서대로 생각하면 맨 앞에 rock인 배열들이 계속해서 만들어지면서 [rock,rock,rock,rock,rock]이 제일 먼저 result에 들어오고
//그 다음에는 [rock,rock,rock,rock,paper]/[rock,rock,rock,rock,scissor]와 같이 우리가 원하는 순서대로 result에 담긴다. 
  permutate(rounds, []);

  return result;
};

처음에 래퍼런스를 보고서 이해하기 위해서 예시 하나를 들어서 함수의 진행 과정을 추적해보았다. rock, paper, scissors가 든 options 배열로 진행하면 우리가 원하는 순서대로 result 배열에 담긴다는 점이 믿기지가 않아서였는데, 이 문제도 그렇고, 다른 문제들을 풀 때 보면 초반에 정렬을 잘 해주면 보통 결과도 순서대로 잘 담기는 것 같았다.

순열 : 새로운 치킨 소스 레시피

알아내야 하는 레시피의 조건은 아래와 같다.

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

- 인자 1: stuffArr는 Number 타입의 재료를 담은 배열.
요소는 0과 1로만 이루어진 숫자이며, 항상 1로 시작한다.
요소는 중복될 수 없으며 길이는 20 이하이다.
배열의 길이는 2 이상 10 이하. ex) [111, 110, 1010, 10, 10110]

• 인자 2: choiceNum
  Number 타입의 1 이상 stuffArr 길이 이하의 자연수
  재료를 선택할 수 있는 수를 뜻한다.
  ex) 2

• 주어진 재료 모두 사용할 수 없다면 빈 배열을 반환.
• 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열 반환.
• 조합 및 요소는 작은 숫자 -> 큰 숫자로 정렬한다.
  ex: [1, 10, 11000, 1111]이 요소로 들어왔다면, 0이 세 개인 11000을 제외하고 [1, 10, 1111] 순서가 되어야 하며,
  [ [1, 10], [1, 1111], [10, 1], [10, 1111], [1111, 1], [1111, 10] ]을 반환해야 한다.

앞선 순열 문제와 다른 점이 있다면 이 문제에서는 경우의 수를 만들기 위해 사용할 수 있는 요소들의 배열을 함수의 첫번째 인자로 받아온다.

function newChickenRecipe(stuffArr, choiceNum) {
 
  //첫 조건 : 0이 3개 이상인 재료는 상한 재료이기 때문에 제외한다.
  let usable = []

  //반복문으로 stuffArr의 매 요소들마다 상한 재료인지 검사한다.
  //각 요소들을 문자열로 만들고 => split으로 나누어 배열에 담고 
  //=> 해당 배열에서 0과 같은 것들만 남겨서 element에 할당 
  //=> 할당된 배열의 길이가 2보다 작을 때만 usable 배열에 push한다.
  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      usable.push(stuffArr[i]);
    }
  }
  
  //두번째 조건 : 만약 사용할 수 있는 재료의 개수 < choiceNum 이면 빈 배열 반환
  if(usable.length < choiceNum){
    return [];
  }
  
  //정렬 : 작은 숫자 -> 큰 숫자로 정렬 (오름차순 정렬 해놓기!! 중요!!!)
usable.sort((a,b)=>a-b)


  //재귀 이용해서 풀기 
let result = [];

 const permutation = (arr, bucket, n) => {
   //탈출조건 : 정해진 N가지의 재료 수가 재귀를 실행할 때마다 1씩 감소하여 0이 되면 result에 bucket을 push한다. 
   //bucket은 만들어진 하나의 소스 레시피의 경우를 담은 배열이다 
    if (n === 0) {
      result.push(bucket);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      const choice = arr[i];
      const sliceArr = arr.slice();//아래 splice를 사용해도 원본 배열을 변경하지 않기 위해서 복사 배열을 만든다.
      sliceArr.splice(i, 1);//splice는 원본배열을 변경한다. sliceArr에는 인덱스 i에 해당하는 요소만 사라진다.
      
      permutation(sliceArr, bucket.concat(choice), n - 1);
    }
  };

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

이번에도 과연 우리가 예상하는 순서대로 result에 담기는 게 맞는지 궁금해서 함수 진행 과정을 추적해보았다.

//예시 풀어서 확인하기 
// stuffArr가 [1, 10, 11000, 1111] 이고, choiceNum은 2라면


// usable = [1,10,1111]

// result = [ ]

// permutation([1,10,1111],[ ],2)

// i가 0,1,2까지 반복문 돈다 

// choice는 arr[i]이므로 각각 반복문마다 1, 10, 1111이 할당될 것임 
// sliceArr는 원 배열의 복사본이고, 이 복사본에서 항상 인덱스i에 해당하는 요소만 사라진다. 
// 그러므로 sliceArr는 각각 [10,1111]/[1,1111],[10,1111]순으로 남는다. 

// 1. permutation([10,1111],[1],1) 

// i=0
// choice는 arr[i]니까 10
// sliceArr는 [1111]
// permutation은([1111],[1,10],0)
// 이러면 탈출조건에 걸려서 첫 return이 [1,10]이 될 거임


// i=1
// choice는 1111
// sliceArr[10]
// permutation([10],[1,1111],0)이므로
// 탈출조건에 걸려서 두번째 return이 [1,1111]이 된다. 



// 2. permutation([1,1111],[10],1)
// i=0
// choice는 1
// sliceArr는 [1111]
// permutation([1111],[10,1],0)
// 탈출조건에 걸려서 result의 세번째 [10,1]

// i=1
// i=0
// choice는 1111
// sliceArr는 [1]
// permutation([1],[10,1111],0)
// 탈출조건에 걸려서 result의 네번째 [10,1111]



// 3. permutation([10,1111],[1111],1)
// i=0
// choice는 10
// sliceArr는 [1111]
// permutation([1111],[1111,1],0)
// 탈출조건에 걸려서 result의 다섯번째 [1111,1]


// i=1
// choice는 1111
// sliceArr는 [10]
// permutation([10],[1111,10],0)
// 탈출조건에 걸려서 result의 여섯번째 [1111,10]

재귀 함수에 따로 n을 인자로 받지 않고, bucket의 길이가 choiceNum과 같아지면 result에 push하고 재귀를 종료하는 방법도 있다.

//재귀 함수 부분만 새롭게 만들어 본 것 

 function recipe(arr, bucket) {
        if (bucket.length === choiceNum) {
            result.push(bucket);
            return;
        }

        for (let i = 0; i < arr.length; i++) {
            let choiced = arr[i];
            let newArr = arr.slice();
            newArr.splice(i, 1);

            recipe(newArr, [...bucket, choiced]);
        }
    }

    recipe(freshStuff, []);

조합 : 블랙잭은 지겨워

New 블랙잭 규칙
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개임.

함수가 받는 인자 cards에는 3개 이상 50개 이하의 카드가 숫자로 들어있는 배열이 할당되어 있다. (중복된 숫자의 카드는 들어있지 않다.)

소수는 1과 자기자신만을 약수로 갖는 수를 말한다.

문제가 너무 구구절절이라 그래서 뭘 구하라고...?하게 되긴 하지만 만들어야 하는 boringBlackjack은 결국

1. 숫자가 적힌 카드들의 집합인 배열 cards를 받아서
2. 그 중에서 3장을 순서에 상관없이 뽑는 경우의 수들 중
3. 그 세 숫자의 합이 소수인 경우의 수를 구하는 것

이라고 할 수 있겠다.

function boringBlackjack(cards) {
  // 순서에 상관없이 3장을 뽑았을 때 그 합이 소수인 경우의 수를 구해야 함.
  
  //합이 소수인 경우의 수를 셀 count 변수를 만든다. 
  let count = 0;

    //일단 3장을 순서에 상관 없이 뽑는 경우의 수들을 모두 구한다
    // 1. cards 에서 카드 3장 뽑기
    let length = cards.length;
    // 카드 뽑는 방식은 첫 카드를 cards 의 0번 index 부터 고정해 놓고 1씩 뒤로 옮겨간다 (순서가 상관이 없기 때문)
    for (let i = 0; i < length; i++) {
    // 두 번째 카드의 인덱스는 첫 카드 + 1에서 시작해야 하고
      for (let j = i + 1; j < length; j++) {
    // 세 번째 카드의 인덱스는 두 번째 카드 + 1에서 시작해야 한다 
        for (let k = j + 1; k < length; k++) {
          const number = cards[i] + cards[j] + cards[k];
          // 세 카드의 합이 소수이면 경우의 수 + 1
          if (isPrime(number)) count++;
        }
      }
    }
  
    //2. 소수 판별하는 함수를 만들어두고 위 반복문에서 사용하고 있다. 
    function isPrime(number) {
    // 2부터 비교하기 시작해서 나누어 떨어지는 수가 있으면 소수가 아니다
    // for 문 조건을 number/2 로 해도 되는 이유는 i > number/2 가 되면 몫이 절대 0이 될수 없기 때문에
    // number/2 까지만 비교해 보아도 소수 판별이 가능하다
      for (let i = 2; i < number/2; i++) {
        if (number % i === 0) return false;
      }
      return true;
    }
  
    return count;
}

예를 들어 17이 소수인지 판별해야 할 때, 위 isPrime처럼 1부터 하나씩 나눠보는 방법을 사용한다면 17/2 은 8.5인데 그러면 8까지 판별해볼 수 있다. 그 이후는 몫이 절대로 0이 될 수 없으므로 8까지만 나누어보아도 17이 소수라는 걸 알 수 있다.

최대공약수 : 빼빼로데이

팀장은 자신보다 먼저 출근해 있는 직원들에게 구매한 빼빼로를 전부 나누어 주려고 하는데 질투하는 경우를 만들지 않기 위해 모든 직원들에게 공평하게 빼빼로를 나눠줘야 함.
직원들은 각각의 빼빼로를 똑같은 개수만큼 받아야 하며 빼빼로를 쪼개서 줄 수는 없음.
하지만 회사에 도착하기 전이라 몇 명의 직원들이 있는지 모르는 상황이다.

아몬드 빼빼로 M개와 누드 빼빼로 N개 개수를 각각 divideChocolateStick 함수의 인자로 받고, 이 함수는 [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수] 배열들이 담긴 2차원 배열을 리턴하는데, 이 2차원 배열은 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬해야 한다.

수가 다르거나 같은 빼빼로 두 종류를 직원에게 나누어줄 수 있는 경우만 결과로 반환할 배열에 들어갈 수 있으므로 직원의 수는 두 빼빼로 개수들의 약수가 된다.
약수는 최대 공약수를 구하면, 그 최대 공약수의 약수들로 구할 수 있다.

//최대 공약수를 구하는 함수를 미리 만들어둔다. (최대 공약수 구하는 방법은 유클리드 호제법*을 사용함.)

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

function divideChocolateStick(M, N) {
  //아몬드 빼빼로 M개와 누드 빼빼로 N개



  //최대 공약수의 약수들이 직원 수가 될 것이며, result의 요소인 배열에 들어가는 것은 [약수, M/약수, N/약수]이다. 
 const result = [];
  
  // 최대공약수를 구한다.
  const GCD = gcd(M, N);
  let temp = 0; 

 // 약수는 대칭적이므로 제곱근까지만 반복해도 된다.
  // 예) 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
  // 제곱근을 기준으로 양쪽의 값 하나씩 곱했을 때 36이 되기 때문에
  // 제곱근 보다 큰 약수는 제곱근보다 작은 약수에서 구할 수 있다.
  const sqrt = Math.floor(Math.sqrt(GCD));
  for (let left = 1; left <= sqrt; left++) {
    if (GCD % left === 0) {
      // 최대공약수의 약수인 경우 중 제곱근 보다 작은 약수의 경우
      result.push([left, M / left, N / left]);
      if (left * left < GCD) {
        // 제곱근이 아닌 경우(제곱근 보다 작은)
        right = GCD / left; // 최대 공약수를 제곱근이 아닌 수로 나누면 제곱근 보다 큰 약수를 구할 수 있다.
        result.push([right, M / right, N / right]);
      }
    }
  }

  // '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬
  result.sort((op1, op2) => op1[0] - op2[0]);

  return result;
}

유클리드 호제법
: 유클리드 호제법은 최대공약수와 관련이 깊은 공식으로 2개의 자연수 a,b가 있을 때 a를 b로 나눈 나머지를 r이라고 하면 a와b의 최대공약수는 b와 r의 최대공약수와 같다는 이론. (단 a가 b보다 커야 한다는 조건(절대적 조건)이 있음. 나누었을 때 음수가 나오면 안 되기 때문.)
이런 성질에 따라 b를 r로 나눈 나머지 r’를 구하고 다시 r을 r’로 나누는 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수.

유클리드 호제법을 알고 있게 되면 최대공약수와 최소공배수를 구하는 모든 문제에 일단 적용해보고 시작할 수 있음.

멱집합 : 집밥이 그리워

반찬이 담긴 배열 sideDishes를 받아 반찬의 모든 경우의 수를 배열에 담아 반환하는 함수를 구하라.

• 반찬을 먹지 않는 것도 포함되며, 반찬은 중복되지 않는다.
• 반찬은 영문으로 작성되어 있으며 출력되는 배열은 전부 사전식 순서로 정렬되어야 한다.(사전식 순서 = 문자열 오름차순)

어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합이라고 한다.

예를 들어 집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}으로 나열할 수 있고, 이 부분집합의 총 개수는 8개. 이 모든 부분집합을 통틀어 멱집합이라고 함.

멱집합은 부분집합을 나열하는 방법에서 가장 앞 원소(혹은 임의의 집합의 원소)가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합 요소가 n개일 때 모든 부분집합의 개수는 2**n개가 된다. (트리구조와 비슷하기도 하나 트리문제는 아님)

function missHouseMeal(sideDishes) {
  const result = [];
	
  //미리 반찬들을 사전식으로 정렬해놓으면 재귀함수 사용시에도 원하는 순서대로 정렬된다. 
  sideDishes.sort();

	function recursion (subset, start) {
		result.push(subset);

		for(let i = start; i < sideDishes.length; i++){
			recursion([...subset, sideDishes[i]], i+1);
		}
	}

	recursion([], 0);

	return result
}