[알고리즘] 순열과 조합

글을 작성하게 된 이유:

알고리즘 문제를 풀다보면 순열과 조합은 항상 마주치게되는 단골 손님입니다.
문제플 풀면서 어찌저찌 구현은 하지만 매번 헷갈렸고 그에 지체되는 시간이 발생했습니다. 정확한 개념부터 응용을 위한 틀이 되는 뼈대를 만들기 위해서 이 글을 작성합니다.

순열이란(Permutation)?

• 서로 다른 n개 중에 r개를 뽑아 순서 있게 나열하는 것 = nPr
• 서로 다른 n개 중에 n개를 뽑아 순서 있게 나열하는 것 = nPn = Factorial = n!
• 10! = 3628800 / 11! = 39916800 / 12! == 479001600 (알고리즘 문제에서 요구하는 시간제한 내에 풀이 불가능)

조합이란(Combination)?

• 서로 다른 n개 중에 r개를 순서 없이 골라낸 것 = nCr
• nCr = n-1Cr-1 + n-1Cr (nC0 = 1) 재귀적 표현 (이 부분이 궁금하시다면 파스칼 삼각형과 이항 계수를 검색해 보시면 됩니다!)

순열, 조합 -> 코드

• 순열과 조합은 반복문을 통해서 구현이 가능하지만, nPr nCr 처럼 뽑는 개수가 정해지지 않은 경우에는 재귀적인 표현을 통해 구현을 합니다.

• 순열 시간복잡도: O(n!)

• 조합 시간복잡도: O(2^n)

• 참고1. 비트마스킹을 통해서 방문처리를 할 수 있지만, 원리를 더 직관적으로 보기 위해서 방문배열을 사용하였습니다.

• 참고2. static 멤버를 사용하면 메모리에 접근 하는 과정이 많기 때문에 매개변수를 사용하는 것보다 성능(시간측면)에서 불리하지만 구현이 간편하기 때문에 static 멤버를 사용하였습니다.

- 순열

public class Main {
	static int[] numbers; // 뽑는 수를 담기위한 배열
    static int[] input; // 입력 받은 수를 담는 배열
    static int N; // 입력 받는 수의 개수
    static int R; // 뽑을 개수
    static boolean[] visited; // 방문처리 배열
    public static void main(String[] args)
    {
    	Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        input = new int[N];
        numbers = new int[R];
        visited = new int[N];
        for (int i=0; i<N; i++) 
        {
        	input[i] = sc.nextInt();
        }
        
        permutation(0);
    }
    
    private static void permutation(int cnt) 
    {
    	// 기저 조건: R개를 선택한 경우
        if (cnt == R)
        {
        	return;
        }
        
        for (int i=0; i<N; i++) 
        {
        	// 방문했던 적이 있다면 방문X
        	if (visited[i]) continue;
            
            visited[i] = true; // 방문처리
            numbers[cnt] = input[i]; 
            perm(cnt+1);
            visited[i] = false // 되돌리기
        }
    }
    
}

- 조합

public class Main {
	static int[] numbers; // 뽑는 수를 담기위한 배열
    static int[] input; // 입력 받은 수를 담는 배열
    static int N; // 입력 받는 수의 개수
    static int R; // 뽑을 개수
    public static void main(String[] args)
    {
    	Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        input = new int[N];
        numbers = new int[R];
        for (int i=0; i<N; i++) 
        {
        	input[i] = sc.nextInt();
        }
        
        combination(0, 0);
    }
    
    private static void combination(int cnt, int start) 
    {
    	// 기저 조건: R개를 선택한 경우
        if (cnt == R)
        {
        	return;
        }
        
        for (int i=start; i<N; i++) 
        {
        	// 조합은 방문 배열 필요 없다!
            // 순서가 중요하지 않기 때문에, 이미 앞에서 쓴 것은 고려조차 하지 않아도 된다.
            numbers[cnt] = input[i]; 
            combination(cnt+1, i+1);
        }
    }
    
}