순열과 조합

Vorhandenheit ·2021년 12월 13일

목록 보기

9/16

순열과 조합

1. 조합

n개 중에서 일부를 선택하여, 순서를 생각하지않고 나열하는 것을 조합이라고 합니다.

const getCombination = function (arr, selectNumber) {
	const result = []
    
    if (selectNumber === 1) return arr.map(el => [el]);
  
  arr.forEach((fixed, index, origin) => {
  	const rest = origin.slice(index +1);
    const combinations = getCombinations(rest, selectNumber -1);
    const attached = combinations.map(el => [fixed, ...el]);
    result.push(...attached);
  })
  return result
}

중복 순열

 const getPermutations = function (arr, selectNumber) {
    const result = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 

    arr.forEach((fixed, index, origin) => {
      const rest = origin
      // 일반 순열알고리즘에서 위의 rest 만 origin로 바뀐다
      const permutations = getPermutations(rest, selectNumber - 1); 
      const attached = permutations.map((el) => [fixed, ...el]); 
      result.push(...attached); 
    });

    return result; 
  }

2. 순열

n개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 합니다. 순열은 순서를 지키며 나열해야합니다.

const getPermutations = function (arr, selectNumber) {
	const result = []
    if (selectNumber === 1) return arr.map(el => [el]);
  
  arr.forEach((fixed, index, origin) => {
  	const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
    const permutations = getPermutations(rest, selectNumber -1);
    const attached = permutations.map(el => [fixed, ...el])
    result.push(...attached);
  });
  return result
}

의무과정만 다 나왔다면 다 아는 개념이니.. 많은 문제를 풀어서 익숙해보도록하자!

문제

1. 카드 뽑기

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

-조합 문제

const findCard = function (arr, selectNumber) {
	const result = []
    
    if (selectNumber === 1) return arr.map(el => [el]);
  
  arr.forEach((fixed, index, origin) => {
  	const rest = origin.slice(index +1);
    const combinations = findCard(rest, selectNumber -1);
    const attached = combinations.map(el => [fixed, ...el]);
    result.push(...attached);
  })
  return result
}

2. 소수 찾기

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

순열 문제

1.숫자의 모음을 가지고 순열을 통해 만들수 있는 모든 수를 담은 배열을 만들고
2.소수인지 체크를 한다

3. 일곱 난쟁이

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

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