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

정은서·2022년 4월 6일
0

알고리즘

목록 보기
2/2

<여행사 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)
profile
정은서
이전 포스트

[알고리즘] Array

0개의 댓글