Algorithm with Math - 순열 / 조합
문제: 카드 뽑기
여러분은 지금 [A, B, C, D, E] 5장의 카드를 갖고 있습니다. 이 5장의 카드 중 3장을 선택하여 나열한다고 하는데 두 가지 조건이 있습니다.
- 순서를 생각하며 3장을 선택합니다.
- 순서를 생각하지 않고 선택합니다.
각 조건의 나열 방법은 모두 몇 가지인가요?
1번 조건에서 모든 가짓수를 구할 때는 1장씩 나열하면서 필요한 장수까지 도달하면 중지합니다.
즉 다음과 같은 방법으로 구하게 됩니다.
1장째의 카드를 선택하는 방법에는 5가지가 있습니다.
그 각각에 대해 2번째 카드를 선택하는 방법에는 4가지가 있습니다.
그 각각에 대해 3번째 카드를 선택하는 방법에는 3가지가 있습니다.
따라서 5 X 4 X 3 = 60이 됩니다.
이렇게 n 개의 무언가 중 일부만을 선택하여 나열하는 것을 순열이라고 합니다. 순열은 순서를 생각하며 나열한다는 것에 주의하셔야 합니다. 예를 들어 3장을 뽑았을 때 ABD와 ADB 둘 다 모두 A, B, D라는 같은 3장의 카드를 선택한 것이지만 나열하는 순서가 다르므로 서로 다른 나열 방법으로 다루어 수를 셉니다.
[! 은 팩토리얼(factorial)로 n! 은 n 보다 작거나 같은 모든 양의 정수의 곱입니다.]
2번 조건에서 모든 가짓수를 구할 때는 3장을 하나의 그룹으로 선택한다는 것입니다. 다음과 같은 방법으로 구하게 됩니다.
먼저 순열과 마찬가지로 순서를 생각하며 셉니다.
중복해서 센 부분으로 나눗셈을 합니다.
우선 순열일 때와 마찬가지로 순서를 생각하여 가수 수를 센다면 조합으로서 올바르지 않습니다. 예를 들어 순열에서는 ABC, ACB, BAC, BCA, CAB, CBA 6가지는 모두 다른 것으로 취급하지만, 조합에서는 이 6가지를 하나의 그룹으로서 취급합니다. 즉, 순열에서처럼 순서를 생각하여 선택하면 6배 중복해서 가짓수를 세는 것이 됩니다.
여기서 나온 6이라는 수는 3장의 카드를 순서를 생각하여 나열한 모든 가짓수, 즉 3장을 치환할 때의 모든 가짓수(3 X 2 X 1)입니다. 순서를 생각하는 바람에 중복된 부분이 발생함으로 순열의 모든 가짓수를 중복되는 6가지로 나누면 조합의 모든 가짓수를 얻을 수 있습니다.
따라서 (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10이 됩니다.
조합은 일반화를 통해 Combination의 약자 C로 표현합니다.
5장에서 3장을 선택하는 모든 조합의 수 = 5C3 = 5! / (3! * 2!) = 10
예시를 통해 순열과 조합을 알아봤습니다. 이번에는 코딩 테스트에 나올법한 간단한 문제 예시에서 어떤 수학적 개념이 필요한지 알아봅시다.
문제: 소수 찾기
한 자리 숫자가 적힌 종잇조각이 흩어져있습니다. 흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이에 적힌 숫자가 적힌 배열이 주어진다면 종잇조각으로 만들 수 있는 소수는 몇 개인가요?
위 문제에서 순열이 숨어 있다는 것을 알아차린다면 쉽게 문제를 해결할 수 있습니다. 다음과 같이 전략을 세워볼 수 있습니다.
n 개의 숫자 중에 1~k 개를 뽑아서 순열을 생성합니다.
각 순열을 정수로 변환하고 해당 정수가 중복되지 않도록 하여 소수인지 검사합니다.
소수이면 개수를 셉니다.
만약 위 문제를 조합으로 접근하게 된다면 순서를 고려하지 않고 k 개를 뽑아내므로 조합으로는 풀 수 없습니다.
문제: 일곱 난쟁이
왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것입니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. 뛰어난 수학적 직관력을 가지고 있던 백설 공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈습니다. 아홉 난쟁이의 키를 줬을 때, 원래 백설 공주를 돕는 일곱 난쟁이를 찾는 방법은 무엇인가요?
위 문제는 조합을 이용해서 일곱 난쟁이를 찾을 수 있습니다. 일곱 난쟁이의 키의 합이 100이라고 주어졌기 때문에 9명의 난쟁이 중 7명의 난쟁이를 순서를 생각하지 않고 아 그 합이 100이 되는 경우를 찾으면 되는 문제입니다.
