코딩테스트를 준비하면서 알고리즘 문제풀이를 하고, 또 실제로 코딩테스트를 치면서 자주 만나는 유형의 문제가 바로 순열, 조합입니다 ! ( 당장 지난 주말 코테에서도 두 번 다 마주친 .. )
이제 순서를 신경 써야하는가 ? 중복이 가능한가 ? 에 따라서 순열, 조합, 중복 순열, 중복 조합중에 잘 판단을 해서 문제에 적용을 하면 되는데요 !
그래서 오늘은 순열, 중복 순열, 조합, 중복 조합 모두를 한 번 정리해보려 합니다 !!! 레츠꼬.. 🔥
서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수
자 이제 순열, 조합, 중복 순열, 중복 조합 모두가 n개에서 r개를 뽑는다는 것은 동일합니다. 순열의 정의에서 '정렬'이라는 단어가 순열의 특징을 나타내는데, 바로 순서가 있다는 겁니다.
[1,2]
와 [2,1]
은 순서가 다르기 때문에, 순열에서는 다른 것으로 카운팅 한다는 것 !이제 Java로 순열 코드를 어떻게 작성하면 좋을지 살펴봅시다 !
public class AlgorithmStudy {
public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
if(depth == r){
for(int num: out) System.out.print(num);
System.out.println();
return;
}
for(int i=0; i<arr.length; i++){
if(!visited[i]){
visited[i] = true;
out[depth] = arr[i];
permutation(arr, out, visited, depth+1, r);
visited[i] = false;
}
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
permutation(arr, new int[r], new boolean[arr.length], 0, r);
}
}
[2,1]
과 같은 경우죠 ! 따라서 탐색을 수행하는 반복문은 0부터 탐색을 시작해야합니다. 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수
이제 이 점을 고려해서 Java로 어떻게 구현하면 좋을지 살펴봅시다 !
public class AlgorithmStudy {
public static void permutation(int[] arr, int[] out, int depth, int r){
if(depth == r){
for(int num: out) System.out.print(num);
System.out.println();
return;
}
for(int i=0; i<arr.length; i++){
out[depth] = arr[i];
permutation(arr, out, depth+1, r);
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
permutation(arr, new int[r], 0, r);
}
}
서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수
[1,2]
와 [2,1]
을 같은 것으로 취급한다는 것입니다. 그럼 이와 같은 특징을 고려하여 Java로 어떻게 작성하면 좋을지 살펴봅시다 !
public class AlgorithmStudy {
public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
if(depth == r){
for(int i=0; i<arr.length; i++){
if(visited[i]) System.out.print(arr[i]);
}
System.out.println();
return;
}
for(int i=start; i<arr.length; i++){
if(!visited[i]){
visited[i] = true;
combination(arr, visited, i+1, depth+1, r);
visited[i] = false;
}
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
combination(arr, new boolean[arr.length], 0, 0, r);
}
}
[1,2]
와 [2,1]
가 같다고 했기 때문에 이런 경우 [1,2]
만을 카운팅 해줍니다. 그러기 위해서 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행해줍니다. 이를 코드로 구현하기 위해서 탐색의 시작 index를 의미하는 start 원소를 사용해주었습니다. 탐색의 시작 기준을 start로 해주고, 재귀 호출을 할 때에는 현재 index인 i에 1을 더한 값을 start로 넣어주었습니다. 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
이제 이 특징을 고려하여 Java로 어떻게 구현하면 되는지 살펴봅시다 !
public class AlgorithmStudy {
public static void combination(int[] arr, int[] out, int start, int depth, int r){
if(depth == r){
for(int num : out) System.out.print(num);
System.out.println();
return;
}
for(int i=start; i<arr.length; i++){
out[depth] = arr[i];
combination(arr, out, i, depth+1, r);
}
}
public static void main(String[] args){
int[] arr = {1, 2, 3};
int r = 2;
combination(arr, new int[r], 0, 0, r);
}
}
이렇게 순열과 조합 총정리를 해봤습니다 ! 헷갈리지 않고, 고민하지 않고 이제 코테에서 완탐 문제는 바로바로 해결해봅시다 !
잘 읽었습니다!