[알고리즘 이론] 완전 탐색 - 순열

완전 탐색 알고리즘

1. 순열
2. 조합
3. 부분집합

📌 Permutation

• 서로 다른 것n개의 원소 중 r개를 순서 있게 골라 나열 한 것
  
  

시간복잡도

순열 공식 : $_nP_r = \frac {n!} {(n - r)!}$
중복 순열 공식 : $_n\Pi_r = n ^ {r}$

순열의 시간복잡도 n값에 대해 모든 경우의 수를 구했을 때, $_nP_n = n!$
즉, $O(n!)$의 시간 복잡도를 가짐

😱 $N \leq 10$ 인 경우만 완탐을 사용하자

1초에 1억번 연산하기 때문에 테케가 1개가 아니라면 10 또는 최대 11이하에서만 완전탐색을 하자

10! = 360만
11! = 4000만
12! = 47900만

---

반복문을 이용한 순열

• 뽑는 개수가 고정되어 있을 때 사용 (뽑는 개수 = for문의 개수)

 		// nP2 중복을 허용한 순열
        int[] arr = new int[] {1,2,3,4,5};
		System.out.println("nP2 중복을 허용한 순열");
		
        for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr.length;j++) {
				System.out.println("{ "+arr[i]+" "+arr[j]+" }");
			}
			System.out.println();
		}

• 출력
  nP2 중복을 허용한 순열
  { 1 1 } { 1 2 } { 1 3 } { 1 4 } { 1 5 }
  { 2 1 } { 2 2 } { 2 3 } { 2 4 } { 2 5 }
  { 3 1 } { 3 2 } { 3 3 } { 3 4 } { 3 5 }
  { 4 1 } { 4 2 } { 4 3 } { 4 4 } { 4 5 }
  { 5 1 } { 5 2 } { 5 3 } { 5 4 } { 5 5 }

		// nP2 중복을 허용하지 않은 순열
        int[] arr = new int[] {1,2,3,4,5};
		System.out.println("nP2 중복을 허용하지 않은 순열");
        
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr.length;j++) {
				if(i!=j) {
					System.out.println("{ "+arr[i]+" "+arr[j]+" }");
				}
			}
			System.out.println();
		}

• 출력
  nP2 중복을 허용하지 않은 순열
  { 1 2 } { 1 3 } { 1 4 } { 1 5 }
  { 2 1 } { 2 3 } { 2 4 } { 2 5 }
  { 3 1 } { 3 2 } { 3 4 } { 3 5 }
  { 4 1 } { 4 2 } { 4 3 } { 4 5 }
  { 5 1 } { 5 2 } { 5 3 } { 5 4 }

재귀를 이용한 순열

• 중복 순열이 아닐때 중복 체크 배열을 사용하여 중복을 제거
  - 중복 체크 시간복잡도 : $O(1)$ (인덱스로 바로 접근하기 때문)

public class Permutation_recursive {
	static int[] arr = new int[] {1,2,3,4,5};
	static int r;
	static int[] permutationResult;   
	static boolean visited[];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();                   // 뽑아야 하는 수 
		permutationResult = new int[r];     // 순열을 저장하는 배열
		
		// nΠr 중복을 허용하는 순열
		permutationDuplication(0);
		
		System.out.println();
		
		// nPr 중복을 허용하지 않는 순열
		visited = new boolean[arr.length];          // 중복 제거를 위한 방문 체크 배열
		permutation(0);
		
	}
	private static void permutationDuplication(int depth) {
		if(depth == r) {                            // r개를 다 뽑으면 return
			System.out.println(Arrays.toString(permutationResult));
			return;
		}
		for(int i=0;i<arr.length;i++) {
			permutationResult[depth] = arr[i];	    // 한 개 뽑기
			permutationDuplication(depth+1);        // 다음 뽑기는 다음 재귀에 넘기기
		}
	}
	
	private static void permutation(int depth) {
		if(depth == r) {                             // r개를 다 뽑으면 return
			System.out.println(Arrays.toString(permutationResult));
			return;
		}
		for(int i=0;i<arr.length;i++) {
			if(!visited[i]) {
				permutationResult[depth] = arr[i];	 // 한 개 뽑기
				visited[i] = true;		  // arr[i]를 뽑았음으로 방문체크
				permutation(depth+1);     // 다음 뽑기는 다음 재귀에 넘기기
				visited[i] = false;       // 재귀 복귀후 다음 것을 뽑아야 함으로 방문체크를 해제
			}
		}
	}

}

• 출력
  2
  중복을 허용하는 순열
  [1, 1][1, 2]
  [1, 3][1, 4]
  [1, 5][2, 1]
  [2, 2][2, 3]
  [2, 4][2, 5]
  [3, 1][3, 2]
  [3, 3][3, 4]
  [3, 5][4, 1]
  [4, 2][4, 3]
  [4, 4][4, 5]
  [5, 1][5, 2]
  [5, 3][5, 4]
  [5, 5]
  
  
  중복을 허용하지 않는 순열
  [1, 2][1, 3]
  [1, 4][1, 5]
  [2, 1][2, 3]
  [2, 4][2, 5]
  [3, 1][3, 2]
  [3, 4][3, 5]
  [4, 1][4, 2]
  [4, 3][4, 5]
  [5, 1][5, 2]
  [5, 3][5, 4]

BitMask를 이용한 순열

• 중복을 제거한 순열을 구할 때 중복 체크 배열을 bit flag로 대체

public class Permutation_bitmask {

	static int[] arr = new int[] {1,2,3,4,5};
	static int[] permutationResult;
	static int N = arr.length;
	static int r;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		permutationResult = new int[r];
		premutationBitFlag(0, 0);   // 뽑은 횟수, flag(중복 순열 제거하는 bit flag)
	}

	private static void premutationBitFlag(int depth, int flag) {
		if(depth == r) {                             // r개를 다 뽑으면 return
			System.out.println(Arrays.toString(permutationResult));
			return;
		}
		for(int i=0;i<N;i++) {
			if( (flag & 1<<i) == 0) {             // 방문 확인
				permutationResult[depth] = arr[i];	 // 한 개 뽑기                    
				premutationBitFlag(depth+1, flag | 1<<i);     // 다음 뽑기는 다음 재귀에 넘기기  +  방문 set
			}
		}
	}

}

Next Permutation을 이용한 순열

Next Permutation 정리