[URECA] Day17 | 알고리즘 | 순두부가 아닌 순(열) 조(합) 부(분집합)

오늘 내용은 달달 외우기 ⭐
 

 

1) 일반순열 (순서 o, 중복 x, O(n!) )

package 순조부;

import java.util.Arrays;

public class 주사위_일반순열 {
	static int totalCnt; //완성된 순열의 수
	static int n;//주사위 던지는 횟수
	static int[]  results;//순열 결과를 저장할 배열
	static boolean[] isSelected;//중복을 피하기 위해 첫 판에서 어떤 수를 뽑았는지 마크해 놓을 배열
	
	public static void main(String[] args) {
		n=2; //2회
		results=new int[n];
		isSelected=new boolean[7];//0번 index는 쓰지 않고 1~6번 index까지만 활용함
		주사위던지기(0);
		System.out.println(totalCnt);
	}
	
	
	//주사위-일반순열(순서 o, 중복 x)
	public static void 주사위던지기(int cnt) {//cnt는 판의 횟수
		//ex. 주사위를 2번 던져서 나오는 모든 경우의 수, 한번 뽑은 걸 다시 뽑을 수 없음==> 중복 체크 코드 있음 : 30
		if(cnt==n) {// cnt는 판의 횟수
			totalCnt++;
			System.out.println(Arrays.toString(results));
			return;
		}
		
		for (int i = 1; i <= 6; i++) {
			if(isSelected[i]) continue;
			results[cnt]=i;
			isSelected[i]=true;
			주사위던지기(cnt+1);
			isSelected[i]=false;
			
		}
	}
	
}

 2)일반조합 (순서 x, 중복 x)

package 순조부;

import java.util.Arrays;

public class 주사위_일반조합 {
	static int totalCnt; // 완성된 조합의 수
	static int n;// 주사위 던지는 횟수
	static int[] results;// 조합 결과를 저장할 배열
	

	public static void main(String[] args) {
		n = 2; // 2회
		results = new int[n];
		
		//첫 번째 인수는 판 번호로 0부터 시작해야 배열에 집어 넣기 좋다.
		주사위던지기(0, 1);//두 번째 인수는 순서와 중복을 없애기 위한 아이디어.최초에는 주사위의 가장 작은 숫자 1부터 부여.
		System.out.println(totalCnt);
	}

	// 주사위-일반조합
	public static void 주사위던지기(int cnt, int start) {// 일반조합(순서 x,중복 x) 
		if (cnt == n) {
			totalCnt++; //최종 15
			System.out.println(Arrays.toString(results));
			return;
		}

		for (int i = start; i <= 6; i++) {
			results[cnt] = i;
			주사위던지기(cnt + 1, i + 1); //두 번째 판을 던지러 갈 때 지금의 i 값보다 1큰수로 시작하게 하면 중복과 순서를 모두 피할 수 있다
		}
	}

}

 3) 부분집합 (O(2^n))

package test;

public class A03_주사위_부분집합 {	
	static int totalCnt; // 부분집합의 총 개수를 저장하는 변수	
	static int[] input={1, 2, 3, 4, 5, 6};// 주사위의 숫자를 가진 배열	
	static boolean[] isSelected;// 각 숫자가 선택되었는지를 저장하는 배열
	
	public static void main(String[] args) {		
		
		isSelected = new boolean[6];	// 선택 여부를 저장할 배열 초기화		
		subset(0);// 부분집합 생성 함수 호출		
		
		System.out.println(totalCnt);// 생성된 부분집합의 총 개수 출력
	}
	
	// 부분집합 생성 함수
	public static void subset(int cnt) {
		// cnt가 6이면 모든 원소를 고려한 상태이므로 부분집합을 하나 완성한 것
		if (cnt == 6) {
			// 완성된 하나의 부분집합 개수 증가
			++totalCnt;
			// 현재 완성된 부분집합 출력
			for (int i = 0; i < 6; i++) {
				// 선택된 원소는 출력하고, 선택되지 않은 원소는 "X"로 표시
				System.out.print((isSelected[i] ? input[i] : "X") + " ");
			}
			System.out.println(); 
			return; 
		}
		
		// 현재 원소를 선택하는 경우
		isSelected[cnt] = true; // 선택 상태로 설정
		subset(cnt + 1); // 다음 원소로 진행
		
		// 현재 원소를 비선택하는 경우
		isSelected[cnt] = false; // 비선택 상태로 설정
		subset(cnt + 1); // 다음 원소로 진행
	}
}