제육's 휘발성 코딩
Published 2022. 2. 13. 15:48
[JAVA] - 순열과 조합 🔷 Java/Basic
반응형

1. 완전 검색

image

2. 순열(Permutation)

  • 서로 다른 n개 중 r개를 선택하는 과정에서 순서가 의미가 있는 경우 - nPr
  • 예 ) 5개의 도시 중 출발지와 도착지가 같은 최소 비용 거리

2.1. 반복문

<code />
// {1, 2, 3}을 포함한 모든 순열 생성 : 3P3 // 동작 과정 1. 1~3 수 선택 시도, 2. 중복 수 필터링, 3. 다음 자릿수 선택 - 선택 이후 1,2,3 반복 for i from 1 to 3 // 처음 수 선택 for j from 1 to 3 // 두번째 수 선택 if j != i then // 첫번째와 두번째가 다르다면 for k from 1 to 3 // 세번 째 수 선택 if k != i and k != j then // 세번째 수가 첫번째, 두번째와 다른 경우 print i,j,k // 세 수 선택 end if end for end if end for end for
  • 단점 : r중 반복문을 사용해야하므로 가변적인 순열에 대응할 수 없다.

2.2. 재귀

<code />
//numbers[] : 순열 저장 배열 //isSelected[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열 perm(cnt) // cnt : 현재까지 뽑은 순열 수의 개수 if cnt == 3 // 기저 조건 // 리턴 else for i from 1 to 3 if isSelected[i] == true then continue // 기존 수 중복 체크 numbers[cnt] <- i isSelected[i] <- true perm(cnt+1) // 다음 수 선택 isSelected[i] <- false end for
  • 재귀를 사용하면 스택에 r개만큼 쌓아서 가변적 순열처리가 가능하다.
<code />
import java.util.Arrays; import java.util.Scanner; public class PermutationTest { static int N, R; static int[] input, numbers; // input : 입력수 배열, numbers : 선택수 배열 static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N]; numbers = new int[R]; isSelected = new boolean[N]; for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } permutation(0); } // 현재 자리에 수 뽑기 public static void permutation(int cnt) { if (cnt == R) { System.out.println(Arrays.toString(numbers)); return; } // 입력받은 모든 수를 현재 자리에 넣어보기 for (int i = 0; i < N; i++) { // 기존자리의 수들과 중복되는지 체크 if (isSelected[i]) continue; numbers[cnt] = input[i]; isSelected[i] = true; // 다음 수 뽑으러 가기 permutation(cnt+1); isSelected[i] = false; } } }

2.3. 비트마스킹 - 순열

<code />
nPn -> N개의 원소로 만들 수 있는 모든 순열 생성 input[] : 숫자 배열 numbers[] : 순열 저장 배열 perm(cnt, flag) // cnt : 현재까지 뽑은 순열 원소의 개수, flag : 선택된 원소에 대한 비트정보를 표현하는 정수 if cnt == N // 리턴 else for i from 0 to N-1 if (flag & 1 << i) != 0 then continue numbers[cnt] <- input[i] perm(cnt+1, flag | 1 << i) end for end perm()
<code />
import java.util.Arrays; import java.util.Scanner; public class PermutationTest { static int N, R; static int[] input, numbers; // input : 입력수 배열, numbers : 선택수 배열 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N]; numbers = new int[R]; for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } permutation(0,0); } // cnt : 직전까지 뽑은 수 갯수, flag : 뽑힌 수들에 대한 플래그 비트열 public static void permutation(int cnt, int flag) { if (cnt == R) { System.out.println(Arrays.toString(numbers)); return; } for (int i = 0; i < N; i++) { if ((flag & 1 << i) != 0) continue; numbers[cnt] = input[i]; permutation(cnt+1, flag | 1 << i); } } }

2.4. NextPermutation

image

<code />
import java.util.Arrays; import java.util.Scanner; public class NextPermutationTest { static int N, input[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); input = new int[N]; for (int i=0; i<N; i++) { input[i] = sc.nextInt(); } Arrays.sort(input); do { System.out.println(Arrays.toString(input)); }while (np()); } private static boolean np() { // 1. 교환위치 찾기 int i = N-1; while(i>0 && input[i-1] >= input[i]) --i; if (i==0) return false; // 2. 교환위치에 교환할 값 찾기 int j = N-1; while(input[i-1] >= input[j]) --j; // 3. 교환위치와 교환할 값 교환하기 swap(i-1,j); // 4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들 수 있는 가장 작은 순열 생성 (오름차순 정렬) int k = N-1; while (i < k) { swap(i++, k--); } return true; } public static void swap(int i, int j) { int tmp = input[i]; input[i] = input[j]; input[j] = tmp; } }

3. 조합

  • 서로 다른 n개 중 r개를 선택하는 과정에서 순서가 의미없는 경우
  • 5개의 도시 중 3개를 선택할 때 가장 숙박비가 비싼 3개의 도시

3.1. 반복문

<code />
// 4C3 조합 - 순서가 의미가 없으므로 다음 수는 전수 +1 for i from 1 to 4 for j from i+1 to 4 for k from j+1 to 4 print i,j,k end for end for end for

3.2. 재귀

<code />
comb(cnt, start) if cnt == r // 리턴 else for i from start to n-1 numbers[cnt] <- input[i]; comb(cnt+1,i+1) end for end comb()
  • 다음 수는 전수+1부터 시작하게 하며, 순서가 의미가 없으므로 중복체크를 하지 않아도 된다.
<code />
import java.util.Arrays; import java.util.Scanner; public class CombinationTest { static int N,R; static int[] input, numbers; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N]; numbers = new int[R]; for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } combination(0, 0); } public static void combination(int cnt, int start) { if (cnt == R) { System.out.println(Arrays.toString(numbers)); return; } for (int i = start; i < N; i++) { numbers[cnt] = input[i]; combination(cnt+1, i); // 다음 자리는 현재 뽑은 i의 다음수부터 시작하도록 전달 } } }

3.3. NextPermutation

image

<code />
import java.util.Scanner; public class CombinationNPTest { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int R = sc.nextInt(); int[] input = new int[N]; for (int i=0; i<N; i++) { input[i] = sc.nextInt(); } int[] p = new int[N]; // p배열에 0보다 큰 값으로 R개를 맨뒤부터 채운다. // 4C2 0011 int cnt = 0; while(++cnt <= R) p[N-cnt] = 1; do { for (int i = 0; i < N; i++) { if (p[i] == 1) { System.out.print(input[i] +" "); } } System.out.println(); } while(np(p)); } private static boolean np(int[] p) { int N = p.length; // 1. 교환위치 찾기 int i = N-1; while(i>0 && p[i-1] >= p[i]) --i; if (i==0) return false; // 2. 교환위치에 교환할 값 찾기 int j = N-1; while(p[i-1] >= p[j]) --j; // 3. 교환위치와 교환할 값 교환하기 swap(p,i-1,j); // 4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들 수 있는 가장 작은 순열 생성 (오름차순 정렬) int k = N-1; while (i < k) { swap(p,i++, k--); } return true; } public static void swap(int[] p ,int i, int j) { int tmp = p[i]; p[i] = p[j]; p[j] = tmp; } }

4. 중복 순열, 중복 조합 예제

<code />
import java.util.Arrays; import java.util.Scanner; public class DiceTest { static int N, numbers[], totalCount; static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); // 던진 주사위 횟수 numbers = new int[N]; // 차례대로 던져진 주사위 눈의 수 int M = sc.nextInt(); switch (M) { case 1 : // 주사위 던지기1 : 중복순열 dice1(0); break; case 2 : // 주사위 던지기2 : 순열 dice2(0, new boolean[7]); break; case 3 : dice3(0,1); break; case 4 : // 주사위 던지기4 : 조합 dice4(0,1); break; default: break; } System.out.println("총 경우의 수 : " + totalCount); } // 주사위 던지기 1 : 중복 순열 public static void dice1(int cnt) { if(cnt == N) { totalCount++; System.out.println(Arrays.toString(numbers)); return; } for (int i = 1; i <= 6; i++) { numbers[cnt] = i; dice1(cnt+1); } } // 순열 : nPr public static void dice2(int cnt, boolean[] isSelected) { if(cnt == N) { totalCount++; System.out.println(Arrays.toString(numbers)); return; } for (int i = 1; i <= 6; i++) { if(isSelected[i]) continue; numbers[cnt] = i; isSelected[i] = true; dice2(cnt + 1, isSelected); isSelected[i] = false; } } // 중복조합 : nHr -> n+r-1Cr public static void dice3(int cnt, int start) { if (cnt == N) { totalCount++; System.out.println(Arrays.toString(numbers)); return; } for (int i = start; i <= 6; i++) { numbers[cnt] = i; dice4(cnt+1, i); } } // 조합 : nCr public static void dice4(int cnt, int start) { if(cnt == N) { totalCount++; System.out.println(Arrays.toString(numbers)); return; } for (int i = start; i <= 6; i++) { numbers[cnt] = i; dice4(cnt+1, i+1); } } }

5. 부분 집합

  • 조합의 모든 경우의 수 (5C1, 5C2, ... , 5C5)에서 5C0 까지 포함된 경우
  • 냅백 알고리즘과 같은 다수의 중요 알고리즘이 최적의 부분 집합을 찾는 것
  • 원소의 개수가 n개일 때 공집합을 포함한 부분 집합의 개수는 2^n 개

5.1. 반복문

<code />
// 1~3 집합의 모든 부분 집합 FOR i 1 -> 0 selected[i] <- i FOR j in 1 -> 0 selected[2] <- j FOR k in 1 -> 0 selected[3] <- k FOR m in 1 -> 3 if selected[i] == 1 then print i
  • 부분 집합의 원소가 몇개가 될지 모르므로 반복문으로 미리 코드를 짤 수가 없다.

5.2. 재귀

<code />
input[] : 숫자 배열 isSelected[] : 부분집합에 포함 / 비포함 여부를 저장한 배열 generateSubSet(cnt) // cnt : 현재까지 처리한 원소 개수 if (cnt == N) // 리턴 else isSelected[cnt] <- true generateSubSet(cnt+1) // 해당 원소를 선택한 경우 isSelected[cnt] <- false generateSubSet(cnt+1) // 해당 원소를 선택하지 않은 경우 end generateSubSet()
  • 간단하게 선택, 비선택으로 나누어 재귀를 호출한다.
<code />
import java.util.Scanner; public class SubSetTest { static int N, input[]; static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); input = new int[N]; isSelected = new boolean[N]; for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } generateSubset(0); } public static void generateSubset(int cnt) { // 부분집합에 고려해야 하는 원소의 개 if (cnt == N) { for (int i = 0; i < N; i++) { System.out.print((isSelected[i]?input[i]:"X")+" "); } System.out.println(); return; } // 현재 원소를 선택 isSelected[cnt] = true; generateSubset(cnt+1); // 현재 원소를 비선택 isSelected[cnt] = false; generateSubset(cnt+1); } }
반응형
profile

제육's 휘발성 코딩

@sasca37

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요! 맞구독은 언제나 환영입니다^^