순열, 조합, 부분집합

순열, 조합, 부분집합은 탐색에서 자주 출제되는 유형이다. 

항상 헷갈렸었는데 정리해보자

 

 

순열: 순서가 의미있다!

 

 

  순열이란 ?
  순서가 의미있는 조합이다. 즉, 순서가 달라지면 그 의미도 달라진다. 
 
  예를들어) 주사위를 3번 던졌을때 나올수있는 모든 수의 순서를 구하라   
  이경우에 (1,3,5)와 (3,1,5)는 다른 경우이다. 
 
  조합과 다르게 현재 선택된 수보다 작은수를 다음에 선택할수있다
  -> visit배열을 이용하여 처리한다. 
 
  순열의 모든 경우를 구하려면 어떻게 해야할까?
  for문을 돌리며 result배열의 각 index에 수를 넣는다

 

 

import java.util.*;

public class 순열_연습 {

	static int[] result;
	static int[] visit;
	static int[] dice = {1, 2, 3, 4, 5, 6};
	
	
	static void permutation(int cnt) {
		
		if(cnt==3) {											// result 배열이 3개 채워졌다면, idx가0부터 시작이므로 idx가 3이라는건 3개채워진후 다음 상황
			System.out.println(Arrays.toString(result));		// 결과를 출력해라 
			return;												// 종료 
		}
		
		for(int i=0; i<6; i++) {
			if(visit[i]==0) {					//방문하지 않은곳이면 넣어라
				visit[i] = 1;					//방문처리
				result[cnt] = dice[i];			//결과를 나타낼 배열에 주사위 수를 저장
				permutation(cnt+1);				//결과배열의 다음 인덱스를 넣으러 재귀 호출 
				visit[i] = 0;					//재귀호출 다 끝나면 visit처리 초기화 
			}
		}
	}
	
	public static void main(String[] args) {
		
		visit = new int[6];
		result = new int[3];			//뽑을 갯수만큼 할당
		
		permutation(0);
	}
}

 

 

---

 

 

 

 

 

 

조합: 앞만 봐!

 

 

 

 조합이란?
 순서 상관없이 원소가 같으면 같은 결과로 취급한다. 
 
 예를들어) 동전 3개를 써서 600원을 만들어라 라고 한다면 
 그 조합으로 인한 결과값만 중요할뿐, 몇번째에 어느동전이 뽑혔는지는 중요하지 않다. 
 따라서 (500원, 50원, 50원)과 (50원, 50원, 500원)은 같은 결과로 취급한다. 
 
 그러므로 조합은 순열보다 경우의 수가 현저히 적다. 
 
 
 어떻게 구현할것인가?
 
 조합은 보통 "앞만봐" 라고 표현한다. 
 앞에서부터 for문을 통해 완전탐색을 해왔다면 현재 index보다 전에 있는 index를 돌아볼 필요가 없다. 
 
 why? 현재 index보다 전에 있는 index는 이전에 탐색을 했을것이기 떄문이다. 
 또 순서가 의미가 없으므로 (1,3,5)와 (3,1,5)는 같은 결과로 취급하기 때문에
 나보다 적은 index는 바라볼 필요가 없다. 

 

 

import java.util.*;

public class 조합_연습 {

	static int[] result;
	static int[] visit;
	static int[] dice = {1, 2, 3, 4, 5, 6};
	
	static void combination(int cnt, int idx) {				// cnt = 결과배열의 index, idx = 현재 내가 선택한 index
		
		if(cnt==3) {										// 결과배열의 index가 3이면 원소가 3개 찾다는 거니까 출력해라
			System.out.println(Arrays.toString(result));
			return;
		}
		
		for(int i=idx; i<=5; i++) {							// for문에서 index의 선택범위는 항상 앞만 본다 
			result[cnt] = dice[i];
			combination(cnt+1, i+1);						// 다음에 앞만봐야하니까 내가 선택한 index에서 1을 추가해서 파라미터로 보내준다.
		}
	}
	
	public static void main(String[] args) {
		
		visit = new int[6];
		result = new int[3];			//뽑을 갯수만큼 할당
		
		combination(0, 0);			//처음에는 index 0부터 뽑을수있고 결과배열index도 0이므로 (0,0) 으로 전달
	}
}

 

 

 

---

 

 

 

 

 

 

부분집합: 개수 제한이 없는 조합!

 

 

 부분집합이란?
 부분집합이란 갯수의 제한이 없는 조합과 같다. 
 조합을 설명할때 3개 합이 ~ 이런조건이 있었으나 이제는 개수의 조건이 사라진것이다. 
 
 즉, 동전들로 어떻게든 합이 500원인 경우를 만들어봐 라고 했을때 
 
  (500), (100, 100, 100, 100, 100) ... 등 여러가지 경우가 나타날수 있다. 
 
  따라서 부분집합의 핵심은 개수의 제한이 없는것!!
 
  어떻게 구현 ??
 
  순열과 조합을 구현할때는 result배열을 이용하였지만 이제는 그럴 필요가 없다. 
  개수 제한이 없기 때문이다. 따라서 메인에서 초기 index를 for문을 통해 
  모두 파라미터로 넘겨주는것이 편하다.

 

 

 

import java.util.*;

public class 부분집합_연습 {
	
	static int[] result;
	static int[] visit;
	static int[] dice = {1, 2, 3, 4, 5, 6};
	
	static void powerset(int cnt, int idx) {
		
		System.out.println(Arrays.toString(Arrays.copyOf(result, cnt)));		//개수 제한이 없으므로 모든 경우를 다 출력! 
																				//result배열의 길이만큼 끊어서 출력
		
		for(int i=idx+1; i<6; i++) {			//이전에 선택했던 index에서 +1 한 곳부터 탐색
			result[cnt] = dice[i];			
			powerset(cnt+1, i);
		}
	}
	
	public static void main(String[] args) {
		
		visit = new int[6];
		result = new int[6];	
		
		for(int i=0; i<6; i++) {				// 시작 index를 main함수에서 모두 다르게하여 전달
			result[0] = dice[i];
			powerset(1, i);
		}
	}
}