[알고리즘] 순열(Permutation)

순열이란?

순열(Permutation)은 집합에서 일부 원소를 선택하여 순서를 고려해 나열하는 방법을 말한다. 선택된 원소들의 순서가 다르면 다른 순열이 된다. 예를 들어, 주어진 집합 {A, B, C}에서 2개를 선택하여 나열할 수 있는 순열은 AB, AC, BA, BC, CA, CB 등이 있다.

쉽게 말해 순서가 바뀌면 연산(혹은 값)이 달라지고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 2로 고정되어 있다.) 순열을 고려해 볼 수 있겠다.

 

사용 사례

• 문제 해결 : 원소들을 모든 가능한 방법을 나열해야 할 때 사용된다. 예를 들어, 순열을 이용하면 문제의 가능한 모든 경우의 수를 탐색하거나, 정렬된 순서대로 원소들을 나열하는 경우에 활용된다.
• 암호 해독 : 암호 해독 문제에서 가능한 모든 암호 조합을 찾을 때 순열을 사용할 수 있다.
• 경우의 수 계산 : 주어진 조건 하에 가능한 모든 경우의 수를 계산하거나 검증할 때 유용하다.

 

시간 복잡도

• 순열을 구하는 시간 복잡도는 O(N!)이다. 이는 주어진 N개의 원소에서 R개를 순서를 고려하여 나열하는 모든 가능한 방법을 찾기 위해 필요한 연산 횟수를 나타낸다. N이 증가함에 따라 연산량이 급격히 증가하므로, 큰 N에 대해서는 효율적인 방법이 필요하다.

 

재귀 호출을 활용한 순열 생성

재귀 호출(Recursive Call)은 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 순열 생성에서 재귀 호출은 문제를 하위 문제로 나누어 해결하는 데 매우 유용하다. 재귀를 사용하면 복잡한 순열 생성 문제를 더 간단하게 해결할 수 있다.

재귀 호출을 사용한 순열 생성의 기본 원리는 다음과 같다.

1. 기본 상태 확인 : 순열의 모든 자리를 채운 경우, 즉 기본 조건에 도달했을 때 현재 순열을 출력한다.
2. 재귀 호출 : 각 원소를 사용하여 다음 자리의 순열을 생성한다. 재귀 호출은 원소를 선택하고, 이를 다음 자리의 순열을 만들기 위해 호출된다.
3. 원상복구 : 재귀 호출이 끝난 후, 사용된 원소를 다시 사용할 수 있도록 상태를 복구한다.

 

코드를 통한 이해

import java.util.Arrays;

public class Permutation {
    static int N = 5, R = 3; // N: 전체 원소 개수, R: 선택할 원소 개수
    static String[] cards = {"A", "B", "C", "D", "E"}; // 원소
    static boolean[] used = new boolean[N]; // 각 원소의 사용 여부
    static String[] result = new String[R]; // 선택된 원소를 저장할 배열

    public static void main(String[] args) {
        perm(0); // 순열 생성 시작
    }

    static void perm(int idx) {
        if (idx == R) { // 기본 상태: 모든 자리 채운 경우
            System.out.println(Arrays.toString(result)); // 순열 출력
            return;
        }
        for (int i = 0; i < N; i++) { // 모든 원소를 시도
            if (used[i]) continue; // 이미 사용된 원소는 건너뛰기
            result[idx] = cards[i]; // 현재 자리 idx에 원소 cards[i]를 배치
            used[i] = true; // 원소 사용 중으로 표시
            perm(idx + 1); // 다음 자리로 이동하여 재귀 호출
            used[i] = false; // 원상복구: 원소 사용 표시를 해제
        }
    }
}

• 첫 번째 호출 : perm(0)이 호출되면, idx는 0으로 초기화되고, result 배열의 첫 번째 자리에 원소를 배치하기 시작한다.
• 중첩 호출 : perm(idx + 1) 이 호출되면 idx가 증가하고, 이로 인해 result 배열의 다음 자리를 채우기 위해 반복된다.
• 기본 상태 도달 : idx가 R에 도달하면, 순열이 완성되었으므로 현재 배열 result를 출력한다.
• 원상복구 : 각 재귀 호출이 끝나면, used[i]를 false로 설정하여 원소 사용 상태를 복구하고, 다른 조합을 시도할 수 있게 된다.

 

결론

재귀 호출을 활용한 순열 생성은 문제를 하위 문제로 나누어 해결하는 간단하고 직관적인 방법이다. 재귀를 통해 각 자리를 채우고, 모든 가능한 조합을 탐색할 수 있으며, 이 방식은 알고리즘의 이해를 돕고 구현을 간편하게 만든다. 하지만 시간 복잡도가 O(N!)으로 매우 커지므로, 큰 입력에 대해서는 성능 최적화를 고려해 볼 필요가 있다.

 

 

비슷한 유형의 알고리즘들도 같이 정리해 보았다.

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 부분집합(Subset)

[알고리즘] 부분집합(Subset)

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 조합(Combination)

[알고리즘] 조합(Combination)