순열이란 ?
순열이란 서로 다룬 n개의 원소 중 r개를 순서 있게 일렬로 나열하는 경우의 수이다.
예) 주사위를 2번 던졌을 때 서로 다른 숫자가 순서 있게 나오는 경우의 수
순열 특징 ?
순열의 특징 몇 가지를 알아보자.
- 순열은 선택에 중복 없이 순서 있게 결과를 가져온다.
- 매 자리마다 모든 원소를 확인한다.
- 중복 여부를 위해 방문 배열을 사용한다.
- 대표적인 구현 방법은 재귀 구현이다.
- 재귀의 깊이는 선택된 원소의 개수와 일치한다.
순열 구현 순서?
재귀의 Stack Overflow를 주의하면서 아래와 같이 순서를 잘 따르자.
- 재귀를 호출하며, 깊이 정도를 전달한다. 이때 깊이는 선택한 원소의 개수와 일치한다.
- 깊이 정도로 원소를 다 선택했는지 확인한다.
- 원소를 다 선택했다면 원하는 동작 후 메서드를 종료한다.
- 덜 선택한 경우 원소를 순회하며 이전에 선택하지 않았던 원소를 선택한다.
- 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!) 이다.
'Computer Science > Algorithm' 카테고리의 다른 글
[Algorithm] 완전탐색 - 부분집합 (0) | 2023.08.08 |
---|---|
[Algorithm] 완전탐색 - 조합 (0) | 2023.08.08 |
[Algorithm] 시간복잡도 문제 (0) | 2023.08.08 |
[Algorithm] 알고리즘 성능 (0) | 2023.08.08 |
[Algorithm] 알고리즘 기초 (0) | 2023.08.07 |