Java로 순열(Permutation) 구현하기

---

보통 알고리즘은 c++로 많이 푼다. 그러나 못지않게 자바로도 많이 푸는데 각자의 장단점이 있다. 그중 c++에는 있고 자바에는 없는것이 바로 next_permutation이다. c++이 라이브러리로 순열을 제공 해준다고해도 순열의 원리가 필요한 특정문제에서는 제한적일 수 있다. 따라서 이번에는 순열을 구현할 수 있는 3가지방법을 자바로 구현해보고자 한다.

---

순열 (Permutation)

순열은 알고리즘 문제를 해결하다보면 단골로 나오는 문제다. 간단한 문제부터 문제속의 문제, 또는 원리를 묻는 문제등의 문제가 출제되어서 알고리즘을 공부한다면 기본적으로 알고있어야 할 내용이다.

순열을 구성하는 방법으로는 아래 3가지가 존재한다.

1. iterative한 방법
2. 스왑을 통한 방법
3. 방문처리를 통한 방법

next_permutation

첫번째로 iterative한 방법으로는 c++ Algorithm 헤더에 있는 next_permutation처럼 구현하는 방법이 있다. next_permutation은 말 그대로 다음번째 순열을 구하는 라이브러리로, 모든 순열을 구하기위해서는 오름차순으로 정렬된 리스트에 대해서 해당된다.

c++에서는 다음과같이 이용된다.

do {
	for(int data : list) {
    		cout << data << " ";
    	}
        cout << '\n';
}while(next_permutation(list.begin(),list.end());

do while의 특성으로 정렬되어있는 맨처음 리스트를 출력하고 그다음 순열을 마지막 순서까지 반복하게 된다. 이 때, 이 next_permutation을 자바로 구현해보자.

1. 꼭대기를 찾는다

• 리스트의 맨 뒤에서부터 두 원소씩 비교해나가며 리스트의 가장 큰값인 꼭대기를 찾는다. 이때 만약 리스트가 5 4 3 2 1로 되어있다면 꼭대기가 0번째 인덱스가된다. 즉, 꼭대기가 0번째인덱스가 되는 순간이 순열의 마지막 순서라는것이다.

2. 다음 순열의 값 찾기

• 다음 순열의 값의 특징은 이전 순열보다 값이 크다는것을 알수있다. 마지막 인덱스에서부터 꼭대기-1(이하 i-1)번째 인덱스의 값보다 큰 값을가진 인덱스(이하 j)를 찾는다. 이때 list[i-1] < list[i] 는 자명하기때문에 j의 값을 못찾는 경우는 없다. j를 찾았다면 list[i-1]과 list[j]를 스왑한다.

3.순서 정해주기

• 다음 순열의 소스를 찾아서 스왑을 했으니, 다음 순열을 정해주기위해서 현재 i번째부터 마지막 인덱스까지 순서대로 스왑해준다.

이렇게 3가지 순서를 통해 next_permutation을 구현할 수 있다. 직접 코드를보며 이해해보자.

private static boolean nextPermutation(int[] list) {
	int i = list.length - 1;
	int j = list.length - 1;
	
	/** 1. 꼭대기 찾기 **/
	while(i > 0 && list[i-1] >= list[i]) --i;
	if(i <= 0) return false;	// 꼭대기가 0번째 인덱스라면 마지막순열
			
        /** 2. j값 찾기 **/
	while(list[i-1] > list[j]) --j;
	swap(i-1,j);
	
    	/** 3. 순서 정해주기 **/
	j = list.length - 1;
	for(; i < j; ++i, --j) {
		swap(i,j);
	}
	return true;
}

스왑을 이용한 순열

두번째로는 스왑을통해서 순열을 구하는 것이다. 특징으로는 순서가 일정하지 않는다는것인데, 가끔 이 스왑의 특성을 이용해 해결해야하는 문제들이 나온다. 이 특성을 이해해보도록 하겠다.

기본적으로 재귀호출을 이용한 방법인데, 백트래킹에 대한 이해도가 필요하다. 코드를 보며 이해해보자.

public static void nPrSwap(int d) { // d: depth	
	if(d == R) {
		System.out.println(Arrays.toString(list));
		return;
	}
	for (int i = d; i < list.length; i++) {	        	
		swap(d,i);
		nPrSwap(d+1);
		swap(d,i);
	}
}

위와 같이 재귀호출을 하기전의 상태를 재귀호출이 끝난 뒤 되돌리는 것을 백트래킹이라 한다. 재귀호출을 하나하나 따라가다보면 첫번째로 끝까지 들어가 return 되는 곳은 처음 리스트 처음 그대로의 순서가된다. 그리고 그 다음 순서는 재귀호출이 끝난뒤 원래 상태로 되돌아 간 부분에서 i값이 증가하여 다른 순열이 완성된다.

모든 순열을 구할순있지만, 같은 순서의 순열을 여러번 생성하는 바람에 단순히 순열만 필요한 순간에서는 next_permutation보다 효율이 많이 떨어진다. 평소에 많이 쓰지않는 방법이긴하나 앞서 말했다시피 리스트의 모든 순서를 구하면서 스왑의 특성을 묻는 문제에서 가끔 사용된다.

방문처리를 이용한 순열

마지막으로 방문처리르 이용한 순열은 위 두가지에 비해 가장 직관적이고, 순열을 구하는 과정에서 추가적인 조건을 잘처리할 수있는 방법이기도 하다.

예를들자면, 보통 iterative한 bottom-up 방식은 프로그래밍에 최적화되어있지만 사람의 입장에서는 받아들이는 순서가 반대다. 반면에 recursive한 top-down 방식은 사람의 이해 순서와 같은 방향으로 코딩이 되어져있기 때문에 추가적인 조건사항 등을 비교적 직관적으로 넣을 수 있다는 점이다.

public static void permutation(int idx) {
	if(idx == R) {
		return;
	}
	for(int i = 0; i < list.length; ++i) {
		if(visited[i]) continue;
			
		resulList[idx] = list[i];
		visited[i] = true;
		permutation(idx+1);
		visited[i] = false;
	}
}

스왑을 이용한 순열과 마찬가지로 방문처리에 대해서 백트래킹을 이용하고있다. 하지만 앞에것과는 다르게 순열이 저장되는 리스트가 바로바로 결정된다.

정리

순열을 구현하는 세가지 방법에대해 알아보았다. 개인적으로 3가지 방법중에 하나만 알아야한다면 방문처리를 이용한 순열을 기억하라고 말하고싶다. 처음 이 방법에 익숙해지고 원리를 이해했다면 나머지 두 방법을 받아들이는 방식을 추천한다.

모든 순열의 시간복잡도는 O(n!)를 따르고있다. 시간복잡도가 확실해서 그런지 순열문제는 크게 두가지 부류로 나눌 수있다. 단순히 순열만을 구해 문제를 풀때는 비교적 실행시간이 빠른 next_permutation을 이용한 풀이가 좋다. 반대로 순열을 구하는 도중에 가지치기가 필요하다던지 추가적인 조건이 들어간다면 방문처리를 이용한 순열을 이용해보자.