0. 설명 하려는 것
(1) 순열, 조합, 중복 순열, 중복 조합의 정의
(2) JAVA 언어를 썼을 때, 구현 방법
1. 순열
(1) 순열의 뜻
nPr = n 개 중에서 r개를 중복 없이 뽑아서 순서 있게 나열하는 것을 말한다. 따라서 {1, 2, 3, 4, 5} 중 5P3 에서 {1, 2, 3} 과 {1, 3, 2}는 다른 숫자이다.
(2) 구현 방법
순열은 재귀로 구현한다. 순열을 재귀로 구현하기 위해서는 다음과 같은 구성요소들이 필요하다.
- 전체 원소들에 대한 방문 배열 isVisited [] : 순열로 값을 뽑을 때, 중복이 없어야 하므로, 방문 배열을 통해, 이미 방문한 지점은 그냥 지나치도록 구현 해야 한다.
- 뽑힌 r개의 원소를 담을 배열 output [] : 전체 원소가 담긴 배열을 arr 이라 했을 때, 뽑힌 원소만 담을 배열 output 또한 필요하다.
- depth 변수 : 재귀가 몇 번째 깊이인지 나타내는 변수이다. 해당 변수가 바로 output 배열의 원소를 대입해야할 위치이다.
- 기저 조건 : output을 nPr 중 r의 크기를 넘어섰을 경우, (depth가 r일 경우), 더 이상, 원소를 n개 중에 고르는 연산을 그만하고, 문제에서 원하는 연산을 하도록 하는 기저 조건이 필요하다. 기저 조건 수행 후에는 이전 재귀로 돌아가야 한다. 따라서 맨 마지막에 return을 써줘야 한다.
방법은 다음과 같다.
- depth < r 일 때,
- arr[i]가 미방문한 지점일 경우, arr[i]를 방문으로 체크한다. output[depth] = arr[i]를 집어넣고, depth+1 의 재귀로 들어간다.
- arr[i]가 방문한 지점일 경우, for 문을 통해 arr[i+1]이 미방문인지 방문인지 확인한다.
- (i)번의 재귀가 끝나고 반환 되었을 경우, output[depth] = arr[i] 인 경우의 수는 다 본 것이다. 이제 for 문을 돌려서 output[depth] = arr[i+1]인 경우를 확인한다.
- depth == r 일 떄,
- 지금까지 뽑은 수들은 nPr을 충족했다. 해당 값들로 문제가 원하는 연산을 한다.
(3) 코드분석
// ⭐ 1번: 순열
// 순열이란? : nPr = n 개 중 r개를 중복 없이 뽑아서 순서를 고려하여 나열 하는 것
// 순서를 고려한다. => 1 3 2 와 1 2 3은 서로 다른 경우의 수이다.
/* 1. arr[] : 원본 배열
* 2. output[] : 출력하고자 하는 배열
* 3. visited[]: 방문 여부 체크
* 4. depth : 현재까지 뽑은 수의 개수
* 5. r : 총 뽑아야 하는 수의 개수
*/
public static void permutation(int [] arr, int [] output, boolean [] visited, int depth, int r) {
// 1. 기저 조건 (depth 가 r 이 되면, 값을 전부 뽑아서 일렬로 나열한 것이므로, 문제에서 원하는 행동을 행한다.)
// 0부터 셌기 때문에 depth == r이란 소리는 모두 세고 +1 해서 원래 세야할 수를 넘어섰다는 뜻이다.
// 따라서 여기서는 원래 행하던 'N개 중 r 뽑아서 일렬로 나열' 계산을 하지 않고, 조건 충족 시 해야할 계산을 행한다.
if(depth == r){
for(int temp: output){
if(temp == 0) {
continue;
}
System.out.print(temp + " ");
}
System.out.println();
// 1-1) 다른 경우의 수를 둘러보기 위해 이전 재귀로 돌아간다.
return;
}
// 2. nPr 실행
for (int i = 0; i < arr.length; i++) {
// 중복이 없어야 하므로, 방문 했으면 고려하지 않고 다음으로 넘어간다.
if(!visited[i]){
visited[i] = true;
// nPr의 현재 자리 수 = 방문하지 않은 값을 넣음
output[depth] = arr[i];
// 다음 수를 세러 넘어간다.
permutation(arr,output,visited, depth+1, r);
// output[1] = 1, output[2] = 5 라고 하고 , 현 depth = 2, i = 5 라고 하자.
// 재귀를 끝내고 돌아왔다는 것은 {1,5, ...} 의 모든 경우를 보고 왔다는 것이다.
// 따라서 i = 5는 다른 위치에서 경우의 수를 셀 때 필요하므로, 미방문으로 전환한다.
visited[i] = false;
}
// 이제 loop가 다음으로 넘어갈 것이고, depth = 2에서 i = 6인 모든 경우의 수를 볼 것이다.
}
}2. 조합
(1) 조합의 정의
nCr이란 n개 중에서 r개를 뽑는 경우의 수이다. 순열과의 차이점은 nCr의 경우, 순서를 고려하지 않는다는 점이다.
(2) 구현 방법
순열과 다르게 인수로 start 변수를 둔다. **start 변수**는 해당 index 지점부터 숫자를 고르도록 하는 변수이다. 해당 변수가 필요한 이유는 다음과 같다. {1, 2, 3, 4, 5}에서, 5C3을 구해보자. 만약 1부터 시작하여 3개를 골랐을 경우, 1,2,3 1,2,4 .... 1,4,5 정도가 될 것이다. 다음 2부터 시작하여 3개를 골라보자. 2,1,3 이 가능한 숫자인가? 아니다. 왜냐하면 1을 셀 때 셌기 때문이다. 이처럼, **1부터 시작하여 그보다 큰 수 중에 남은 2개를 고르는 경우의 수가 이미 1과 2 를 골랐을 떄 나올 수 있는 모든 경우의 수를 포함하고 있다!** 따라서, 2부터 셀 때는 1을 고려하지 말고 2보다 큰 3부터 끝까지의 수를 고르면 된다. 이는 3부터 시작할 때, 4부터 시작할 때, 5부터 시작할 때, 모두 같다.
(3) 코드 분석
// ⭐ 2번: 조합
/*
* 1) 순열과 다른 점
* 순열과 다르게, 조합은 start 변수를 둔다.
* start 변수는 조합에 포함할 값을 찾는 행위를 시작해야할 지점이다.
*
* 왜 이런가?
* 조합은 순서를 고려하지 않는다.
* 예를 들어 {1,2,3,4,5,6}의 배열에 관하여 6C3을 구한다고 하자.
* 처음 1을 포함하여 3개를 고르는 수에서 2를 포함하는 모든 경우의 수, 3을 포함하는 모든 경우의 수를 다 구했다.
* 따라서 그 후 2를 포함하여 3개 고르는 수에서 1을 포함하는 경우는 이미 전에 모두 계산했기에 포함할 필요가 없다.
*
* arr = 총 배열, output = 총 배열에서 r 개 중복없이 선택한 수가 들어있는 배열
* start = 선택의 시작점 depth = 지금까지 선택한 수의 개수
* r = 총 선택해야할 수의 개수
* */
public static void Combination (int [] arr, int [] output, int start, int depth, int r ) {
// 1) 기저 조건
if(depth == r){
for(int temp: output){
if (temp == 0) {
continue;
}
System.out.print(temp + " ");
}
System.out.println();
return;
}
// 2) nCr 계산
for (int i = start; i < arr.length; i++) {
output[depth] = arr[i];
Combination(arr,output,i+1, depth+1, r);
}
}3. 중복 순열
(1) 정의
n개 중에 중복이 가능한 r개를 뽑아서 순서 있게 나열하는 것을 말한다.
(2) 구현 방법
순열을 구현할 때, 방문 배열이 왜 필요 했는가? 이유는, 중복을 제거하기 위함이었다. 이제 중복이 허용되므로 해당 방문 배열이 필요 없어졌다. 따라서 구현은 다음과 같다.
- depth < r 일 때, 방문 했는지 여부 상관 없이 output[depth] = arr[i]를 집어넣는다. 어짜피 1,1,1,1,1 이 되면 1로만 할 수 있는 모든 경우의 수를 봤으므로, 제일 깊숙한 depth의 for 문이 다음 값으로 넘어간다. 따라서 1,1,1,1,2 가 된다.
- depth == r 일 때, 이제 문제에서 원하는 일을 하면 된다.
(3) 코드 분석
// ⭐ 3번: 중복 순열
/*
* 1) 순열과의 차이점:
* 방문 배열이 더 이상 필요 없다. -> 같은 수도 세어서 순서를 고려하여 나열하면 된다.
* 같은 수 세는 경우 다 세면 for 문이 자동으로 그 다음 수를 고려 할 것이다.
* 예를 들어 5ㅠ5 를 구하는 경우,
* 1,1,1,1,1 다 세면 자동으로 5번째 depth의 포문이 자동으로 2로 넘어가서
* 1,1,1,1,2 가 세어진다. 이것을 이용하면 된다.
*
*
* arr = 타겟 배열, output = 중복 순열 세면서 담은 값들(모든 경우의 수가 담긴다.)
* depth = 현재까지 뽑은 수의 개수 r = 총 뽑아야 할 개수
* */
public static void RepeatablePermutation (int [] arr, int [] output, int depth, int r ) {
// 1) 기저 조건
if(depth == r) {
for(int temp : output){
if(temp == 0) {continue;}
System.out.print( temp + " ");
}
System.out.println();
return;
}
for (int i = 0; i < arr.length; i++) {
output[depth] = arr[i];
RepeatablePermutation(arr,output,depth+1, r);
}
}4. 중복 조합
(1) 정의
중복이 가능하게 n개 중 r개를 뽑는 경우의 수
(2) 구현 방법
n개 중 중복 되게 r개를 뽑으면 된다. 위의 조합에서 보면 다음 재귀로 갈 때, start 인수에는 i+1이란 값을 집어넣었다. 그 이유는 같은 값부터 시작하는 경우의 수를 제거하기 위함이었다. 근데 이제 다음 depth에서도 같은 값부터 시작해도 된다. 왜냐하면 중복이 허용되기 때문이다. 따라서 코드는 다음과 같다.
(3) 코드 분석
// ⭐ 4번: 중복 조합
// 조합과 다른 점: 자기 자신도 선택할 수 있으므로, start를 i+1이 아닌 i 자체로 다음 재귀에 넘겨준다.
public static void RepeatableCombination (int [] arr, int [] output, int start, int depth, int r) {
// 1) 기저 조건
if(depth == r) {
for (int temp : output){
if(temp == 0) {continue;}
System.out.print(temp + " ");
}
System.out.println();
return;
}
for (int i = start; i < arr.length; i++) {
output[depth] = arr[i];
RepeatableCombination(arr,output,i,depth+1, r);
}
}'알고리즘 > 알고리즘-이론' 카테고리의 다른 글
| 자료 구조 완벽 정리! (0) | 2024.06.23 |
|---|---|
| JAVA 2차원 배열 (matrix) 회전 공식 완벽 정리! (0) | 2024.06.14 |
| 시간 복잡도의 개념과 코딩 테스트에서의 활용법 (0) | 2024.06.13 |
| 🖤알고리즘 이론 - BFS에 대하여 JAVA (0) | 2024.03.05 |
| 🖤LIS 알고리즘의 이론과 구현 (0) | 2024.01.05 |
