[알고리즘] 순열/조합/부분집합

<여행사 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)

좋은 웹페이지 즐겨찾기