[JAVA] <완전 탐색> 수열과 조합 알고리즘

완전 탐색 알고리즘에서 임의의 숫자로 되어있는 문자열을 준 뒤, 이 문자열에서 조합이 가능한 경우의 수를 뽑는 문제가 자주 나오는 것 같다. 

LV2 문제를 풀다가 도저히 선정리 없이는 풀기가 힘들고, 입사 코딩 테스트에도 등장할 개념 같아서 자세하게 다루고 넘어가려고 한다.

 

{1,2,3,4,5,6,7}의 배열을 가지고 3자리의 수를 전부 뽑는다고 가정하면, {1, 2, 3}과 {3, 2, 1}을 같은 경우로 생각하냐 마냐의 2가지 경우로 나눌 수 있다.

---

1. 중복을 허용하는 수열 뽑기

 

수열은 123을 뽑는 경우와 321을 뽑는 건 다르다고 생각하는 경우이다.

즉, {1,2,3,4,5,6,7} 중 3개를 뽑는 "모든" 경우의 수를 구하는 개념이다.

재귀함수를 이용하여 코드를 작성하면,

 

---

	private static void getSequence(List<Integer> inputArray, List<Integer> resultArray, int inputLen, int num) {

		if (num == 0) { // 원하는 자리수의 조합을 하나 완성했을 경우
			System.out.println(resultArray.toString()); // 출력 후 다음으로
			return;
		}
		for (int i = 0; i < inputLen; i++) {
			resultArray.add(inputArray.remove(i)); // 입력 리스트에서 1개를 제거하여 결과 리스트에 삽입
			getSequence(inputArray, resultArray, inputLen - 1, num - 1); // 배열을 한칸씩 줄여서 다시 재귀
			inputArray.add(i, resultArray.remove(resultArray.size() - 1)); 
			// 제거했던 입력값을 다시 입력 리스트에 삽입(중복 허용)
		}
	}

재귀를 생각하는 것이 조금 복잡해 보이지만, 데이터를 몇 개만 따라가다 보면 그렇게 복잡한 로직은 아니라는 것을 알 수 있다. 

 

 

2. 중복을 허용하지 않는 조합 뽑기

 

조합은 비슷한 개념이지만, 123을 뽑는 경우 321을 뽑는 경우 모두 1, 2, 3의 수가 들어가므로 같은 경우라고 생각하여 경우의 수 중 중복이 되는 경우는 제외한 경우의 수를 구하는 개념이다.

마찬가지로 재귀를 이용하여 작성해보면, 

---

private static void getCombination(List<Integer> inputArray, List<Integer> resultArray, int start, int inputLen,
			int num) {

		if (num == 0) {
			System.out.println(resultArray.toString());
			return;
		}
		for (int i = start; i < inputLen; i++) {
			resultArray.add(inputArray.get(i)); // visited의 역할, 현재 값을 삽입 후
			getCombination(inputArray, resultArray, i + 1, inputLen, num - 1); 
			// 현재 인덱스 + 1, 출력 자리수 -1을 한 뒤, 재귀를 한번 진행한 후
			resultArray.remove(resultArray.size() - 1); // 현재 값 제거
		}
	}

 

큰 차이가 없는 거 같아 보이지만, 진행했던 start 값을 증가시키면서 재귀를 진행하여 중복 값이 아예 나올 수 없게끔 하며, 재귀를 한 바퀴 다 돌기 전에는 사용했던 인덱스를 다시 사용하지 않는 게 특징이다.

 

이 두 개념을 잘 이용하면 왠만한 완전 탐색을 이용한 문제들은 쉽게 접근하여 풀이할 수 있다.

 

끝!!