순열과 조합

leekoby·2023년 4월 6일

알고리즘 자료구조

[자료구조/알고리즘] 이론

목록 보기

15/17

🔧변경내용🔨

제목 날짜 내용
발행일 23.04.06

제목	날짜	내용
발행일	23.04.06

📌들어가기에 앞서

해당 포스트는 순열과 조합를 학습한 것을 정리한 내용입니다.

🌈 순열

순열(順列, permutation)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.

[그림] 사과, 오렌지, 레몬으로 이루어진 집합

여기 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있다.

만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 이번에는 순서에 상관있게 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까?

[그림] 3가지의 과일 중 2가지의 과일을 선택해 만든 순열

총 6개의 부분집합이 나올 수 있다.

왜냐하면 순열은 조합과 달리 순서도 따져서 부분집합을 만들기 때문이다.

즉 사과가 뒤로 가는 경우와 사과가 앞으로 가는 경우를 다르게 보고 각기 하나의 경우의 수로 치는 것이다.

그래서 {사과 오렌지} {오렌지 사과}가 다른 집합으로 취급될 수 있는 것이다.

순열의 식은 이렇게 표현된다.

순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현한다.

여기서 n은 원소의 총개수를 의미하고, r은 그중 뽑는 개수를 의미한다.

여기서 중요한 것은, 순열은 중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다는 것이다.

한 번 3P2의 값을 식으로 확인해보도록 하자.

이렇게 식으로 확인해 보았을 때도 6개의 부분조합이 도출됨을 알 수 있다.

🌈 조합

조합(組合, combination)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.

[그림] 사과, 오렌지, 레몬으로 이루어진 집합

여기 또다시 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있다.

만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 순서에 상관없는 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까?

[그림] 3가지의 과일 중 2가지의 과일을 선택해 만든 조합

총 3개의 부분집합이 나올 수 있을 것이다.

왜냐하면 조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이기 때문이다.

즉 사과가 뒤로 가든, 앞으로 가든 상관 없이 그저 사과 1개와 오렌지 1개가 있으면 하나의 경우의 수로 치는 것이다.

조합의 식은 이렇게 표현한다.

[그림] 조합식

조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현한다.

여기서 n은 원소의 총개수를 의미하고, r은 그중 뽑는 개수를 의미한다.

여기서 중요한 것은, 조합 또한 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다는 것이다.

과일이 3개가 있는데 4개, 5개를 뽑으라는 것처럼, 없는 것들을 뽑으라는 말과 똑같기 때문에 R은 최대 N개까지만 뽑을 수 있다.

한 번 3C2의 값을 식으로 확인해보도록 하자.

이렇게 식으로 확인해 보았을 때도 3개의 부분조합이 도출됨을 알 수 있다.

💻 순열과 조합을 이용한 문제들

앞서 나온 순열과 조합의 개념을 다시 한 번 복습하며 문제들을 보자.

시작하기 전에 알아두어야 할 용어

순열 :

요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수.

조합 :

순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수.

! (factorial, 팩토리얼) n! :

n에서부터 1씩 감소하여 1까지의 모든 정수의 곱
n 보다 작거나 같은 모든 양의 정수의 곱
팩토리얼에서, 0!과 1!은 모두 1

문제: 카드 뽑기

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

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

각 조건을 만족시키며 카드를 나열하는 방법은 각각 몇 가지일까요?

case 1. 순서를 생각하며 3장을 선택할 때의 모든 경우의 수

모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지한다.

해당 조건을 만족하려면, 다음과 같은 방법으로 경우의 수를 구한다.

첫번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있다.
첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법에는 네 가지가 있다.
두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법에는 세 가지가 있다.

따라서 5 X 4 X 3 = 60 가지의 방법이 있다.

이렇게 n 개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 한다.

순열은 순서를 지키며 나열해야 한다.

예를 들어 카드를 3장 뽑을 때, [A, B, D]와 [A, D, B] 두 경우 모두 A, B, 그리고 D라는 같은 카드를 3장 선택했지만, 나열하는 순서가 다르므로 서로 다른 경우로 파악해야 한다.

5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
일반식 : nPr = n! / (n - r)!
5! = 5 X (5 - 1) X (5 - 2) X (5 - 3) X (5 - 4) = 5 X 4 X 3 X 2 X 1 = 120

그렇다면, 순열의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까?

예) [A, B, C], [A, B, D], [A, B, E], [A, C, B] ... 등

// 반복문 코드
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();

result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수다.

반복문 3개로 구성된 이 순열 코드는 어렵지 않다.

반복문의 개수 === 요소를 뽑는 개수
- 5개의 요소 중 3개를 뽑는 조건 : 하나의 반복문당 5 개의 요소(lookup.length)를 순회하고, 반복문을 3번 중첩하여 3개의 요소를 뽑는다.

조금 더 풀어서 쓰자면 이러한 식이 된다.

// 반복문 1개당 1개의 요소를 뽑습니다.
  for (let i = 0; i < lookup.length; i++) {
		let pick1 = lookup[i];
    for (let j = 0; j < lookup.length; j++) {
			let pick2 = lookup[j];
      for (let k = 0; k < lookup.length; k++) {
				let pick3 = lookup[k];
 				if(i === j || j === k || k === i) continue;
        result.push([pick1, pick2, pick3])
      }
    }
  }

중복된 요소는 제거
같은 인덱스를 선택하는 것은, 중복된 요소를 선택한다는 것과 같다.
하지만 순열은 중복된 요소를 허용하지 않기 때문에, result에 넣기 전에, 동일한 인덱스인지 검사하고, 동일하다면 삽입하지 않고 다음으로 넘어간다.
AAA부터 EEE까지 전부 만드는 코드이지만, 중복 요소는 건너뛰므로써 순열이 완성된다.

결과

/* 
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
  [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
  [ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
  [ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
  [ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
  [ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
  [ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
  [ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
  [ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
  [ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
  [ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
  [ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
  [ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
  [ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
  [ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
  [ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
  [ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
  [ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
  [ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]
*/

case 2. 순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수

2번 조건에서 모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 한다.

다음과 같은 방법으로 경우의 수를 구한다.

순열로 구할 수 있는 경우를 찾는다.
순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.

먼저, 조합은 순열과 달리 순서를 고려하지 않는다.

만약 순열처럼 순서를 생각하여 경우의 수를 센다면, 조합이 아닌 것이다.

예를 들어 순열에서는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급한다.

다시 말해 순열에서처럼 순서를 생각하여 선택하면, 중복된 경우가 6배 발생한다.

여기서 나온 여섯 가지 경우의 수는 3장의 카드를 순서를 생각하여 나열한 모든 경우의 수다.

3장의 카드를 순열 공식에 적용한 결과가 3! / (3-3)! = (3 X 2 X 1) / 1 = 6 이다.

순서를 생각하느라 중복된 부분이 발생한 순열의 모든 가짓수를, 중복된 6가지로 나누어 주면 조합의 모든 경우의 수를 얻을 수 있다.

따라서 (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10 이다.

5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10
일반식: nCr = n! / (r! * (n - r)!)

그렇다면, 조합의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까?

예) [A, B, C], [A, B, D]\, [A, B, E], [B, C, D] ... 등

// 반복문 코드
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();

순열과 마찬가지로 result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수다.

순열과 다른 점은, 반복의 조건에 있습니다. (i = 0, j = i + 1, k = j + 1)

한 번 조합한 요소는 다시 조합하지 않는다.

하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음, 그 요소를 반복에 포함하지 않고 다음 요소부터 시작한다.

/*
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ], [ 'A', 'D', 'E' ],
  [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ], [ 'B', 'D', 'E' ], 
	[ 'C', 'D', 'E' ]
]
*/

보시다시피 반복문으로 순열과 조합을 만들어낼 수는 있다.

하지만, 분명한 한계점이 존재한다.

개수가 늘어나면 반복문의 수도 늘어난다.
- 만약, 11개의 요소 중 10개를 뽑아야 한다면, 10중 반복문을 구현해야 한다.
- 이는 굉장히 비효율적일 뿐더러 보기 좋은(쉬운) 코드에 부합하지도 않는다.
뽑아야 되는 개수가 n개처럼 변수로 들어왔을 때 대응이 어렵다.
- 요소 개수를 변수로 받는 건 요소 .length를 사용하여 대응할 수 있지만,
- 뽑아야 되는 개수도 변수로 받게 된다면 몇 개의 반복문을 설정해야 하는지, 설정은 어떻게 하는지 굉장히 까다로워질 것이다.

📌 그렇기에 순열과 조합은 재귀를 사용하여 풀이하는 경우가 많다.

순열 재귀


function permutationRecursive(lookup, numElements, used = new Set(), permutation = []) {
  // base case: 순열에 원하는 수의 원소가 있는 경우
  if (permutation.length === numElements) {
    return [permutation];
  }

  // recursive case: 배열에서 사용되지 않는 각 요소에 대해,
  // 현재 순열에 추가하고 재귀적으로 순열을 생성
  let result = [];
  for (let i = 0; i < lookup.length; i++) {
    if (used.has(i)) continue;
    let newPermutation = [...permutation, lookup[i]];
    let newUsed = new Set(used).add(i);
    let permutations = permutationRecursive(lookup, numElements, newUsed, newPermutation);
    result.push(...permutations);
  }

  return result;
}

호출

let lookup = ['A', 'B', 'C', 'D', 'E'];
let result = permutationRecursive(lookup, 3);
console.log(result);

순열 재귀 2

let arr = [2, 3, 4, 5]
let result = [];

const recursion = (count, burket) => {
  //base case
  if (count === 0) {
    // burket을 result에 넣고 여기서 burket은 일회용 배열임
    result.push(burket)
    // 아무것도 리턴하지 않음.
    return;
  }
  // 어쩃든 arr배열을 순회하긴 해야하니까 반복문 하나는 필요함
  for (let i = 0; i < arr.length; i++) {
    // 현재 요소 선언
    let curEl = arr[i]
    // 재귀
    recursion(count - 1, burket.concat(curEl))
  }
  // 마지막으로 result 리턴
}
  // 재귀 함수 실행 3은 3번 뽑기 그 다음 일회성 빈배열 선언
  recursion(3, [])

console.log(result);

조합 재귀

function combinationRecursive(lookup, numElements, startIndex = 0, combination = []) {
  // base case: 조합이 원하는 수의 요소를 가질 때
  if (combination.length === numElements) {
    return [combination];
  }

  // recursive case: 지정된 시작 인덱스에서 시작하는 각 인덱스에 대해 
  // 해당 인덱스의 요소를 현재 조합에 추가하고 
  // 나머지 인덱스와의 조합을 재귀적으로 생성
  let result = [];
  for (let i = startIndex; i < lookup.length; i++) {
    let newCombination = [...combination, lookup[i]];
    let newStartIndex = i + 1;
    let combinations = combinationRecursive(lookup, numElements, newStartIndex, newCombination);
    result.push(...combinations);
  }

  return result;
}

호출

let lookup = ['A', 'B', 'C', 'D', 'E'];
let result = combinationRecursive(lookup, 3);
console.log(result);

조합 재귀 2

let arr = [2, 3, 4, 5, 6, 7]
let result = [];

const recursion = (count, i, burket) => {
  // base case
  if (count === 0) {
    result.push(burket)
    return;
  }

  // for 문 한번 돌림
  for (; i < arr.length; i++) {
    let curEl = arr[i]
    // rescursive case
    recursion(count - 1, i + 1, burket.concat(curEl))
  }

  // 리턴
  return result;
}
// 재귀 함수 실행한번 하고
recursion(3, 0, []);
console.log(result)

문제: 소수 찾기

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

완전탐색 문제긴하지만, 이 문제에는 순열이 숨어 있다.

만약 이 사실을 알아차린다면, 문제를 보다 쉽게 해결할 수 있다.

순열을 이용한다면, 다음과 같이 전략을 세울 수 있다.

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

숫자는 순서에 의해 전혀 다른 값이 될 수 있다.

예를 들어 123과 321은 전혀 다른 숫자다.

만약 이 문제를 조합으로 접근하게 된다면, 123과 321은 같은 경우로 취급한다.

따라서, 순서를 고려하지 않고 k 개를 뽑아내는 조합으로는 이 문제를 해결할 수 없다.

// 소수 판별 함수
function isPrime(num) {
  if (num < 2) return false;
  if (num === 2) return true;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}
// 만들 수 있는 소수가 몇 개인지 구하는 함수
function solution(numbers) {
  const arr = numbers.split('');
  const answer = new Set();
  // 같은 숫자의 경우 한 번만 세야 하므로 Set 사용해주기
    // 만들 수 있는 모든 순열을 재귀적으로 찾기
  function getPermutation(numbersArray, fixedNumber) {
    if (numbersArray.length) {
      for (let i = 0; i < numbersArray.length; i++) {
        const temp = [...numbersArray];
        // fixedNumber를 제외한 숫자 배열을 재귀함수 호출 시 넘기기 위함
        temp.splice(i, 1);
        if (isPrime(parseInt(fixedNumber + numbersArray[i]))) {
          // 문자열을 parseInt 해서 넣어주어야 '011' 과 '11' 이 같은 숫자로 취급됨
          answer.add(parseInt(fixedNumber + numbersArray[i]));
        }
        getPermutation(temp, fixedNumber + numbersArray[i]);
      }
    }
  }
  
  getPermutation(arr, '');
  return answer.size;
}

문제: 일곱 난쟁이

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

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

const fs = require("fs");
const { arrayBuffer } = require("stream/consumers");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath)
    .toString()
    .trim()
    .split('\n')
    .map(Number);

let answer = input;
let sum = answer.reduce((a, b) => a + b, 0)

endOfCircuit: for (let i = 0; i < 8; i++) {
    for (let j = i + 1; j < 9; j++) {
        if ((sum - answer[i] - answer[j] === 100)) {
            answer.splice(j, 1)
            answer.splice(i, 1)
            break endOfCircuit;
        }
    }
}
console.log(answer.sort((a, b) => a - b).join('\n'));