순조부 2 - 순열(Permutation)
순열은 서로 다른 n개 중 r개를 택하여 한 줄로 나열한 것이다.
순열을 코드로 표현하는 방법은 재귀, 비트마스킹, 넥퍼(Next Permutation) 3가지 방법으로 나타낼 수 있다.
재귀
- N개의 숫자를 배열에 저장
- 배열에서 각 위치의 숫자를 뽑았을 때, 뽑지 않았을 때의 순열을 생성
- 순열의 크기가 R개가 됐을 때 순열 완성
public class Permutation {
// N개 중 R개의 순열 뽑기
static int N, R;
// arr - 입력받을 배열
// temp - 순열을 저장할 배열
static int[] arr, temp;
// 순열을 만들기 위해 arr의 요소가 선택됐는지 안됐는지 판단하는 배열
static boolean[] isSelected;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
arr = new int[N];
temp = new int[R];
isSelected = new boolean[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
perm(0);
}
// 재귀로 순열 만들기
// arr의 요소를 하나씩 탐색하면서 temp에 순서대로 넣어본다.
// 이미 선택된 요소는 선택하지 않는다.
private static void perm(int cnt) {
// 기저조건
// 순열의 크기가 찾고자하는 R의 크기가 되었을 때 재귀를 종료
if(cnt == R) {
System.out.println(Arrays.toString(temp));
return;
}
for (int i = 0; i < N; i++) {
// 이미 선택된 숫자일 경우 건너뛴다
if(isSelected[i])
continue;
// cnt의 위치에 순서대로 arr의 값을 넣는다.
temp[cnt] = arr[i];
// 선택된 숫자를 표시하고 재귀를 태운다.
isSelected[i] = true;
perm(cnt+1);
// 해당 숫자의 사용을 해제한다.
isSelected[i] = false;
}
}
}
입력
5 3
1 2 3 4 5
출력
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
...
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]
비트마스킹
비트마스킹도 기본적으론 재귀를 사용하지만 위에서 사용한 isSelected 대신 비트연산(Shift연산)을 활용하여 순열에 사용한 요소의 위치를 파악한다.
비트마스킹을 사용하면 isSelected와 같은 체크용 배열을 따로 관리하지 않아 공간복잡도면에서 좀 더 좋으며, 이진수를 이용해 연산을 하므로 연산 속도가 더 빠르다.
위 그림과 같이 1을 비트연산으로 이동하며 선택한 위치를 표시할 수 있다.
그럼 이걸 어떻게 사용하느냐?
and연산(&) 과 or연산(|) 을 사용하여 지금까지 순열에 사용된 요소들의 위치를 찾을 수 있다.
지금까지 사용한 값과 현재 탐색하는 요소의 index값을 and연산을 하여 0이 아니면
이전에 이미 선택된 요소인 것이다.
if((flag & 1<<i) != 0)
continue;
여기서 중요한건 연산 결과가 0이 아니다(≠ 0) 이다. 비트마스킹을 처음 배우면 ((flag & 1<<i) == 1) 이렇게 사용하는 경우가 있는데 위 그림을 보고 1이라고 생각하면 안된다. 이진수인걸 주의하면 위 그림의 결과는 4라는걸 알 수 있다.
이미 선택된 요소가 아닐 경우 새로 선택된 요소의 위치를 표시할 땐 or연산을 하여 표시한 후 그 값을 다음 재귀에 넘겨준다.
bitPerm(cnt+1, flag | 1<<i);
isSelected를 사용하던 코드를 위 코드로 바꿔주면 BitMasking을 사용한 순열이다.
입력 및 결과는 재귀때랑 같다.
public class Permutaion_Bit {
public static void main(String[] args) throws IOException {
// 입력은 위 재귀코드와 똑같다.
bitPerm(0, 0);
}
// 비트마스킹 순열 만들기
// arr의 요소를 하나씩 탐색하면서 temp에 순서대로 넣어본다.
// 이미 선택된 요소는 선택하지 않는다.
private static void bitPerm(int cnt, int flag) {
// 기저조건
// 순열의 크기가 찾고자하는 R의 크기가 되었을 때 재귀를 종료
if(cnt == R) {
System.out.println(Arrays.toString(temp));
return;
}
for (int i = 0; i < N; i++) {
// 이미 선택된 숫자일 경우 건너뛴다
if((flag & 1<<i) != 0)
continue;
// cnt의 위치에 순서대로 arr의 값을 넣는다.
temp[cnt] = arr[i];
// 선택된 숫자를 표시하고 재귀를 태운다.
bitPerm(cnt+1, flag | 1<<i);
}
}
}
넥퍼(Next Permutation)
넥퍼는 정렬된 수를 사전 순으로 다음 순열을 생성하는 방식이다.
사전 순으로 생성하기 때문에 처음에 배열을 정렬하고 가장 작은 순열을 한 번 처리해야한다.
넥퍼의 알고리즘은 우선 배열을 오름차순으로 정렬한다. 그 다음 사전 순으로 다음으로 큰 순열을 생성하여 가장 큰 내림차순 순열이 될 때까지 반복한다.
- 뒤쪽부터 탐색하며 증가하는 구간 중 가장 큰 값(i)의 앞자리(i-1)을 찾는다.
- 뒤쪽부터 탐색하며 교환위치(i-1)보다 큰 값 위치(j)를 찾는다.
- 두 위치(i-1, j)를 교환한다.
- i부터 맨 뒤까지 오름차순으로 정렬한다.
아래 그림은 [1, 2, 3, 4] 를 예로들어 넥퍼를 진행하는 과정이다.
.
.
.
위와 같은 과정을 거쳐 가장 작은 순열부터 가장 큰 순열의 순서로 생성된다.
이제 과정을 알았으니 코드를 살펴보자, 코드는 생각보다 간단하므로 주석으로 설명을 대체한다.
public class NPTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] input = new int[N];
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
// 오름차순 정렬
Arrays.sort(input);
// 정렬된 순열을 먼저 출력 후 np를 태우기 위해 do-while 사용
do {
System.out.println(Arrays.toString(input));
} while (np(input));
}
public static boolean np(int[] numbers) { // 다음 순열 존재하면 true, 아니면 false
int N = numbers.length;
// 1. 뒤쪽부터 탐색하며 증가하는 구간 중 가장 큰 값(i)의 앞자리(i-1)을 찾는다.
int i = N - 1;
while (i > 0 && numbers[i - 1] >= numbers[i])
--i;
// 다음 순열을 만들수 없는 이미 가장 큰 순열의 상태
if (i == 0)
return false;
// 2. 뒤쪽부터 탐색하며 교환위치(i-1)보다 큰 값 위치(j)를 찾는다.
int j = N - 1;
while (numbers[i - 1] >= numbers[j])
--j;
// 3. 두 위치(i-1, j)를 교환한다.
swap(numbers, i - 1, j);
// 4. i부터 맨 뒤까지 오름차순으로 정렬한다.
Arrays.sort(numbers, i, N);
return true;
}
public static void swap(int[] numbers, int i, int j) {
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}