Algorithm with Math - 순열, 조합 (nPr, nCr)

Algorithm with Math - 순열 / 조합

문제: 카드 뽑기

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

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

각 조건을 만족하면서 카드를 나열하는 방법은 모두 몇 가지인가요?

1. 순열 공식 : nPr = n! / (n - r)!
   • 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60 가지
2. 조합 공식: nCr = n! / (r! * (n - r)!)
   • 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10 가지

 

문제: 소수 찾기

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

이 문제에는 순열이 숨어 있습니다. 만약 이 사실을 알아차린다면, 문제를 보다 쉽게 해결할 수 있습니다.

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

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

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

예를 들어 123과 321은 전혀 다른 숫자이지만 이 문제를 조합으로 접근하게 된다면, 123과 321은 같은 경우로 취급합니다. 따라서, 순서를 고려하지 않고 k 개를 뽑아내는 조합으로는 이 문제를 해결할 수 없습니다.

 

문제: 일곱 난쟁이

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

 

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