[자료구조] 순열

순열 (Permutation) 이란?

• 순서를 정해서 나열

• 서로 다른 n개 중에 r개를 선택하는 경우의 수

• 순서 존재, 중복 허용 X

• n​Pr​

순열에서는 { 1, 2, 3 }, { 1, 3, 2 }, { 2, 1, 3 } 등 모두 다른 경우의 수로 취급한다. 순서가 있는 열이기 때문이다.

아래 문제를 해결하는 방법은 2가지가 있다.

< 해결할 문제 >

 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오

단순히 머리 속에서 생각하면 이해가 쉽지 않아 그림을 그려가며 직접 로직이 어떻게 진행되는지 따져보며 이해하는 것을 추천한다.

1. SWAP을 이용한 구현

아래 사진은 숫자 3개일 때, SWAP을 이용한 구현 방식을 나타내고 있다.

swap 함수를 만들어 배열들의 값을 직접 바꾸는 방식이다.

depth를 기준 인덱스로 하여 depth보다 인덱스가 작은 값들은 그대로 고정하고

depth보다 인덱스가 큰 값들만 가지고 다시 swap을 진행한다.

// 순열 - 방법 1
// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하기

public class Permutation01 {
    void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return; // 탈출 조건
        }

        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }

    void swap(int[] arr, int depth, int idx) {
        int tmp = arr[depth];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
    }

    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};

        Permutation01 p = new Permutation01();
        p.permutation(arr, 0, 4, 3);
    }
}

해당 방법을 사용하면 왼쪽 결과창처럼 순열의 순서가 보장이 되지 않는 것을 확인할 수 있다. swap 순서에 따라 {1, 4, 2} , {1, 4, 3} 순으로 나와야하는데 순서는 다르게 출력이 된다.

2. Visited를 이용한 구현 (DFS)

Visited 배열을 사용하면 1번과 다르게 순서를 보장하여 출력할 수 있다.

DFS를 돌면서 모든 인덱스를 방문하여 out 변수에 값을 넣는다.

depth == r 일때, 배열을 출력하고 해당 조건문을 탈출하는데

탈출하고 돌아왔을 때, 각 변수들의 값을 주의해주어야한다.

visited 배열을 통해 이미 들어간 값은 해당 값을 true로 바꾸어 중복하여 넣지 않도록 한다.

depth 값은 out에 들어간 숫자의 길이를 의미한다.

depth 값이 r만큼 되면 out에 들어가 있는 값을 출력한다.

// 순열 - 방법2 (visited 사용)
// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오

import java.util.Arrays;

public class Permutation02 {
    void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
        if (depth == r) {
            System.out.println(Arrays.toString(out));
            return; // 탈출 조건
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, depth + 1, n, r, visited, out);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[4];
        int[] out = new int[3];

        Permutation02 p = new Permutation02();
        p.permutation(arr, 0, 4, 3, visited, out);
    }
}

순열은 다양한 문제에서 활용이 되기 때문에 제대로 이해하고 넘어가는 것이 중요하다.

문제를 해결할 때, swap 방식보다는 visited 방식이 좀 더 자주 쓰인다.

길어지는 코드와 다양한 조건에 당황하지 않고, 유연하게 코드를 작성할 수 있도록 연습해야겠다.