순열과 조합
순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는
▶ P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r - 1) = n! / (n - r)!
상황에 따라서는 주어지는 Data가 나올 수 있는 모든 경우가 필요할 수 있다.
- 순서 의미 O → 순열
- 순서 의미 X → 조합
- 중복 허용
순열 접근 방식
① P(4, 3) = 4 x 3 x 2
② P(4, 3) = 4개 중 1개 선택 x 3개 중 1개 선택 x 2개 중 1개 선택
③ 재귀탐색하는 모습은 아래와 같다.
| [1, 2, 3, 4] 에서 『1』 선택 | [2, 3, 4] 에서 『2』 선택 | [3, 4] 에서 『3』 선택 ▶ 1 2 3 |
| [3, 4] 에서 『4』 선택 ▶ 1 2 4 | ||
| [2, 3, 4] 에서 『3』 선택 | [2, 4] 에서 『2』 선택 ▶ 1 3 2 | |
| [2, 4] 에서 『4』 선택 ▶ 1 3 4 | ||
| [2, 3, 4] 에서 『4』 선택 | [2, 3] 에서 『2』 선택 ▶ 1 4 2 | |
| [2, 3] 에서 『3』 선택 ▶ 1 4 3 |
과정 ③을 처음 [1, 2, 3, 4]에서 2~4를 선택한 경우를 반복
순열 및 조합 구성할 때는 재귀 (DFS)를 이용하면 된다.
[BOJ] N과 M 모음
| 순열 (Combination) | 조합 (Combination) | |||
| 중복되는 결과 허용 여부 | 중복 허용 X | 중복 허용 O | 중복 허용 X | 중복 허용 O |
| 1~N 중에서 선택 (Input Data 중복 X) |
N과 M (1) | N과 M (3) | N과 M (2) | N과 M (4) |
| 임의의 데이터 M개 선택 (Input Data 중복 X) |
N과 M(5) | N과 M(7) | N과 M(6) | N과 M(8) |
| 임의의 데이터 M개 선택 (Input Data 중복 O) |
N과 M(9) | N과 M(11) | N과 M(10) | N과 M(12) |
문제 [1] ~ [4]
- 주어지는 개수(N)에 따라 [1...N]의 숫자 중 M개 선택
문제 [5] ~ [8]
- 주어지는 개수(N)에 따라 임의로 주어지는 원소 중 M개 선택
- 주어지는 원소는 중복되지 않는 것을 보장
ex) {3, 7, 5}
- 원소가 정렬되지 않은 상태로 주어질 수 있다.
- 문제 조건에서 사전순 출력하라고 언급되어 있는데
출력되는 모든 Case가 전체적으로 사전순을 의미하는 것이다.
순열 {3, 1, 2} 자체는 사전순이 아니지만 순열의 Case 중에 해당된다.
해당 Case가 {1, 3, 2}와 {3, 2, 1}와 {2, 1, 3} 등의 Case 보다 앞서서 출력되면 안된다.
▶ 사전순으로 출력하기 위해 원소를 정렬 후에 순열/조합 처리
문제 [9] ~ [12]
- 주어지는 개수(N) 따라 임의로 주어지는 원소 중 M개 선택
- 주어지는 원소가 중복될 수 있다.
ex) {3, 7, 7, 3, 5}
- 주어지는 원소는 정렬되지 않은 상태로 주어질 수 있다.
- 전체 출력은 사전순으로 출력된다.
▶ 사전순 출력을 위해 원소를 정렬하고, 이미 선택된 숫자를 제외해야 한다.
조합 접근 방식 및 예제
1부터 차례대로 번호 매겨진 N개의 원소 중 4개를 고르는 모든 경우
6C4 구하는 예제
public class Main{
public static void main(String[] args) {
int N = 6;
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = i+1;
}
int count = 0;
for(int i=0; i < N; i++) {
for(int j=i+1; j < N; j++) {
for(int k=j+1; k < N; k++) {
for(int p=k+1; p < N; p++) {
System.out.print("( ");
System.out.print(arr[i] + ", ");
System.out.print(arr[j] + ", ");
System.out.print(arr[k] + ", ");
System.out.print(arr[p] + " ");
System.out.println(")");
count++;
}
}
}
}
System.out.println(count++);
}
}
개수만큼 for문을 만들어야 하는 한계가 있다.
위 형태를 재귀함수(recursive function) 혹은 재귀호출(recursion) 표현할 수 있다.
- 뽑은 원소들의 총 개수
- 더 골러야 할 원소들의 개수
- 지금까지 고른 원소들의 번호
public class Main{
static int N;
static int[] arr;
static int count;
public static void main(String[] args) {
N = 6;
arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = i+1;
}
pick(0, 0);
System.out.println(count);
}
static void pick(int startIdx, int cnt) {
if(cnt == 4) { // 4개 다 뽑았으면 stop
checkPickArr(); // 뽑은 원소 확인하기
return;
}
for(int i=startIdx; i<N; i++) {
// 아직 뽑아지지 않은 숫자라면
if(arr[i] != -1) {
arr[i] = -1; // 뽑은 표시
pick(i+1, cnt + 1);
arr[i] = i+1; // 다음 경우를 위해 원소값을 원상 복구
}
}
}
static void checkPickArr() {
System.out.print("( ");
for(int i=0; i<N; i++) {
if(arr[i] == -1) {
System.out.print((i+1) + " ");
}
}
System.out.println(")");
count++;
}
}
Reference
- [SWEA] 4747 사막에서 만난 지니 (중복 허용하지 않는 조합)
- [SWEA] 3421 수제 버거 장인 (중복 없는 조합)
- [BOJ] 2309 일곱 난쟁이 (중복 없는 조합)
- [BOJ] 12101 1, 2, 3 더하기 2 (중복 조합)
'알고리즘' 카테고리의 다른 글
| freopen( )을 이용한 파일 입출력 (2) | 2021.05.24 |
|---|---|
| 동적계획법(Dynamic Programming, DP) (0) | 2021.05.22 |
| 아스키(Ascii) 코드 활용 (1) | 2021.05.06 |
| [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++) (0) | 2021.05.05 |
| [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기 (2) | 2021.05.05 |
댓글