[알고리즘] 순열/조합/부분집합
<여행사 BIG sale!>
- 출발, 도착 선택하면 모든 도시를 여행시켜 드립니다. 단 숙박비는 본인이 부담. (여행자가 A,B를 선택했다면 여행사는 어느 여행 코스를 선택할까?)
- 이동경비 최소
- “순열” 4P4
- 3개의 도시를 선택하면 3개 도시의 숙박비를 지원해드립니다. (여행자는 숙박비 지원만 고려했을 때 어느 도시를 선택할 때 가장 이득일까?)
- 숙박비 비싼 3개 도시
- “조합” 6C3
- 여행 도시를 선택할 때마다 추가 도시에 대해 할인. 2개 선택 10%, 3개 선택 20%, 4개 선택 30%, 이동 경비는 무료 (여행자가 70만원이 있다. 최대 개수의 도시를 선택하려면?)
- “부분집합” 6C6 → 6C5 → 6C4 → 6C3 → 6C2 → 6C1 → 6C0 ⇒ 2^6
<순열>
- 서로 다른 것 중에서 몇 개를 뽑아서 한 줄로 나열
- nPr = n(n-1)(n-2) ... (n-r+1)
- nPn = n!
- 다수의 알고리즘 문제: 순서화된 요소들의 집합에서 최선의 방법 찾는 것
- N개 요소들에 대해 n!개의 순열들이 존재
- 순열 만드는 방법
- 반복문
for i from 1 to 3 for i 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
- 재귀호출을 통한 순열 생성
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
-
for i 1 to 3 → i 기존 수 중복체크
- for j 1 to 3 → j 기존수 중복체크package com.ssafy.pcs; import java.util.Arrays; import java.util.Scanner; public class PermutationTest { static int N,R; static int[] 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); //처음에 아무것도안뽑았으니까 0 부터 시작. 재귀 돌때마다 증가 } //현재 자리에 수 뽑기 //cnt: 직전까지 뽑은 수 개수 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; //현재 자리에 input 넣기 numbers[cnt]= input[i]; //i 인덱스는 사용중이에용 isSelected[i]=true; //다음 수 뽑으러 가기 permutation(cnt+1); isSelected[i]=false; } } }
-
- 반복문
<조합>
- 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것
- combination
- nCr = n!/((n-r)!r!)
- nCr = n-1Cr-1 + n-1Cr → 재귀적 표현
-
반복문 → 순열과 다르게 중복체크x
for i from 1 to 4 for j from i+1 to 4 for k from j+1 to 4 print i,j,k
-
재귀를 이용한 조합
package com.ssafy.pcs; 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)3); return; } //<유도파트> for (int i=start;i<N;i++) { numbers[cnt]=input[i]; //다음자리는 현재 뽑은 i의 다음수부터 시작하도록 전달 combination(cnt+1,i+1); } } }
-
<완전 검색 활용- 주사위 던지기>
- 주사위를 3번 던져서 나올 수 있는 모든 경우 → “중복 순열”
- 주사위를 3번 던져서 모두 다른 수가 나올 수 있는 경우 → “순열”
- 주사위를 3번 던진 결과가 중복되는 경우를 제외하고 나오는 모든 경우 → “중복조합”
- 주사위 3번 던져 모두 다른 수가 나오는 경우 → “조합”
package com.ssafy.pcs; import java.util.Arrays; import java.util.Scanner; public class DiceTest { static int N; //주사위를 몇번 던질 건지 static int[] numbers;//뽑힌 주사위 눈들을 기억할 배열 static int totalCnt; //경우의 수가 잘 나오는지 확인 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N=sc.nextInt(); //던진 주사위 횟수 numbers = new int[N]; //차례대로 던져진 주사위 눈의 수 int M = sc.nextInt(); //던지기 모드(1-4) switch (M) { case 1: //주사위 던지기1: 중복순열 dice1(0); //아직 안던졌으니까 0 break; case 2: //주사위 던지기 2: 순열 dice2(0,new boolean[7]); break; case 3: dice3(0,1); break; case 4: dice4(0,1); break; default: break; } System.out.println("총 경우의 수 : "+totalCnt); } //주사위 던지기1 : 중복 순열 public static void dice1(int cnt) { //기본조건 if(cnt==N) { totalCnt++; //n번 다 던졌을때 카운트(총 경우의수) System.out.println(Arrays.toString(numbers)); return; } //유도조건 for(int i=1;i<=6;i++) {//i : 주사위 눈은 6까지 있음 numbers[cnt]=i; //중복허용하기 때문에 중복체크코드x dice1(cnt+1); } } //순열: nPr public static void dice2(int cnt,boolean[] isSelected) { if(cnt==N) { totalCnt++; System.out.println(Arrays.toString(numbers)); return; } for(int i=1;i<=6;i++) { //중복허용x if(isSelected[i]) { continue; } numbers[cnt]=i; isSelected[i]=true; dice2(cnt+1,isSelected); isSelected[i]=false; } } //중복조합 public static void dice3(int cnt, int start) { //기저조건 if(cnt==N){ totalCnt++; System.out.println(Arrays.toString(numbers)); return; } //유도파트 //중복 안되니까 시작을 정해줘야함 for(int i=start;i<=6;i++) { numbers[cnt]=i; dice3(cnt+1,i); //다음 주사위는 선택한 현재수부터 시도하도록 한다. } } //조합 public static void dice4(int cnt, int start) { //기저조건 if(cnt==N){ totalCnt++; System.out.println(Arrays.toString(numbers)); return; } //유도파트 //중복 안되니까 시작을 정해줘야함 for(int i=start;i<=6;i++) { numbers[cnt]=i; dice4(cnt+1,i+1); } } }
<완전 검색 - 부분 집합>
- 집합에 포함된 원소들을 선택
- 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분집합을 찾는 것
- 예) 배낭 짐싸기(knapsack)
- 부분집합의수 : 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개
- 부분집합 생성하는 방법
-
반복문
for i in 1 ->0 selected[1] <-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
-
입력된 숫자로 구성된 집합의 모든 부분집합(power set) 생성
-
재귀적 구현
input[] : 숫자 배열 isSelected[] : 부분집합에 포함/비포함 여부를 저장한 배열 generateSubSet(cnt) //cnt: 현재까지 처리한 원소개수 if(cnt==N) 부분집합 완성 else isSelected[cnt] <-true generateSubSet(cnt+1) isSelected[cnt] <-false generateSubSet(cnt+1) end generateSubSet(cnt+1)
-
Author And Source
이 문제에 관하여([알고리즘] 순열/조합/부분집합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wjddmstj123/알고리즘-StackQueue저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)