DAY77. [자료구조/알고리즘] 코테 준비2

Davina·2022년 12월 12일

algorithm

코드스테이츠 FE - section4

목록 보기

5/7

Algorithm with Math

순열과 조합

순열 (Permutation)

서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것

= 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것

n = 원소의 총 개수
r = 그 중 뽑는 개수
n ≥ r 필수 ! (중복 허용 X)

조합 (Combination)

서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것

= n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것

n = 원소의 총 개수
r = 그 중 뽑는 개수
n ≥ r 필수 ! (중복 허용 X)

예제

카드뽑기
[A, B, C, D, E]로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.

순서를 생각하며 3장을 선택합니다. ⇒ 60가지

//반복문의 개수 === 요소를 뽑는 개수
function permutationLoop() {
	// 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ['A', 'B', 'C', 'D', 'E'];

  let result = [];

  for (let i = 0; i < lookup.length; i++) {
    for (let j = 0; j < lookup.length; j++) {
      for (let k = 0; k < lookup.length; k++) {
        if(i === j || j === k || k === i) continue; //중복된 요소는 제거
        result.push([lookup[i], lookup[j], lookup[k]])
      }
    }
  }

  return result;
}

permutationLoop();

순서를 생각하지 않고 3장을 선택합니다. ⇒ 10가지

function combinationLoop() {
	// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ['A', 'B', 'C', 'D', 'E'];
  let result = [];

  console.log(lookup);

  for (let i = 0; i < lookup.length; i++) {
    for (let j = i + 1; j < lookup.length; j++) { //한 번 조합한 요소는 다시 조합하지 않는다.
      for (let k = j + 1; k < lookup.length; k++) { //한 번 조합한 요소는 다시 조합하지 않는다. 
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }

  return result;
}

combinationLoop();

소수 찾기 (순열)
한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다. 흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 종이에 기록된 모든 숫자가 배열로 주어진다면, 이 종잇조각으로 만들 수 있는 소수는 몇 개인가요?

n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성합니다.
각 순열을 정수로 변환하고, 해당 정수가 중복되지 않으면서 동시에 소수인지 검사합니다.
소수라면 개수를 셉니다.

일곱 난쟁이 (조합)
왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다. 하루일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉" 명이었던 겁니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. (뛰어난 수학적 직관력을 가지고 있던) 백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다. 아홉 난쟁이 각각의 키가 주어질 때, 원래 백설 공주와 평화롭게 생활하던 일곱 난쟁이를 찾는 방법은 무엇인가요?

위 문제는 조합을 이용해서 일곱 난쟁이를 찾을 수 있습니다. 모든 일곱 난쟁이의 키를 합했을 때 100이 된다고 주어졌기 때문에, 9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고, 난쟁이 7명의 키를 합했을 때 100이 되는 경우를 찾으면 됩니다.

GCD & LCM

GCD(Greatest Common Divisor) 최대공약수

두 수 이상의 여러 공약수 중 최대인 수

공약수 (Common Divisor)
두 수 이상의 여러 수 중 공통된 약수
약수 → 어떤 수를 나누어떨어지게 하는 수

LCM(Lowest Common Multiple) 최대공배수

두 수 이상의 여러 공배수 중 최소인 수

공배수 (Common Multiple)
두 수 이상의 여러 수 중 공통된 배수
배수 → 하나의 수에 정수를 곱한 수

유클리드 호제법

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론입니다. 이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게 됩니다.

단 a가 b보다 커야 한다는 조건(절대적 조건)
q는 몫(Quotient)을 의미, r은 나머지(Rest)를 의미

//유클리드 호제법을 이용해 최대공약수를 구하는 로직
function gcd(a, b){
	while(b !== 0){ //0으로 나누면 무한대를 값으로 반환 -> 이를 방지하기 위해 조건
		let r = a % b;
		a = b;
		b = r;
	}
	return a;
}

//유클리드 호제법을 이용해 최소공배수를 구하는 로직
function lcm(a, b){
	return a * (b / gcd(a, b));
}

예제

Mask States
방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요?
(휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

	작업 시간 + 쉬는 시간 5분
A	60분에 9개
B	75분에 15개
C	90분에 25개

세 명이 동시에 휴식을 취하는 시점은 세 명이 쉬고 난 직후가 같을 시점이 됩니다. 따라서 쉬고 난 직후가 처음으로 같을 시점을 구해야 하므로, 앞서 학습했던 최소공배수의 개념을 알아야 합니다.

결과적으로, LCM(60, 75, 90)은 900입니다. (LCM; Least Common Multiple, 최소 공배수)

A는 B, C와 휴식을 취한 직후가 처음으로 같을 시점까지 900/60 = 15 번 작업하고, 15번 X 9개 = 135개의 마스크를 만들어 냅니다.
B는 900/75 = 12번의 작업을 반복하고 12턴 X 15개 = 180개,
C는 900/90 = 10번의 작업을 반복하고 10턴 X 25개 = 250개의 마스크를 만들어 냅니다.

따라서, A, B, C가 하루에 제작한 마스크의 총 개수는 135개 + 180개 + 250개 = 565개가 됩니다.

멱집합

어떤 집합이 있을 때, 이 집합의 모든 부분집합

부분집합을 나열하는 방법 ⇒ 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정

Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.
- Step B: 2를 제외한 {3}의 부분집합을 나열합니다.
  - Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}
  - Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}
- Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.
  - Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}
Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.
- Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열합니다.
  - Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}
  - Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}

원소가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합의 요소가 n 개일 때 모든 부분집합의 개수는 2^n개

순환구조 → 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법 (재귀 응용 가능)

코플릿

해설

5. [중복순열] 가위바위보

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

입력: 없음

출력:

2차원 배열(arr[i])을 리턴해야 합니다.
arr[i]는 전체 경우의 수 중 한 가지 경우(총 세 번의 선택)를 의미하는 배열입니다.
arr[i]는 'rock', 'paper', 'scissors' 중 한 가지 이상을 요소로 갖는 배열입니다.
arr[i].length는 3

주의 사항:

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

let output = rockPaperScissors();

console.log(output);
/*
    [
      ["rock", "rock", "rock"],
      ["rock", "rock", "paper"],
      ["rock", "rock", "scissors"],
      ["rock", "paper", "rock"],
      // ...etc ...
    ]
  */

ADVANCED: 가위바위보 게임의 수를 나타내는 양의 정수 rounds가 주어질 경우, 해당 rounds 동안 선택할 수 있는 모든 경우의 수를 리턴하도록 함수를 작성해 보세요.

let output = rockPaperScissors(5);

console.log(output);
/*
    [
      ["rock", "rock", "rock", "rock", "rock"],
      ["rock", "rock", , "rock", "rock", "paper"],
      ["rock", "rock", , "rock", "rock", "scissors"],
      ["rock", "rock", "rock", "paper", "rock"],
      ["rock", "rock", "rock", "paper", "paper"],
      ["rock", "rock", "rock", "paper", "scissors"],
      ["rock", "rock", "rock", "scissors", "rock"],
      // ...etc ...
    ]
  */

function rockPaperScissors (num) {
  //1. 빈 배열 result 를 만들어준다.
  let result=[];
  //2. “rock”, “paper”, “scissors” 가 담긴배열을만들어준다.(rps)
  let rps=["rock", "paper", "scissors"];
  //ADVANCED3. for문을 정해진 수만큼돌리는게 아니라 전달인자로 받아온 숫자만큼 돌려야합니다.
  let rounds = num || 3; //num이 undefined일때 처리해주기 위해 3

  function recursion(arr){
    //탈출문
    if(arr.length===rounds){
      result.push(arr);
      return;
    }
    //중심로직
    for(let i=0;i<rps.length;i++){
      let newArr=[...arr,rps[i]]
      recursion(newArr);
    }
  }
  recursion([]);
  return result;
}

//3. rps를 순회하는삼중 for문을만든다
//4. 각 for문 마다 arr의 0, 1, 2 번째 index 에 바위, 보 , 가위를 순서대로담아준다.
//   for(let i=0;i<rps.length;i++){
//     let choice1=rps[i];
//     for(let j=0;j<rps.length;j++){
//       let choice2=rps[j];
//       for(let k=0;k<rps.length;k++){
//         let choice3=rps[k];
//   //5. result 에 arr. push한다.
//         result.push([choice1,choice2,choice3]);
//       }
//     }
//   }
//   //6. for문이모두끝나면 result를 리턴해준다.
//   return result;
// };

Algorithm 2020.12.07

6. [순열] 새로운 치킨 소스 레시피

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

N 가지의 재료 중에 단 M 가지만을 사용하여 조합한 모든 경우의 수 중 하나이다.
재료는 0과 1로만 이루어진 숫자로 암호화가 되어 있고, 항상 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

출력:

Number 타입을 반환해야 합니다.
- stuffArr가 [1, 10, 11000, 1111] 이고, choiceNum은 2라면 사용 가능한 재료는 [1, 10, 1111] 입니다. 조합할 수 있는 경우의 수는 6 가지입니다.

주의사항:

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

const output1 = newChickenRecipe([1, 10, 1100, 1111], 2);
console.log(output1);
/*
  [
    [1, 10], [1, 1100], [1, 1111],
    [10, 1], [10, 1100], [10, 1111],
    [1100, 1], [1100, 10], [1100, 1111],
    [1111, 1], [1111, 10], [1111, 1100]
  ];
*/

const output2 = newChickenRecipe([10000, 10, 1], 3);
console.log(output2); // []

function newChickenRecipe(stuffArr, choiceNum) {
  //1. result 선언하고 빈 배열 할당한다. 
  let result=[];

  //상한 재료 여부 판별 함수
  function isRotten(num){
    let str=String(num);
    let count=0;
    for(let i=0;i<str.length;i++){
      if(str[i]==="0"){
        count++
        if(count>=3){
          return false;
        }
      }
    }
    return true;
  }
  //신선한 재료를 일단 뽑자
  let freshStuff=stuffArr.filter((e)=>isRotten(e));
  freshStuff.sort((a,b)=>a-b); //그런 뒤에 오름차순으로 정렬해주자

  //만약, 주어진 재료 모두 사용할 수 없다면 빈 배열[]을 반환해야 합니다.
  //만약, 사용할 수 있는 재료가 choiceNum보다 작다면 빈 배열[] 을 반환해야 합니다.
  if(freshStuff.length===0||freshStuff.length<choiceNum){
    return [];
  }

  //선택한 재료를 담을 배열(bucket)을 만들어 함수의 전달인자로 전달한다. 
  function recipe(arr,bucket){
    //탈출문 bucket의 길이가 choiceNum과 같아질때 result에 push하고 재귀함수 종료
    if(bucket.length===choiceNum){
      result.push(bucket);
      return;
    }

    for(let i=0;i<arr.length;i++){
      //요소 하나를 선택하여
      let choice=arr[i];
      let newArr=arr.slice(); //원본 배열 건들지 않기 위해 원본 배열 복사
      //선택한 요소를 빼주고
      newArr.splice(i,1);
      //재귀 실행
      recipe(newArr, [...bucket, choice]);
    }
  }
  recipe(freshStuff,[]);
  return result;
}

7. [조합] 블랙잭은 지겨워

문제:

평범한 블랙잭 게임에서 수시로 패배하자 흥미가 떨어진 김코딩은 박타짜에게 게임룰을 변형하여 새로운 카드 놀이를 해 볼 것을 제안합니다.
새로운 룰은 다음과 같습니다.

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개입니다.

게임을 진행하기 전에 소수에 대해 아무런 지식이 없는 박타짜는 게임을 며칠 미룬 뒤, 게임의 룰을 따르는 함수를 만들기로 했습니다.
소수에 약한 박타짜를 도와 여러 장의 카드 중 세 장씩 조합해 소수가 되는 경우의 수를 리턴하는 함수를 완성해 주세요.

입력:

인자 1

cards: Array 3개 이상 50개 이하의 카드가 숫자로 들어 있는 배열

출력: number type return

주의 사항:

cards 에는 중복된 숫자의 카드는 들어있지 않습니다.
각 카드에 적힌 수는 1이상 1,000이하의 자연수입니다.

let output = boringBlackjack([1, 2, 3, 4]);
console.log(output); // 1

let output = boringBlackjack([2, 3, 4, 8, 13]);
console.log(output); // 3

function boringBlackjack(cards) {
  //count 선언 후, 0 할당
  let count=0;

  //소수 = 1보다 큰 자연수 중에 1과 자기 자신만을 약수로 갖는 수 
  //소수인지 판별하는 함수 만들기
  function isPrime(number){
    for(let i=2;i<number;i++){
      if(number%i===0){
        return false;
      }
    }
    return true;
  }
  //이전에 선택한 숫자를 건너뛰는 삼중 for문 작성
  for(let i=0;i<cards.length;i++){
    for(let j=i+1;j<cards.length;j++){
      for(let k=j+1;k<cards.length;k++){
        const number=cards[i]+cards[j]+cards[k]; //선택한 카드 3개의 합
        if(isPrime(number)){
          count++; //소수면 count +1
        }
      }
    }
  }
  return count;
}

8. [GCD] 빼빼로 데이

문제:

오늘은 빼빼로 데이입니다. 한 회사의 팀장은 출근길에 아몬드 빼빼로 M개와 누드 빼빼로 N개를 구매하여 아침 일찍 출근길에 나섰습니다.

팀장은 자신보다 먼저 출근해 있는 직원들에게 구매한 빼빼로를 전부 나누어 주려고 합니다.
단, 서로 질투하는 경우를 만들지 않기 위해 모든 직원들에게 공평하게 빼빼로를 나누어 주려고 합니다.
직원들은 각각의 빼빼로를 똑같은 개수만큼 받아야 합니다. 빼빼로를 쪼개서 줄 수는 없습니다.

하지만 회사에 도착하기 전이라 몇 명의 직원들이 있는지 모르는 상황입니다.
팀장이 아몬드 빼빼로를 4개, 누드 빼빼로를 8개를 구매 했다면, 다음과 같이 세 가지 방법으로 나누어 줄 수 있습니다.

출근한 직원이 1명이라면 아몬드 빼빼로 4개와 누드 빼빼로 8개를 줄 수 있습니다.
출근한 직원이 2명이라면 아몬드 빼빼로 2개와 누드 빼빼로 4개를 각각 줄 수 있습니다.
출근한 직원이 3명이라면 빼빼로를 남기지 않고 공평하게 주는 방법은 없습니다.
출근한 직원이 4명이라면 아몬드 빼빼로 1개와 누드 빼빼로 2개를 각각 줄 수 있습니다.

팀장은 출근한 직원 수에 따라 어떻게 빼빼로를 나누어 줄지 고민하고 있습니다.
여러분이 직원 수에 따라 빼빼로를 나누어 주는 방법을 구하는 솔루션을 제공해 주세요.

입력:

인자 1: M

Number 타입의 양의 정수 (1 ≤ M ≤ 1,000,000,000)

인자 2: N

Number 타입의 양의 정수 (1 ≤ N ≤ 1,000,000,000)

출력:

2차원 배열 output을 리턴해야 합니다.
output[i]은 다음과 같은 순서를 가진 길이 3의 배열입니다.
- [빼빼로를 받게 되는 직원의 수, 나누어 주는 아몬드 빼빼로의 수, 나누어 주는 누드 빼빼로의 수]
output은 output[i][0], 즉 '빼빼로를 받게 되는 직원의 수'를 기준으로 오름차순으로 정렬합니다.

let M = 4;
let N = 8;
let output = divideChocolateStick(M, N);
console.log(output);
// [[1, 4, 8], [2, 2, 4], [4, 1, 2]]

function divideChocolateStick(M, N) {
  //1. result를 선언하고 빈 배열을 할당한다.
  let result=[];
  //2. 두 수의 공약수를 찾는다.
  function findgcd(a,b){
    while(b!==0){
      let r=a%b;
      a=b;
      b=r;
    }
    return a;
  }
  let gcd=findgcd(M,N);
  //3. 가장 작은 공약수부터 시작해서 가장 큰 공약수 순서대로 순회
  //약수는 제곱근을 중심으로 해서 대칭이다. (시간복잡도 고려)
  let sqrt=Math.floor(Math.sqrt(gcd));
  for(let left=1;left<=sqrt;left++){
    if(gcd%left===0){
  //4. [공약수 , N/공약수 , M/공약수]를 result 에 push한다.
      result.push([left,M/left, N/left]);

      if(left*left<gcd){
        let right=gcd/left;
        result.push([right, M/right, N/right]);
      }
    }
  }
  // 최대 공약수의 약수를 오름차순으로 정렬합니다.
  //5. result를 리턴한다.
  result.sort((a,b)=>a[0]-b[0]);
  return result;
}

9. [멱집합] 집밥이 그리워

문제:

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

밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.

입력:

인자 1: sideDishes

String 타입의 영문으로 된 반찬이 나열되어 있는 배열

출력:

Array 타입을 리턴해야 합니다.
밥과 함께 먹을 수 있는 반찬의 모든 경우의 수가 담긴 배열

주의 사항:

반찬은 영문으로 작성이 되어 있습니다.
반찬은 중복되지 않습니다.
반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
반찬은 3개 이상 99개 이하입니다.
출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다.

let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
console.log(output);
/*
[ [], 
  [ 'eggroll' ], 
  [ 'eggroll', 'fishSoup' ], 
  [ 'eggroll', 'fishSoup', 'kimchi' ], 
  [ 'eggroll', 'kimchi' ], 
  [ 'fishSoup' ], 
  [ 'fishSoup', 'kimchi' ], 
  [ 'kimchi' ]
] 
*/

function missHouseMeal(sideDishes) {
  //1. result를 선언하고, 빈 배열을 할당한다.
  let result=[];
  //2. sideDishes배열을 정렬해준다(sort)
  sideDishes.sort();
  //3. sideDishes 첫 요소부터 마지막 요소까지 순회하면서 각각의 요소를 배열에 넣어주거나, 넣지않는다.(재귀함수형태로구현한다.)
  function recursion(subset, start){
  //4. 마지막 요소까지 순회가 끝나면, 요소들을 담고있는 배열을 result에 push한다.
    result.push(subset);

    for(let i=start; i<sideDishes.length;i++){
      recursion(subset.concat(sideDishes[i]),i+1);
    }
  }
  //5. 만들어진 재귀함수를 실행한다.
  recursion([],0);
  //6. result를 리턴한다.
  return result;
}

Davina

[많을 (다) 빛날 (빈)] 빛이나는 사람이 되고 싶습니다

이전 포스트

DAY76. [자료구조/알고리즘] 코테 준비

다음 포스트

DAY77. [자료구조/알고리즘] 코테 준비2

코드스테이츠 FE - section4

Algorithm with Math

순열과 조합

순열 (Permutation)

조합 (Combination)

예제

GCD & LCM

GCD(Greatest Common Divisor) 최대공약수

LCM(Lowest Common Multiple) 최대공배수

유클리드 호제법

예제

멱집합

코플릿

5. [중복순열] 가위바위보

6. [순열] 새로운 치킨 소스 레시피

7. [조합] 블랙잭은 지겨워

8. [GCD] 빼빼로 데이

9. [멱집합] 집밥이 그리워

DAY76. [자료구조/알고리즘] 코테 준비

DAY77. 정규표현식

0개의 댓글