[Java] 순열, 조합, 부분집합 (Permutation, Combination, Subset)

순열, 조합, 부분집합 알고리즘은
알고리즘의 기초이고 각종 코딩테스트 단골 주제이다.
하지만 항상 막상 구현하려고 하면,
손과 머리가 버벅이는 경우가 많았다.
이번 기회에 블로그에 정리를 해서 장기 기억으로 남기기위해 포스팅한다.
이번 포스팅에는 재귀함수를 이용하여 구현할 것이다.
비트마스크라던지 다른 좋은 방법들이 많지만 아직 미숙하여 기초부터!

---

1. 순열 ( Permutation )

import java.util.Arrays;

public class Perm_Practice {

	static int[] src = { 1, 2, 3, 4, 5 };
	static int[] tgt = new int[2];
	static boolean[] select = new boolean[src.length];

	public static void main(String[] args) {
		perm(0);
	}

	private static void perm(int tgtIdx) {

		// 기저조건
		if (tgtIdx == tgt.length) {
			System.out.println(Arrays.toString(tgt));
			return;
		}

		for (int i = 0; i < src.length; i++) {

			if (!select[i]) {

				tgt[tgtIdx] = src[i];

				select[i] = true;
				perm(tgtIdx + 1);
				select[i] = false;
			}
		}
	}
}

순열 알고리즘에서는 nPr을 예로 들었을 때

n개의 원소를 가지고 있는 source 배열,

r개를 뽑아 담는 target 배열,

뽑았는지 체크하는 select 배열

이렇게 세가지가 필요하다.

재귀함수의 파라미터는 tgtIdx로 한다.

 

Logic

재귀함수의 파라미터는 tgt 배열의 인덱스로 한다.

기저조건으로 tgt배열의 길이가 되었을 때 리턴하도록 한다.

반복문을 src배열의 길이만큼 돌면서 선택하지 않은 src배열의 원소를 tgt배열에 담는다.

담은 배열의 인덱스는 select 배열에 방문처리하여 중복해서 담는것을 방지한다.

재귀의 깊이를 1 깊게하여 tgtIdx+1을 호출한다.

바로 다음 라인에서 방문처리를 지워줘서 모든 인덱스를 방문할 수 있도록 한다.

 

재귀함수의 핵심 부분

select[i] = true;
perm(tgtIdx + 1);
select[i] = false;

이 부분이 처음에 가장 어렵게 느껴지지만 사람의 머리로 재귀를 이해하는 것은 원래 어려운 것 같다. 가장 핵심적인 부분이다.

 

---

2. 조합 ( Combination )

import java.util.Arrays;

public class Comb_Two_Recursive {

	static int[] src = { 1, 2, 3, 4, 5 };
	static int[] tgt = new int[3];

	public static void main(String[] args) {
		comb(0, 0);
	}

	private static void comb(int srcIdx, int tgtIdx) {

		// tgtIdx 기저조건
		if (tgtIdx == tgt.length) {
			System.out.println(Arrays.toString(tgt));
			return;
		}

		// srcIdx 기저조건
		if (srcIdx == src.length) return;
		

		tgt[tgtIdx] = src[srcIdx]; // src의 값을 tgt에 담는다.

		comb(srcIdx + 1, tgtIdx + 1); // 현재 src를 담고 다음 tgtIdx를 재귀로 채우겠다.
		comb(srcIdx + 1, tgtIdx); // 현재 src를 담지 않고 현재 tgtIdx의 값을 재귀로 채우겠다.

	}

}

 

 

조합 알고리즘은 nCr을 예로 들었을 때,

n개의 원소를 가지고 있는 source 배열,

r개를 뽑아 담는 target 배열

이렇게 두가지가 필요하다.

재귀함수의 파라미터는 srcIdx와 tgtIdx를 사용한다.

파라미터가 한개인 재귀도 있지만 이게 더 직관적이고 간결해서 주로 사용한다.

 

Logic

기저조건 2가지.

tgtIdx가 tgt배열의 길이만큼 되면 r개만큼 전부 뽑았다는 뜻이므로 리턴한다.

tgtIdx가 tgt배열의 길이만큼 되지 않았는데 srcIdx가 src배열의 길이만큼 된 경우,

r개를 뽑지않고 끝까지 왔다는 뜻이므로 그냥 리턴한다.

 

재귀함수의 핵심 부분

comb(srcIdx + 1, tgtIdx + 1); // 현재 src를 담고 다음 tgtIdx를 재귀로 채우겠다.
comb(srcIdx + 1, tgtIdx); // 현재 src를 담지 않고 현재 tgtIdx의 값을 재귀로 채우겠다.

src의 값을 tgt에 담고

현재 tgt 상태를 가지고 다음 tgtIdx를 뽑기 위해 넘어가는 것이 첫번째 라인이고,

현재 srcIdx를 담지 않고 다음 srcIdx를 담기 위해 현재 tgtIdx를 가지고 재귀로 들어가는 것이 두번째 라인이다.

 

 

---

3. 부분집합 ( Subset )

public class Subset_Practice {

	static int[] src = { 1, 2, 3, 4, 5 };
	static boolean[] select = new boolean[src.length];

	public static void main(String[] args) {
		subset(0);
	}

	private static void subset(int i) {
		if (i == src.length) {
			print();
			return;
		}

		select[i] = true; // 선택
		subset(i + 1); // 재귀
		select[i] = false; // 선택 X
		subset(i + 1); // 재귀

	}

	private static void print() {
		for (int i = 0; i < select.length; i++) {
			if (select[i]) System.out.print(src[i] + " ");
		}
		System.out.println();
	}

}

부분집합 알고리즘은 n개의 배열에서 모든 부분집합을 뽑는다고 할 때,

전체 원소가 담긴 source 배열과,

뽑았는지 체크하는 select 배열

이렇게 두가지가 필요하다.

파라미터는 srcIdx가 들어간다. (편의상 i로 하였다.)

 

Logic

기저조건으로 i가 src 배열의 길이만큼 되면, 끝까지 탐색했다는 뜻이므로 

그 때의 select 배열을 이용하여 print하는 함수를 호출한다. 따로 분리하지 않아도 되지만 분리하였다.

 

 

재귀함수의 핵심 부분

select[i] = true; // 선택
subset(i + 1); // 재귀
select[i] = false; // 선택 X
subset(i + 1); // 재귀

현재 인덱스를 선택하고 다음 인덱스로 재귀를 타거나,현재 인덱스를 선택하지 않고 다음 인덱스로 재귀를 타는 두가지를 써준다.결과적으로 모든 src 인덱스에 대해 선택 or 선택 X 경우를 모두 고려하게 된다.

 

 

쉬운 내용일 수 있지만 주기적으로 되새겨 봐야하는 중요한 내용이기도 하다.이해가 어느정도 따라왔다면 실전에서 기계적으로 구현할 수 있는 능력도 중요하다고 생각한다.삼성 코테같은 경우 파이썬의 itertools를 사용하지 못하는 경우도 있었으므로 이정도는 구현할 줄 알아야 한다.

 

---

본 포스팅은 직접 작성한 내용이므로 가져가실 때는 출처를 남겨주시면 감사하겠습니다.