2021년 8월 25일에 작성된 문서 1번 입니다.
자료 구조 배운 내용을 정리했습니다.

Algorithm with Math - 순열 / 조합

문제: 카드 뽑기

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

1. 순서를 생각하며 3장을 선택

2. 순서를 생각하지 않고 선택.

   
   
   

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

조건 1을 만족하는 모든 경우의 수

1번 조건에서 모든 경우의 수를 구할 때에는 모든 카드를 1장씩 나열하면서 나열된 카드가 3장에 도달하면 카드의 나열을 중지합니다.

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

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

총 5 X 4 X 3 = 60 가지의 방법이 있다.

순열 : n 개 중에서 일부만을 선택하여 나열하는 것.
순서를 지키며 나열해야 한다.

순열 공식은 아래에 나와 있다.

• 5장에서 3장을 선택하는 모든 순열 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
• 일반식 : nPr = n! / (n - r)!
• ! (factorial) : n! 은 n에서부터 1씩 감소하여 1까지의 모든 정수의 곱. (n 보다 작거나 같은 모든 양의 정수의 곱.)
• 5! = 5 X (5 - 1) X (5 - 2) X (5 - 3) X (5 - 4) = 5 X 4 X 3 X 2 X 1 = 120
• 팩토리얼에서 0!과 1!은 모두 1.

조건 2를 만족하는 모든 경우의 수

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

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

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

조합 : 순서를 고려하지 않는다.

조합 공식은 아래에 나와 있다.

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

문제: 소수 찾기

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

이 문제에는 순열이 숨어 있다. 문제의 해결책을 세운다면, 아래와 같다.

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

문제: 일곱 난쟁이

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

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

Written with StackEdit.