[알고리즘] 순열(Permutation)

참고: https://gorakgarak.tistory.com/522

순열(Permutation) 알고리즘

 

프로그래머스의 코딩 테스트 문제 중에서 완적 탐색 기법 lever2 단계인 '소수 찾기'를 풀다가 '순열'의 개념이 필요하게 되었다.
직접 구현해보려고 했으나, 쉽지않아서 구글링을 통해서 학습하였다. (알고리즘이 직관적으로 이해하기가 쉽지 않아 꽤 오랜 시간 손 코딩을 하면서 따라가며 이해하였다) 

참고: https://jar100.tistory.com/16

프로그래머스 알고리즘 : 소수 찾기 (java)

 

일반적으로 순열을 만들 때 ex. 1,2,3,4 

• 1-2-3-4
• 1-2-4-3
• 1-3-2-4
• 1-3-4-2
• 1-4-2-3
• 1-4-3-2
• 2-1-3-4
• .....

이렇게 숫자를 뒤에서부터 섞으면(= 순서를 변경), 순열의 모든 경우를 구할수 있다. 그렇다면 이를 알고리즘으로 어떻게 구현할 것인가?

위의 그림을 보자, 위 그림은 ABC의 알파벳을 재귀적으로 푸는 방법이다. ABC 중 첫번째 알파벳을 뭘로 할 것인가. 종류는 세 가지밖에 없다. 처음을 배열은 ABC 순서로 정해져 있다.

• A
• B
• C

위와같은 경우에서 첫 번째가 A인 경우는 첫 번째[0] 인자인 A를 첫 번째[0] 인자 A와 바꾼 것이나 다름이 없다. (실질적으로는 바뀌는 건 없다)

첫 번째 인자가 B로 설정되어있는 경우는 첫 번째[0] 인자인 A를 두 번째[1] 인자 B와 바꾼 것이다.

세 번째 인자가 C로 설정되어있는 경우는 첫 번째[0] 인자인 A를 세 번째[2] 인자 C와 바꾼 것이다.

첫 번째[0] 인자는 이렇게 바뀌고 있다.

• [0] <-> [0]

• [0] <-> [1]
• [0] <-> [2]

이제 첫번째 인자가 고정되었으니, 두 번째 인자와 세 번째 인자에 대해 고민을 할 필요가 있다. 위와 정확히 마찬가지로 같다.

(첫 번째[0] 인자가 [0]으로 고정된 경우)

• [0][1] <-> [0][1]   즉, 두 번째 인자[1]인 B와 두번째 인자[1]인 B를 바꾼다. (실질적으로 바뀌는건 없다) ABC
• [0][1] <-> [0][2]  두번째 인자[1]인 B와 두번째 인자[2]인 C를 바꾼다. ACB

이제 마지막[2] 인자를 살펴본다.

• [0][1] <-> [0][1]의 경우에 --> [0][1][2] <-> [0][1][2]  (바뀌는 건 없다) ABC
• [0][1] <-> [0][2]의 경우에 --> [0][1][2] <-> [0][2][1] (바뀌는 건 없다)  ACB

이제 A에 대한 경우를 모두 살펴보았고 첫 번째[0] 인자가 [0] <-> [1] , [0] <-> [2]인 경우도 이런 방향으로 알고리즘을 재귀적으로
짠다면, 그림과 같이 ABC, ACB, BAC, BCA, CBA, CAB 순으로 튀어나오게 될 것이다. (순서대로 나오지 않는다!) 

nPk(고등학교 수학 시간에 nPr을 많이 썼던 거 같지만..)의 순열을 구해야 하는 문제, 즉 n개중 k개로 이루어진 순열을 구하려고 한다. 샘플에서는 1,23,4 네 개로 이루어진 배열을 가지고 4개로 이루어진 순열을 구해보고자 한다.

다음과 같은 시그니처를 사용한다.

perm ( int[] arr , int depth , int n , int k )

배열 arr은 계속해서 데이터를 들고 다니면서 교환 작업을 하고 있는지에 대한 변수이다. 맨 처음 깊이라면 depth = 0의 위치에서 작업하고 있을 것이며, 이는 첫 번째[0]가 첫번째[0] 또는 두 번째[1] 또는 세 번째[2] 또는 네 번째[3] 인자를 교환하는 중이다.
depth는 0에 대한 것을 다 끝마치고 1로 넘어가는 것이 아니라 0,1,2,3,2,3,1,2,3과 같은 형태로 내부적으로 변하고 있다. (물론 프로그램의 시작점에서는 0으로 넣어주어야 한다)

n은 총 배열 안에 들어있는 숫자를 뜻하며 고정값이다. (예제는 1,2,3,4 모두를 사용해 순열을 만드므로 4로 고정된다

k는 몇 개를 뽑아내서 순열을 만들 것인지를 뜻하며 고정값이다. 샘플을 1,2,3,4 모두를 사용해 순열을 만드므로 4로 고정된다.

public void perm(char[] arr, int depth, int n , int k ) {
        if (depth == k) {
            // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
            print(arr);
            return;
        } else {
            for (int i = depth; i < n; i++) {
                swap(arr, i, depth);
                perm(arr, depth + 1, k, sosuList);
                swap(arr, i, depth);
            }
        }
    }

 

실제적인 코드의 구현은 위와 같다. 일단 depth를 검사해 k와 같으면 더 이상 순열을 만들지 않는다. 우리가 원하는 것은 k개의 숫자가 있는 순열이기 때문이다. 4에 도달하면 출력해야 하는 숫자 네 개가 모두 세팅되었다는 뜻이므로 출력해주면 된다

depth에 따라서 for문의 시작점이 다르다. depth가 0이라면 1 XXX, 2 XXX, 3 XXX, 4 XXX를 뽑아줘야 하므로 총 네 번의 루프가 돌아야 하며, 이는 i < n이라는 조건에서 n은 4로 고정이고 i는 depth에 따라 0부터 시작하기 때문에 0,1,2,3 네 번이 도는 것이다.

다만,

(depth 0) 1 XXX이 만들어지면, (2 XXX를 만드는 것이 아니라)
(depth 1) 2XXX를 만드는 것이 아니라 12XX, 13XX, 14XX를 만들고
(depth 2) 바로 다음으로 123X
(depth 3) 마지막으로 1234가 채워져 지며
(depth 4) 출력한다

perm (arr, depth + 1 , n , k ) 함수에  ( {1,2,3,4} , 4 , 4 , 4 ) 인자가 채워져서 호출된다. 그렇지만, depth는 이제 k와 같으므로 바로 return을 통해, perm문을 끝내고 다음 문장인 swap()을 실행하게 된다. 
마지막으로 의문인 점은 왜 swap 함수를 두 번 쓰는 것인가?인데, 깔끔해 보이지 않음에도, swap() 함수는 꼭 필요하다. 재귀 함수를 쓰면서 perm() 함수에 자꾸 걸려서 뒤쪽 swap() 함수가 드디어 호출된다. 두 번째 swap()은 전 단계의 분기점에서의 배열의 순서를 기억하고 이를 초기화하는 작업에 지나지 않는다. 트리구조에서 depth는 0,1,2,3,2,3,1,2,3.... 이런 식으로 한두 칸씩 뒤로 돌아가면서 다시 계산을 하는데 그 지점에서의 배열 안의 숫자 순서를 기억하고 있어야 한다. swap() 없이 바로 사용하고자 한다면, 분기로 돌아가서 다시 교환을 하는 게 아니라, 이미 다른 분기에서 망가뜨려버린 배열의 순서를 그대로 이용하게 되어, 황당한 순열들이 튀어나오게 된다. 

perm 메서드를 사용하기 위해서는 준비작업적 함수가 두 가지 필요하다.

1. 배열의 특정 위치를 교환하는 함수 (필수)
2. 배열을 출력하는 함수 (선택)

배열의 특정위치를 교환하는 함수가 필요한 이유는 , C의 경우에는 포인터가 있어 주소 값을 바로 찾아서 바꿔버릴 수 있어 조금 더 편리하게 값들을 바로 바꿀 수 있는 반면, 다른 언어들은 주소에 직접 접근하지 않고 참조형 변수로 접근하거나, 배열 자체를 전달해 이의 값을 바꾸도록 하기 때문이다. 그렇다고 포인터를 남발하면 남발할수록 프로그램은 파악하기도 어렵고 버그가 자주 나니 지양하는 편이 낫다.

배열의 특정 위치를 교환하는 함수는 swap 메서드이고 다음과 같다. 이렇게 교환을 하면 굳이 포인터를 넘기지 않아도 알아서 배열 안에 있는 값들이 교환된다. (다만 리턴 값이 없기 때문에 이러한 프로그램 방식은 좋지 않다)

public void swap(int[] arr, int i, int j) { 
		int temp = arr[i]; 
  	  	arr[i] = arr[j]; 
  	  	arr[j] = temp; 
    }

 

배열을 출력하는 함수는 그냥 배열을 출력하는 함수이므로 중요하지 않기에 생략하겠다.

최종적인 자바 코드는 아래와 같다.

package algo; public class Permutation { 
	public static void main(String[] args) { 
    	int[] arr = { 1, 2, 3, 4 }; 
        
        perm(arr, 0, 4, 4); 
    } 
        
    public static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
        	print(arr,k); return; 
        } 
        for (int i = depth; i < n; i++) {
        	swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth); 
        } 
    } // 자바에서는 포인터가 없기 때문에 아래와 같이, 인덱스 i와 j를 통해 바꿔줌. 
            
    public static void swap(int[] arr, int i, int j) {
            
    	int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
                
    } 
            
    public static void print(int[] arr, int k) { 
    
    	for (int i = 0; i < k; i++) { 
        	
            if (i == k - 1) 
            	System.out.println(arr[i]); 
            else 
            	System.out.print(arr[i] + ","); 
         } 
    } 
}

이러한 순열( 조합 또한)은 코딩 테스트 문제를 풀면서 요구하는 경우가 더러 있었고, 정해진 시간에서 갑자기 떠올리기가 쉽지 않았다. 
지금까지 코딩 테스트를 망했었던 이유들을 분석하면서 이런 알고리즘들을 차례차례 정리해뒀다가 그 원리를 잘 떠올려서 적시적소에 써먹도록 해야겠다.