순열 (Permutation)

SW 역량테스트문제를 풀면서, 완전 탐색 (브루트포스) 문제를 해결할 때 필수적인 개념인 순열에 대해서 정리하려고 합니다. 브루트포스 문제를 만나면 단순 반복문을 통해 탐색하는 문제가 아닌, 재귀와 백트래킹을 통한 순열 또는 조합이 엮인 문제가 많은 것 같습니다. 그래서 순열과 조합에 대한 부분은 반드시 완벽하게 이해하고 문제를 풀어야 합니다. 그림만 통해서 저는 이해하기 어려웠기 때문에 문제와 그림을 통해서 정리해보겠습니다.

순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시하기도 합니다.

[네이버 지식백과] 순열 [Permutation, 順列] (두산백과)

가장 기본 적인 순열 문제를 통해서 코드를 이해 해보겠습니다.

---

https://www.acmicpc.net/problem/10974

---

import java.util.Scanner;

// 10974 모든 순열
public class Main {
	static int N;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		int[] arr = new int[N];
		int num = 1;
		for(int i=0; i<N; i++) {
			arr[i] = num++;
		}
		perm(arr, 0);
	}
	
	public static void perm(int [] arr, int depth) {
		if(depth == N) {
			for(int i=0; i<N; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
		for(int i=depth; i<N; i++) {
			rightRotate(arr, i, depth);
			perm(arr, depth+1);
			leftRotate(arr, i, depth);
		}
	}
	
	public static void rightRotate(int[] arr, int e, int s) {
		int temp = arr[e];
		for(int i=e; i>s; i--) {
			arr[i] = arr[i-1];
		}
		arr[s] = temp;
	}
	public static void leftRotate(int[] arr, int s, int e) {
		int temp = arr[e];
		for(int i=e; i<s; i++) {
			arr[i] = arr[i+1];
		}
		arr[s] = temp;
	}
}

---

문제를 이해해보면 1부터 N 까지 이루어진 순열을 사전순으로 출력하는 문제 입니다. 하지만 depth 와 i의 swap 을 통해 출력하면 오름차순으로 출력되지 않기 때문에 rightRotate와 leftRotate 를 사용했습니다. 순서를 고려하지 않고 순열을 구하려면 두 함수가 들어가는 자리에 i번째 와 depth번째를 교환해주는 swap(arr, i, depth) 두개를 넣어주면 됩니다. 

저는 순열 구하는 것을 처음 공부했기 때문에, 공부하지 않았으면 아마 못풀었을 것 같습니다. 제가 처음 보고 느끼기에 재귀가 너무 복잡해서 잘 이해가 되지 않았습니다.

public static void perm(int [] arr, int depth) {
		if(depth == N) {
			for(int i=0; i<N; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
		for(int i=depth; i<N; i++) {
			rightRotate(arr, i, depth);
			perm(arr, depth+1);
			leftRotate(arr, i, depth);
		}
	}

위의 순열 코드와 그림을 통해서 설명하겠습니다. 배열의 0번째부터 3번째 인덱스까지 ABCD가 들어있다고 가정합니다. ABCD의 순열을 구하는 코드라고 생각해보겠습니다.

1. perm(arr, 0)을 시행하면 반복문이 0부터 3까지 돌면서 rightRotate(arr, 0, 0)을 하는데 0과 0의 자리는 바뀌지 않습니다. 그리고 perm(arr, 1)을 시행합니다.

2. perm(arr, 1) 은 1부터 3까지 반복문을 수행합니다. 그리고 rightRotate(arr, 1, 1)을 시행하는데 1번째와 1번째를 바꿔도 똑같기 때문에 변화하는 것은 없습니다. 다음에 perm(arr, 2) 를 시행합니다.

3. perm(arr, 2) 는 2부터 3까지 반복문을 수행합니다. rightRotate(arr, 2, 2)는 변화하는 것이 없고, perm(arr, 3)을 시행합니다.

4. perm(arr, 3) 은 3부터 3까지 반복문을 수행하는데, rightRotate(arr, 3, 3) 역시 변화 안하고 perm(arr, 4)를 시행합니다.

5. perm(arr, 4)는 depth 가 4이기 때문에 드디어 재귀함수의 기저조건에 걸리게 됩니다. 그래서 ABCD를 출력합니다.

6. ABCD를 출력한 다음이 중요한데 perm(arr, 4)가 끝났기 때문에 나와서 perm(arr, 3)의 남은 수행을 마저합니다. 그러면 leftRotate(arr, 3, 3)을 시행하는데 변화가 없습니다. 이제 perm(arr, 3)이 끝났습니다.

7.  perm(arr, 3)이 끝났기 때문에 perm(arr, 2)를 마저 수행해야 합니다. perm(arr, 2) 에서 perm(arr, 3)이 끝났기 때문에 다음 줄인 leftRotate(arr, 2, 2) 를 하는데 변화가 없습니다. 이제 드디어 i를 1증가시켜 rightRotate(arr, 2, 3)을 해서 2번째 index부터 3번째 index까지 rightRotate를 시켜 ABDC가 되었습니다. 그리고나서 perm(arr, 3)을 부릅니다.

8. perm(arr, 3)에서 rightRotate(arr, 3, 3)을하고 perm(arr, 4) 를 하면 ABDC가 출력됩니다.

9. perm(arr, 4) 가 끝나고 leftRotate(arr, 3, 3)을 하고 perm(arr, 3)이 끝나게 되면 다시 perm(arr, 2)로 돌아와 leftRotate(arr, 2, 3)을 해서 ABCD로 복구 시킵니다.

함수가 실행되는 순서만 적어보자면,

perm(arr, 0) --> rightRotate(arr, 0, 0) --> perm(arr, 1) --> rightRotate(arr, 1, 1) --> perm(arr, 2) -->

righRotate(arr, 2, 2) --> perm(arr, 3) --> rightRotate(arr, 3, 3) --> perm(arr, 4) --> print(1,2,3,4), return ! -->

leftRotate(arr, 3, 3) --> leftRotate(arr, 2, 2) --> perm(arr, 2) 실행 도중 i가 1증가 --> rightRotate(arr, 3, 2) -->

perm(arr, 3) --> rightRotate(arr, 3, 3) --> perm(arr, 4) --> print(1,2,4,3), return! --> . . .

이러한 과정이 반복되면서 순열이 구해지는 것입니다. 밑의 사진과 함께 위의 코드를 보면 좀더 이해가 쉽게 될 것입니다. 순열의 코드를 한줄씩 보면서 재귀가 언제 어떻게 나오고 다시 들어가는지 이해해야 합니다.

http://www.algocoding.net/design/search/permutation.html