순열(permutation)

어제 알고리즘 수업시간에 순열을 만드는 법을 배웠습니다. 평소 문제를 풀다가 여러 경우의 수를 고려하기 위해 순열 또는 조합이 필요한 경우를 느껴왔기 때문에 수업이 기대되었는데요. 물론 처음부터 순열 소스코드가 바로 이해되지는 않았지만 끝나고 혼자 고민하는 시간을 통해서 어떻게 구성되는지 대략적인 구조를 파악할 수 있었습니다.

 

오늘 배운 순열 구현 방법은 swap함수와 재귀를 이용하는 방법인데요. 우선 소스코드부터 보도록 하겠습니다.

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

    void permutation(int[] arr, int d, int n, int r) {
        if (r == 0) {
            System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, d)));
            return;
        }
        for (int i = d; i < n; i++) {
            myswap(arr, d, i);
            permutation(arr, d + 1, n, r - 1);
            myswap(arr, d, i);
        }
    }

메소드별로 어떻게 구현되고 있는지 살펴볼까요?

• myswap()메서드

  • temp 지역변수를 이용하여 배열 내에서 두 원소의 위치를 바꿔주는 메서드입니다.
  • permutation()메서드에서 아주 중요한 역할을 하는데요. 이 메서드가 배열 내에서 자리를 바꿔주면서 모든 경우의 수를 만들어줍니다.

• permutation()메서드

  • 먼저 매개변수의 의미부터 알아보도록 하겠습니다.

    • int[] arr : 순열을 구성하는 각각의 숫자들의 배열을 의미합니다.
    • d : 인덱스의 깊이를 의미하고 재귀 구현시 중복되는 순열이 발생하지 않도록 기준점을 제시합니다. 메서드 내에서 점차 증가합니다. 예를들어 0이면 0부터 n까지, 1이면 1부터 n까지(인덱스 0인 부분은 변화되지 않습니다), 2이면 2부터 n까지(인덱스 0, 1인 부분은 변화되지 않습니다) swap이 발생하도록 합니다.
    • n : 몇 개의 수가 활용될지 말합니다. 예를들어 [1, 2, 3, 4, 5, 6]과 같이 6개의 숫자가 제시되었더라도 n이 4이고 d가 0이면 인덱스 0부터 3까지의 수만 순열에 활용됩니다.
    • r : 몇 개의 수가 출력될건지와 종료시점을 결정합니다. d와 연결되어 있는데요. 이는 메서드 내에서 d가 증가되면서 r이 감소되기 때문입니다. d를 보통 0으로 맞추지만 다른 수로 설정시 원하는 개수의 수로 출력안될 수 있습니다.

  • 위에서 살펴본 매개변수는 서로 유기적으로 연결되기 때문에 수를 어떻게 설정하느냐에 따라 원하는 값이 전혀 다르게 나올 수 있습니다. 순열에 초점을 맞춘다면 d = 0, n = '순열 구성할 숫자', r = '출력할 숫자 길이'로 맞춰주는 것이 좋습니다.

  • 이제 메서드 안의 코드를 살펴보면 처음 if문은 종료시점을 의미하고 여기서 출력 및 값 저장이 이루어지게 됩니다. 여기선 출력만 있는데요. Arrays.toString()은 배열 안 원소를 그대로 출력하고, Arrays.copyOfRange()는 배열을 어디부터 어디까지 자를지 결정합니다. 몇 개 출력될지 결정하는 r은 재귀를 돌면서 0이 되었기 때문에 r이 줄어든 만큼 수가 커진 d을 이용하여 출력합니다.

  • for문 내에서는 드디어 재귀가 등장하는데요. d가 0일 때 n까지 반복문을 돌립니다. 깊이에 따라 그 자리와 i번째와 자리를 바꾸고 permutation(arr, d + 1, n, r - 1);를 호출합니다. 이 재귀 호출은 깊이가 하나 증가되고 r은 하나 감소되어 이전 깊이의 인덱스는 고정시키고 이후만 바뀔 수 있도록 합니다. r이 감소되는건 종료시점을 설정하기 위함이지요.

  • 마지막에 myswap(arr, d, i);이 있는 이유는 각각의 재귀가 종료되는 시점에 호출되었던 모든 메서드에서 차례대로 다시 swap했던 부분을 되돌려 놓음으로써 원상태로 돌려놓기 위함입니다. 그래야 다음 swap이 발생할 때 기존에 섞였던 것과 독립적일 수 있기 때문입니다. 이렇게 까지 하는 이유는 기본적으로 arr을 보낼 때 각 배열의 주소값을 보내기 때문입니다. 따라서 마지막에 myswap(arr, d, i);을 안 사용하려면 permutation(arr.clone(), d + 1, n, r - 1);처럼 clone()메서드를 사용하여 새로운 배열을 재귀 메서드로 보내면 됩니다. 그 대신 재귀시 매번 새로운 배열을 생성해 메모리 낭비가 발생할 수 있겠죠.

 

이제는 실제로 호출했을 때 어떻게 호출되는지 각각의 경우를 살펴보도록 하겠습니다. permutation(arr, 0, 4, 4)가 호출되었다고 생각하겠습니다. 이 말은 [1, 2, 3, 4]의 수를 4개 출력하여 24개의 경우의 수가 발생되도록 합니다.

위 그림을 보면 최초 permutation(arr, 0, 4, 4)가 호출되고 swap(0, 0)을 한뒤 또 다시 permutation(arr, 1, 4, 3)을 호출하는 것을 볼 수 있는데요. 이 후에 swap(1, 1)이 발생한 것을 볼 수 있죠. 맨 윗부분은 이렇게 따라가면 하나도 안 바뀐것을 알 수 있습니다. 자기 자신의 인덱스와 swap()하기 때문이죠. 이렇게 하나의 경우가 끝날때마다 다시 제 자리로 다시 옮겨놓습니다.

하나의 예를 더 살펴보겠습니다. 이번엔 6번째 경우를 살펴보죠. 처음에 (0, 0) 자리 바꾸면 [1, 2, 3, 4], 다시 (1, 3) 바꾸면 [1, 4, 3, 2], (2, 3)자리 바꾸면 [1, 4, 2, 3], 마지막으로 (3, 3)자리 바꾸면 그대로니까 결국은 [1, 4, 2, 3]이 출력되는 것이죠. 물론 이 각각의 경우 자리 바꿀 때마다 다시 swap()하여 결국은 [1, 2, 3, 4]로 돌려놓습니다.

 

여기에서 조금만 더 코드를 추가하면 조합으로도 활용할 수 있는데요. permutation()의 if문에서 배열을 정렬하고(이렇게 되면 순서가 의미가 없어지겠죠). 그리고 이를 Arrays.toString()을 활용해 HashSet<String>에 넣습니다. 이렇게 되면 중복되는 배열은 Set에 넣어져 하나로 됩니다. 물론 굳이 문자열로 바꾸지 않더라도 상황에 따라 달리 사용될 수 있으나 포인트는 Set을 이용하여 중복을 없앤다는 것입니다!

 

순열에 대해 찬찬히 살펴보았습니다. 어떠신가요? 이해가 잘 되시나요? 재귀가 처음부터 바로 머리 속으로 어떻게 돌아가는지 안다는 건 정말 쉽지 않은 것 같습니다. 저도 아직까지 재귀가 돌아가는 모습이 머리 속에 쉽게 그려지진 않습니다. 하지만 더디더라도 이렇게 하나하나의 경우를 고려해가면서 이해해간다면 결국 재귀도 정복할 수 있을거라 생각합니다.