[Algorithm] 순열(Permutation)

개요

 

◎ 순열이란?

◎ 구현코드 (Java)

◎ 시간 복잡도

◎ 번외

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 순열에 대해 적어보는 시간을 가져보려고 합니다.

 

 

순열이란?

 

순열은 고등학교 수학 시간에 배웠던 것으로 개념을 정의해보자면 서로 다른 n개 중에서 순서를 생각하며 r개를 택하는 경우의 수를 의미합니다.

 

대표적으로 n명의 사람들이 r명을 택하여 일렬로 줄을 서는 경우의 수를 구하라고 하는 것이 있습니다.

 

예를 들어 3명(A, B, C) 중 2명을 택하여 일렬로 줄을 세운다고 하면 경우는 다음과 같습니다.

1. A B

2. A C

3. B A

4. B C

5. C A

6. C B

 

순열을 구하는 공식도 다음과 같이 있습니다.

 

위의 예시를 공식에 대입해보면 P(3) = 3! / (3-2)!으로 6이라는 결과값이 나오는데 직접 센 것과 동일한 값이 나오죠?

 

이렇게 고등학교 때 배웠던 순열이 알고리즘 풀이를 위해서도 종종 사용됩니다.

 

위의 예제를 코드로 구현해보도록 하겠습니다.

 

 

구현코드 (Java)

 

package math;

import java.util.Arrays;

public class Permutation {
	static int count;
	
	public static void main(String[] args) {
		String[] stringArray = new String[]{"A", "B", "C"};
		
		permutation(0, 2, 0, stringArray); // 두 번째 파라미터 값만 조정
		
		System.out.println("총 갯수: " + count); // 총 갯수: 6
	}
	
	public static void permutation(int n, int r, int depth, String[] array) {
		if(n >= array.length || depth >= r) {
			System.out.println(Arrays.toString(Arrays.copyOf(array, r))); // [A, B]
													    // [A, C]
													    // [B, A]
													    // [B, C]
													    // [C, B]
													    // [C, A]
			count++;
			return;
		}
		
		for(int a=n; a<array.length; a++) {
			String temp = array[a];
			array[a] = array[n];
			array[n] = temp;
			
			permutation(n+1, r, depth+1, array);
			
			temp = array[a];
			array[a] = array[n];
			array[n] = temp;
		}
	}
}

728x90

 

시간 복잡도

 

순열의 시간 복잡도는 O(N!)이라는 매우 큰 시간 복잡도를 가지고 있습니다.

 

이런 이유로 여러 알고리즘 문제들을 풀 때도 순열을 사용해야 되면 보통 n값의 크기가 커봐야 10초반 정도의 크기가 주어집니다,

 

그만큼 많은 시간을 소비하기 떄문에 잘못 사용하면 결과값을 몇 시간, 몇 일 뒤에 확인하는 상황이 발생할 수 있습니다.

 

 

번외

 

위의 코드를 이용하여 순열 알고리즘을 구현할 수 있지만 경험상 보통 자주 사용되는 순열 알고리즘은 n값과 r값이 동일한 형태입니다.

 

사람들을 일렬로 세우는 것으로 비유하자면 사람들을 모두 선택하여 일렬로 줄을 세우는 것을 의미하죠.

 

이런 경우를 위해 순열이 사용되는게 더 드물기에 위의 코드에서 r값을 제거하여 순열을 구현하면 다음과 같습니다.

 

package math;

import java.util.Arrays;

public class Permutation {
	static int count;
	
	public static void main(String[] args) {
		String[] stringArray = new String[]{"A", "B", "C"};
		
		permutation(0, stringArray);
		
		System.out.println("총 갯수: " + count); // 총 갯수: 6
	}
	
	public static void permutation(int n, String[] array) {
		if(n >= array.length) {
			System.out.println(Arrays.toString(array)); // [A, B, C]
									   	   // [A, C, B]
										   // [B, A, C]
										   // [B, C, A]
										   // [C, B, A]
										   // [C, A, B]
			
			count++;
			return;
		}
		
		for(int a=n; a<array.length; a++) {
			String temp = array[a];
			array[a] = array[n];
			array[n] = temp;
			
			permutation(n+1, array);
			
			temp = array[a];
			array[a] = array[n];
			array[n] = temp;
		}
	}
}

 

코드를 읽다가 문득 "그냥 맨 처음 코드에 r을 최대로 집어넣으면 되지 않는 건가?" 생각하시는 분들이 계실 수 있는데...

 

r을 생각하지 않으면 코드가 조금이라도 더 짧아지자나요? 네... 그냥 그렇다고요...

 

 

정리

 

● 순열은 n개 중 순서를 생각하여 r개를 택하는 경우의 수를 의미

● O(N!)이라는 매우 큰 시간 복잡도를 가짐

● 알고리즘 풀이를 위해 생각보다 자주 사용됨

 

이상으로 순열에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.