## 순열 (Permutation) 순열은 서로 다른 n개 중에서 r개를 선택하여 **순서를 고려**하여 나열하는 것입니다. 수식으로는 $_nP_r$ 로 표현합니다. ### 순열의 특징 1. 순서가 다르면 다른 경우로 취급 2. 순서를 정하는 경우의 수를 구할 때 사용 3. $_nP_r = \frac{n!}{(n-r)!}$ ### 예시 4명을 3명씩 줄 세우는 경우의 수 ($_4P_3$) - 첫 번째 자리에 올 수 있는 사람: 4명 - 두 번째 자리에 올 수 있는 사람: 3명 - 세 번째 자리에 올 수 있는 사람: 2명 - $_4P_3 = 4 \times 3 \times 2 = 24$ 가지 ### 순열 구현 (Python) ```python def dfs(): if len(selected) == m: print(selected) return for i in range(len(numbers)): if numbers[i] in selected: continue selected.append(numbers[i]) dfs() selected.pop() # 3개 선택하는 순열 m = 3 numbers = [1, 2, 3, 4, 5] selected = [] dfs() ``` ## 중복 순열 (Permutation with Repetition) 중복 순열은 서로 다른 n개 중에서 r개를 선택하여 **순서를 고려**하여 나열할 때, **중복을 허용**하는 것입니다. 수식으로는 $_n\Pi_r$ 로 표현합니다. # 순열과 조합 ### 중복 순열의 특징 1. 순서가 다르면 다른 경우로 취급 2. 중복 선택이 가능 3. $_n\Pi_r = n^r$ ### 예시 주사위를 3번 던지는 경우의 수 ($_6\Pi_3$) - 첫 번째 던질 때 나올 수 있는 수: 6가지 - 두 번째 던질 때 나올 수 있는 수: 6가지 - 세 번째 던질 때 나올 수 있는 수: 6가지 - $_6\Pi_3 = 6 \times 6 \times 6 = 216$ 가지 ### 중복 순열 구현 (Python) ```python def dfs(): if len(selected) == m: print(selected) return for i in range(len(numbers)): selected.append(numbers[i]) dfs() selected.pop() # 3개 선택하는 중복순열 m = 3 numbers = [1, 2, 3, 4, 5] selected = [] dfs() ``` ## 조합 (Combination) 조합은 서로 다른 n개 중에서 r개를 선택할 때, **순서를 고려하지 않고** 선택하는 것입니다. 수식으로는 $_nC_r$ 로 표현합니다. ### 조합의 특징 1. 순서가 달라도 같은 것으로 취급 2. 선택만 하는 경우의 수를 구할 때 사용 3. $_nC_r = \frac{n!}{r!(n-r)!}$ 4. $_nC_r = {_nC_{n-r}}$ ### 예시 4명 중 3명을 선택하는 경우의 수 ($_4C_3$) - 순서는 고려하지 않음 - $_4C_3 = \frac{4!}{3!(4-3)!} = \frac{24}{6} = 4$ 가지 ### 조합 구현 (Python) ```python def dfs(start): if len(selected) == m: print(selected) return for i in range(start, len(numbers)): if numbers[i] in selected: continue selected.append(numbers[i]) dfs(i + 1) selected.pop() # 3개 선택하는 조합 m = 3 numbers = [1, 2, 3, 4, 5] selected = [] dfs(0) ``` ## 중복 조합 (Combination with Repetition) 중복 조합은 서로 다른 n개 중에서 r개를 선택할 때, **순서를 고려하지 않고**, **중복을 허용**하여 선택하는 것입니다. 수식으로는 $_nH_r$ 로 표현합니다. ### 중복 조합의 특징 1. 순서가 달라도 같은 것으로 취급 2. 중복 선택이 가능 3. $_nH_r = _{n+r-1}C_r$ ### 예시 아이스크림 3가지 맛 중 2개를 선택하는 경우의 수 (중복 허용) ($_3H_2$) - 순서는 고려하지 않음 - 같은 맛을 2번 선택할 수 있음 - $_3H_2 = _4C_2 = 6$ 가지 ### 중복 조합 구현 (Python) ```python def dfs(start): if len(selected) == m: print(selected) return for i in range(start, len(numbers)): selected.append(numbers[i]) dfs(i) # 다음 숫자를 고를 때 현재 인덱스부터 시작 (중복 허용) selected.pop() # 3개 선택하는 중복조합 m = 3 numbers = [1, 2, 3, 4, 5] selected = [] dfs(0) ``` ## 정리 각 개념의 핵심 특징: - 순열: 순서 고려 O, 중복 X - 중복 순열: 순서 고려 O, 중복 O - 조합: 순서 고려 X, 중복 X - 중복 조합: 순서 고려 X, 중복 O ## 연습 문제 (백준) ### 순열 연습 문제 1. [N과 M (1)](https://www.acmicpc.net/problem/15649) - 기본적인 순열 구현 2. [N과 M (5)](https://www.acmicpc.net/problem/15654) - 주어진 수로 순열 만들기 3. [차이를 최대로](https://www.acmicpc.net/problem/10819) - 순열을 활용한 완전탐색 ### 중복 순열 연습 문제 1. [N과 M (3)](https://www.acmicpc.net/problem/15651) - 기본적인 중복 순열 2. [N과 M (7)](https://www.acmicpc.net/problem/15656) - 주어진 수로 중복 순열 만들기 3. [암호 만들기](https://www.acmicpc.net/problem/1759) - 중복 순열 응용 ### 조합 연습 문제 1. [N과 M (2)](https://www.acmicpc.net/problem/15650) - 기본적인 조합 2. [N과 M (6)](https://www.acmicpc.net/problem/15655) - 주어진 수로 조합 만들기 3. [로또](https://www.acmicpc.net/problem/6603) - 조합의 실전 응용 ### 중복 조합 연습 문제 1. [N과 M (4)](https://www.acmicpc.net/problem/15652) - 기본적인 중복 조합 2. [N과 M (8)](https://www.acmicpc.net/problem/15657) - 주어진 수로 중복 조합 만들기 3. [중복 조합](https://www.acmicpc.net/problem/2407) - 중복 조합 계산