[Algorithm] 완전탐색 - 순열

순열이란 ?

순열이란 서로 다룬 n개의 원소 중 r개를 순서 있게 일렬로 나열하는 경우의 수이다.

 

예) 주사위를 2번 던졌을 때 서로 다른 숫자가 순서 있게 나오는 경우의 수

---

순열 특징 ?

순열의 특징 몇 가지를 알아보자.

 

• 순열은 선택에 중복 없이 순서 있게 결과를 가져온다.
• 매 자리마다 모든 원소를 확인한다.
• 중복 여부를 위해 방문 배열을 사용한다.
• 대표적인 구현 방법은 재귀 구현이다.
• 재귀의 깊이는 선택된 원소의 개수와 일치한다.

---

순열 구현 순서?

재귀의 Stack Overflow를 주의하면서 아래와 같이 순서를 잘 따르자.

 

1. 재귀를 호출하며, 깊이 정도를 전달한다. 이때 깊이는 선택한 원소의 개수와 일치한다.
2. 깊이 정도로 원소를 다 선택했는지 확인한다.
3. 원소를 다 선택했다면 원하는 동작 후 메서드를 종료한다.
4. 덜 선택한 경우 원소를 순회하며 이전에 선택하지 않았던 원소를 선택한다.
5. 1번 ~ 4번 과정을 반복한다.

---

순열 시간복잡도

원소를 선택할 때마다 전체 원소의 개수 중 재귀의 깊이를 뺀 나머지를 선택 가능하다.

 

순열의 시간복잡도 : O(N!)

---

순열 그림으로 살펴보기

[ 주사위의 모습 ]

[ 1, 1 ] [ 1, 2 ] [ 1, 3 ] [ 1, 4 ] [ 1, 5 ] [ 1, 6 ]

 

[ 2, 1 ] [ 2, 2 ] [ 2, 3 ] [ 2, 4 ] [ 2, 5 ] [ 2, 6 ]

. . .

[ 5, 1 ] [ 5, 2 ] [ 5, 3 ] [ 5, 4 ] [ 5, 5 ] [ 5, 6 ]

 

[ 6, 1 ] [ 6, 2 ] [ 6, 3 ] [ 6, 4 ] [ 6, 5 ] [ 6, 6 ]

---

소스코드

// 순열, 중복 순열

import java.util.Arrays;
import java.util.Scanner;

public class OverlapPermutation {
	
	// 주사위 던지는 횟수, 주사위 던지기 모드
	public static int throwCnt, throwMode;
	// 던져진 주사위 결과 배열
	public static int nums[];
	// 주사위 번호 방문 여부 체크 배열
	public static boolean v[];
	
	// 주사위 던지기 메서드 (중복 순열 버전)
	static void throwDiceOverlapPermutation(int cnt) {
		
		// 종료 조건 : 주사위를 다 던진 경우
		if(cnt==throwCnt) {
			
			// 결과 출력
			System.out.println("중복 순열 : " + Arrays.toString(nums));
			return;
		}
		
		// 한 번 던질 때 가능한 상황에 대한 시도(1,2,3,4,5,6 중 하나)
		for(int i=1; i<=6; i++) {
			
			// 주사위 결과 번호 저장
			nums[cnt] = i;
			
			// 다음 주사위 던지기
			throwDiceOverlapPermutation(cnt+1);
		}
	}
	
	// 주사위 던지기 메서드 (순열 버전)
	static void throwDicePermutation(int cnt) {
		
		// 종료 조건 : 주사위를 다 던진 경우
		if(cnt==throwCnt) {
			
			// 결과 출력
			System.out.println("순열 : " + Arrays.toString(nums));
			return;
		}
		
		
		
		// 한 번 던질 때 가능한 상황에 대한 시도(1,2,3,4,5,6 중 하나)
		for(int i=1; i<=6; i++) {
			
			// 기존 주사위의 눈과 중복되는지 체크
			if(v[i]) continue;
			
			// 주사위 결과 번호 저장
			nums[cnt] = i;
			
			// 선택된 번호 방문 체크
			v[i] = true;
			
			// 다음 주사위 던지기
			throwDicePermutation(cnt+1);
			
			// 선택된 번호를 다른 번호 선택을 위해 방문 체크 해제
			v[i] = false;
		}
	}
	
	
	public static void main(String[] args) {
		
		// 입력으로 주사위 던지는 횟수, 주사위 던지기 모드(1,2)
		Scanner sc = new Scanner(System.in);
		
		// 주사위 던지는 횟수 입력
		throwCnt = sc.nextInt();
		
		// 주사위 던지기 모드 입력
		throwMode = sc.nextInt();
		
		// 던져진 주사위 결과 배열 생성
		nums = new int[throwCnt];

		switch(throwMode) {
		
		// 중복 순열
		case 1:
			// 주사위 던지기 (중복 순열 버전)
			throwDiceOverlapPermutation(0);
			break;
			
		// 순열
		case 2:
			// 주사위 번호 방문 여부 체크 배열 생성
			v = new boolean[7];
			
			// 주사위 던지기 (순열 버전)
			throwDicePermutation(0);
			break;
		}
	}
}

---

요약

• 순열은 선택에 중복 없이 순서 있게 결과를 가져온다.
• 매 자리마다모든 원소를 확인한다.
• 방문 배열을 사용한다.
• 대표적인 구현 방법은 재귀 구현이다.
• 재귀의 깊이는 선택된 원소의 개수와 일치한다.
• 순열의 시간복잡도는 O(N!) 이다.