순열, 조합, 부분집합 알고리즘

완전탐색 문제를 풀기위해 필수적으로 알아야되는 순열, 조합, 부분집합, 다음순열의 개념과 간략화한 알고리즘을 정리하려고 한다.

0. 공통 변수와 의미

순열, 조합, 부분집합, 다음순열에서 공통적으로 사용할 변수와 의미는 다음과 같다.

int N : 선택의 후보가 될 수 있는 N개의 수
int M : 선택하고자 하는 원소의 수
int cnt : 재귀 호출 내에서 해당 시점에서 선택한 원소의 수를 의미
boolean[] isSelected : 재귀 수행 중 과거에 해당 원소를 이미 선택을 했는지 판단하기 위한 boolean 배열
int[] selectedArr : 선택한 원소를 저장할 int 배열

1. 순열

순열은 주어진 숫자들의 순서를 고려하여 조합을 만들기 때문에 아래 두 가지를 체크해야한다.

• 후보가 되는 수들을 매번 처음부터 확인
• 해당 수가 이미 선택된 수인지 확인

// 1 ~ N 사이의 값 중에 M개 뽑기
 public void permutation(int cnt) {
 	if (cnt == M) {
    	    // 순열을 완성했을 때 처리할 로직
            return;
  	}
    	for (int i = 0; i < N; i++) {
    	    if (isSelected[i]) continue;
            selectedArr[cnt] = i + 1;
            isSelected[i] = true;
            permutation(cnt + 1);
            isSelected[i] = false;
        }
 }
            

2. 조합

조합은 주어진 숫자들의 순서를 고려하지 않고 조합을 만들기 때문에 순열처럼 선택 여부를 확인할 필요가 없다. 조합을 함수를 호출 할 때 현 시점에서 선택한 인덱스 + 1의 값을 매개변수로 넘겨주어 항상 다음 수 부터 선택하도록 구현할 수 있다.

• 다음으로 선택할 index값을 함수의 파라미터로 전달한다.
• 함수 수행 시점에서 선택할 값은 index부터 시작한다.

// 1 ~ N 사이의 값 중에 M개 뽑기
 public void combination(int cnt, int index) {
 	if (cnt == M) {
    	    // 조합을 완성했을 때 처리할 로직
            return;
  	}
    	for (int i = index; i < N; i++) {
    	    selectedArr[cnt] = i + 1;
            combination(cnt + 1, i + 1);
        }
 }
            

3. 부분집합

집합의 원소들을 선택, 비선택하는 과정을 통해 공집합을 포함한 각기 다른 부분집합을 구할 수 있다.

• 매 시점에서 원소의 선택과 비선택을 마킹하고 재귀함수를 호출한다.
• 원소를 M개 선택한 시점에서 선택 마킹 정보를 이용해 부분집합을 완성한다.

// 1 ~ N 사이의 값 중에 M개 뽑기
 public void subset(int cnt) {
 	if (cnt == M) {
    	    for (int i = 0; i < M; i++) {
            	if (isSelected[i]) {
                   // 완성된 부분집합에 포함된 요소이면 
                }
            }
    	    // 조합을 완성했을 때 처리할 로직
            return;
  	}
    	isSelected[cnt] = true; // 선택
       	subset(cnt + 1);
        isSelected[cnt] = false; // 비선택
       	subset(cnt + 1);
 }
            

4. 다음순열

작성중