스타와 링크 풀어보기
| n! ( = P(n, n) ) | P(n, r) | C(n, r) | Pie(n, r) | |
| 경우의수 | n! | n!/(n-r)! | n!/(n-r)!r! | n^r |
| t복잡도 | O(n!) | O(n^r) | O(n^min(r, n-r)) | O(n^r) |
| 백준풀이 | BF - 순서 | BF - 선택 | ||
| lvl의미 | 선택한 개수 | 선택지 인덱스 | ||
| r 간 순서 | 반영 | 무시 | 반영 | |
| 결과정렬 | 인덱싱 0부터/N-1부터 | 선택먼저/비선택먼저 | ||
| 구현 |
std::next_permutation 혹은 직접 구현 (아래 코드 참조) |
C(n, r)로 조합 구하고 next_permutation로 순서 정하기
|
BF(int i, int lvl){ if(lvl > r) return for(;i < n; ++i) BF(i + 1, lvl + 1); } |
BF(int lvl){ if(lvl > r) return for(int i = 0;i < n; ++i) BF(i + 1, lvl + 1); } |
|
자식 호출 횟수가 매번 다름(n번~n-r+1번) |
자식 호출 횟수가 매번 같음(n번) |
|||
| 예시 |
백준17406 배열 돌리기 : K 개의 연산 |
백준 15649 N과 M(1) |
백준 15650 N과 M(2) 백준 14502 연구소 : n 개의 빈칸 중 3개의 벽 선택 |
백준 16922 로마 숫자 만들기 : 4개 숫자(0~N) 선택 4가지 로마 숫자 종류, 각0~N개 까지 존재 가능 |
| 수학명칭 | factorial |
순열 |
조합 |
중복순열 |
| 수학풀이 | 서로 다른 n명을 일렬로 나열 |
서로 다른 n 명 중 r명을 일렬로 나열 |
서로다른 n 명 중 r명을 선택 |
서로 다른 n 명 중 r명을 중복을 허락하여 일렬로 나열 |