[알고리즘] 순열, 중복순열, 조합, 중복조합 총 정리 (Java, 자바)

출처 : https://www.geeksforgeeks.org/java-program-to-print-all-permutations-of-a-given-string/?ref=gcse

 

이번 포스팅에서는 코딩 테스트를 풀다 보면 정말 자주 나오는 순열, 중복순열, 조합, 중복조합에 대해 정리해보려고 한다.

순열, 중복순열, 조합, 중복조합은 완전 탐색 문제에서 자주 나오고, 구현하는 방법만 알면 문제를 정말 쉽게 풀 수 있으므로 꼭 알아야 하는 알고리즘이다.

구현은 재귀를 이용한 백트래킹을 사용할 것이다.

개인적으로 이 방법이 가장 깔끔하다고 생각한다.

주의해야 할 점은 시간 복잡도가 굉장히 크므로 n이 10 근처일 때 사용해야 한다. (n이 굉장히 크면 시간 초과 발생)

 

구현에 앞서서 초기 조건은 다음과 같다.

public class Main {
    static int[] arr = {1, 2, 3, 4};    // n에 해당하는 배열
    static int[] output;                // r개를 뽑은 배열
    static boolean[] visited;            // 방문 처리 배열
    static int N = 4, R = 3;            // n은 4, r은 3

    public static void main(String[] args) {
        output = new int[R];        // r개를 뽑은 배열 초기화
        visited = new boolean[N];    // 방문 처리 배열 초기화

        ...
    }
}

n은 4, r은 3, 초기 배열은 {1, 2, 3, 4} 이다.

---

 

 

순열

순서를 고려하면서 서로 다른 n개에서 중복 없이 r개를 일렬로 나열하는 수이다.

경우의 수는 nPr = n! / (n-r)! 로 시간 복잡도는 O(n!) 이 소요된다.

static void permutation(int depth, int n, int r) {
    // 순열이 완성된 경우
    if(depth == r) {
        System.out.println(Arrays.toString(output));
        return;
    }

    // 0부터 n까지 반복
    for(int i = 0; i < n; i++) {
        // 방문하지 않은 값이면 넣기
        if(!visited[i]) {
            visited[i] = true;    // 방문 처리
            output[depth] = arr[i];    // 현재 depth를 인덱스로 사용
            permutation(depth + 1, n, r);    // depth + 1를 전달
            visited[i] = false; // 다음 순열을 뽑기위해 방문처리 제거
        }
    }
}

사용 및 결과

사용

permutation(0, N, R);

 

결과

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

---

 

 

중복 순열

순서를 고려하면서 서로 다른 n개에서 중복으로 r개를 일렬로 나열하는 수이다.

경우의 수는 n^r 로 시간 복잡도는 O(n^r) 이 소요된다.

순열과 다르게 방문처리를 하지 않는다.

static void repeatPermutation(int depth, int n, int r) {
	// 순열이 완성된 경우
	if (depth == r) {
		System.out.println(Arrays.toString(output));
		return;
	}

	// 0부터 n까지 반복
	for (int i = 0; i < n; i++) {
		output[depth] = arr[i]; // 현재 depth를 인덱스로 사용
		repeatPermutation(depth + 1, n, r); // depth + 1를 전달
	}
}

사용 및 결과

사용

repeatPermutation(0, N, R);

 

결과

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[1, 3, 4]
[1, 4, 1]
[1, 4, 2]
[1, 4, 3]
[1, 4, 4]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 1, 4]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[2, 3, 4]
[2, 4, 1]
[2, 4, 2]
[2, 4, 3]
[2, 4, 4]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 1, 4]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 2, 4]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
[3, 3, 4]
[3, 4, 1]
[3, 4, 2]
[3, 4, 3]
[3, 4, 4]
[4, 1, 1]
[4, 1, 2]
[4, 1, 3]
[4, 1, 4]
[4, 2, 1]
[4, 2, 2]
[4, 2, 3]
[4, 2, 4]
[4, 3, 1]
[4, 3, 2]
[4, 3, 3]
[4, 3, 4]
[4, 4, 1]
[4, 4, 2]
[4, 4, 3]
[4, 4, 4]

 

---

 

 

조합

순서를 고려하지 않고 n개에서 중복 없이 r개를 일렬로 나열하는 수이다.

경우의 수는 nCr = n! / r! * (n-r)! 로 시간 복잡도는 O(2^n) 이 소요된다.

순열과 다르게 인자로 start를 전달한다.

static void combination(int start, int depth, int n, int r) {
	// 조합이 완성된 경우
	if(depth == r) {
		System.out.println(Arrays.toString(output));
		return;
	}
	
	// start 부터 n까지 반복
	for(int i = start; i < n; i++) {
		output[depth] = arr[i];	// 현재 depth를 인덱스로 사용
		combination(i + 1, depth + 1, n, r);	// i + 1, depth + 1를 전달
	}
}

사용 및 결과

사용

combination(0, 0, N, R);

 

결과

[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

 

---

 

 

중복 조합

순서를 고려하지 않고 n개에서 중복으로 r개를 일렬로 나열하는 수이다.

경우의 수는 nHr = (n-1+r)Cr = (n-1+r)!/r! * (n-1)! 이다.

조합과 다르게 i + 1이 아닌 i를 인자로 전달한다.

static void repeatCombination(int start, int depth, int n, int r) {
	// 조합이 완성된 경우
	if(depth == r) {
		System.out.println(Arrays.toString(output));
		return;
	}
	
	// start 부터 n까지 반복
	for(int i = start; i < n; i++) {
		output[depth] = arr[i];	// 현재 depth를 인덱스로 사용
		repeatCombination(i, depth + 1, n, r);	// i, depth + 1를 전달
	}
}

사용 및 결과

사용

repeatCombination(0, 0, N, R);

 

결과

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 3, 3]
[1, 3, 4]
[1, 4, 4]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 3, 3]
[2, 3, 4]
[2, 4, 4]
[3, 3, 3]
[3, 3, 4]
[3, 4, 4]
[4, 4, 4]

---

 

 

전체 코드

import java.util.Arrays;

public class Main {
	static int[] arr = { 1, 2, 3, 4 };
	static int[] output;
	static boolean[] visited;
	static int N = 4, R = 3;

	public static void main(String[] args) {
		output = new int[R];
		visited = new boolean[N];

		// 1. 순열
		permutation(0, N, R);
		
		// 2. 중복순열
		repeatPermutation(0, N, R);
		
		// 3. 조합
		combination(0, 0, N, R);
		
		// 4. 중복조합
		repeatCombination(0, 0, N, R);
	}

	// 순열
	static void permutation(int depth, int n, int r) {
		// 순열이 완성된 경우
		if (depth == r) {
			System.out.println(Arrays.toString(output));
			return;
		}

		// 0부터 n까지 반복
		for (int i = 0; i < n; i++) {
			// 방문하지 않은 값이면 넣기
			if (!visited[i]) {
				visited[i] = true; // 방문 처리
				output[depth] = arr[i]; // 현재 depth를 인덱스로 사용
				permutation(depth + 1, n, r); // depth + 1를 전달
				visited[i] = false; // 다음 순열을 뽑기위해 방문처리 제거
			}
		}
	}

	// 중복순열
	static void repeatPermutation(int depth, int n, int r) {
		// 순열이 완성된 경우
		if (depth == r) {
			System.out.println(Arrays.toString(output));
			return;
		}
	
		// 0부터 n까지 반복
		for (int i = 0; i < n; i++) {
			output[depth] = arr[i]; // 현재 depth를 인덱스로 사용
			repeatPermutation(depth + 1, n, r); // depth + 1를 전달
		}
	}
	
	// 조합
	static void combination(int start, int depth, int n, int r) {
		// 조합이 완성된 경우
		if(depth == r) {
			System.out.println(Arrays.toString(output));
			return;
		}
		
		// start 부터 n까지 반복
		for(int i = start; i < n; i++) {
			output[depth] = arr[i];	// 현재 depth를 인덱스로 사용
			combination(i + 1, depth + 1, n, r);	// i + 1, depth + 1를 전달
		}
	}
	
	// 중복조합
	static void repeatCombination(int start, int depth, int n, int r) {
		// 조합이 완성된 경우
		if(depth == r) {
			System.out.println(Arrays.toString(output));
			return;
		}
		
		// start 부터 n까지 반복
		for(int i = start; i < n; i++) {
			output[depth] = arr[i];	// 현재 depth를 인덱스로 사용
			repeatCombination(i, depth + 1, n, r);	// i, depth + 1를 전달
		}
	}
}

 

순열, 중복순열, 조합, 중복조합은 구현만 할 줄 알아도 풀 수 있는 문제가 많으니

눈감고 구현할 수 있을 정도로 반복 숙달하는 것을 추천한다.

연습은 아래 문제들을 추천한다.

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (시리즈)