부분집합_재귀함수_순열 구하기 (JAVA)

[ 순열 (Permutation) ]

• n개의 원소 중 r개의 원소를 꺼내는 경우의 수
• 순서가 유효하기 때문에 원소의 중복을 허용함 (조합은 순서가 유효하지 않아 중복 불허)
• 경우의 수 : n! / (n-r)! 의 갯수를 가짐
• 표기법  : nPr

순서가 있도록 모든 경우의 수를 뽑아내는 것을 순열이라고 합니다. 부분집합 중 {1, 2, 3}과 {3,2,1}은 엄연히 다른 것으로 인식합니다. 예를 들어 {1,2,3} 중 2개를 조합해 만들 수 있는 모든 숫자를 구하라고 한다면 순열을 이용해야 합니다. 두 숫자를 붙이는 것은 순서에 따라 다르니까요.

 

 

---

 

 

일단 최대한 직관적으로 작성 후 백준 알고리즘 문제를 통해 검증을 완료한 코드입니다.

 

* 전체 코드

 

package pojoPrj;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		List<String> arr = new ArrayList<>();
		arr.add("a");
		arr.add("b");
		arr.add("c");

		List<String> result = new ArrayList<>();
		reculsion(arr, result, arr.size(), 2);

	}

	/**
	 * 순열 구하기
	 * 
	 * @param arr    : 기준 리스트
	 * @param result : 결과를 담아줄 리스트
	 * @param n      : 전체 갯수
	 * @param r      : 뽑을 갯수
	 */
	private static void reculsion(List<String> arr, List<String> result, int n, int r) {

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			reculsion(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}
	}
}

 

 

---

 

 

원리는 간단합니다. 3개의 원소 중 2개를 뽑는다고 가정하면, 1개의 원소를 뽑고나면 이제 나머지 2개 중 1개를 뽑기만 하면 됩니다.

 

 

 

1. 하나를 뽑아 결과에 넣는다.

 

리스트의 remove() 메소드는 지운 값을 그대로 리턴시켜주기 때문에 아래와 같이 한번에 작성 가능합니다.

 

result.add(arr.remove(i));

 

 

 

2. 이제 a와는 관계 없이 2개 중 하나를 뽑아야 하는 상태로 바뀌므로 다시 재귀호출을 해준다.

 

p와 r을 하나씩 줄여서 재귀호출을 시켜주면 됩니다.

 

reculsion(arr, result, n - 1, r - 1);

 

 

 

3. 재귀호출에서는 다시 첫 원소를 결과 리스트에 넣는다.

 

 

 

 

4. 이제 다음 재귀호출은 1개 중 0개를 뽑는 상태가 되므로 탈출문에 들어간다.

 

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

 

 

 

5. 재귀함수에서 빠져나오면 결과 리스트에 있던 것을 다시 원본 리스트로 옮겨준다.

 

제일 최근에 빠진 원소는 result 리스트의 가장 마지막에 있으므로 찾아서 있던 자리에 복구시켜주면 됩니다. 

 

arr.add(i, result.remove(result.size() - 1));

 

 

 

6. 반복문에 의해 2번 째 원소에 재귀함수를 다시 적용한다. 

적용되는 기준 원소가 계속 바껴줘야하므로 반복문을 돌려줍니다. 반복문에서 i < n은 현재 호출된 함수의 nPr에서 전체 갯수만큼 반복시켜주면 됩니다. n은 현재 원본 리스트에 남아있는 갯수와 동일합니다.

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			reculsion(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}

 

 

 

7. 위 로직이 계속 반복된다. 

 

첫번 째 원소인 "a"가 포함된 부분집합을 모두 찾았으면 이제 반복문이 작동해 다시 "b"를 기준으로 재귀함수가 시작됩니다. 원본 배열을 지운 뒤 다시 넣어주므로 계속 변함없이 유지되기 때문에 "b"가 다시 "a"를 가져오게 되어 순서가 바뀐 부분집합이 생성됩니다. 

 

하나를 선택해서 빼둔 뒤 남은 원소들에서 이어서 뽑는 작업을 계속 반복한다고 생각하면 됩니다.

 

	private static void reculsion(List<String> arr, List<String> result, int n, int r) {

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			reculsion(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}
	}

 

 

---

 

 

원리를 이해했다면 아래와 같이 조금 수정할 수도 있습니다. 위에서는 결과를 List에 붙였다 뗐다가 해서 속도상 조금 불리할 수 있습니다. 이번에는 현재 찾을 r의 갯수를 기준으로 해봅니다. 

 

nPr에서 r의 갯수가 정해져있으므로 결과를 담을 배열은 고정된 크기의 일반 배열로 잡아줍니다. 그리고 depth라는 정보를 추가해주는데, depth는 이 결과 배열을 채워넣을 순서를 의미합니다. depth가 0이라면 result[0]에 데이터를 넣을 순서라는 것입니다.

 

그리고 중복이 없을 경우 depth를 찾은 만큼 원본 배열의 문자가 빠지기 때문에 반복문은 전체갯수 n에서 찾은 갯수(빠진 갯수) depth만큼만 돌려줍니다. 재귀함수를 호출할 때는 depth만 하나씩 늘려주면 됩니다. 이렇게하면 굳이 결과를 리스트에 넣었다 뺐다 하지 않고 해당 result[depth]의 값만 계속 바꿔줄 수 있게 됩니다. 

 

	private void permutation(List<Integer> nums, int[] result, int depth, int n, int r) {

		if (depth == r) {
			System.out.println(Arrays.toString(result));
			return;
		}

		for (int i = 0; i < n - depth; i++) {
			result[depth] = nums.remove(i);
			permutation(arr, nums, result, depth + 1, n, r);
			nums.add(i, result[depth]);
		}
	}

 

 

---

 

 

 

순열이나 조합 등 경우의 수 재귀함수 알고리즘은 처음에는 직관적으로 와닿지 않을 수 있지만 몇 번 사용해보면 의외로 쉽습니다. 만약 위 알고리즘에서 중복 숫자를 허용해야한다면 원본 배열에서 해당 값을 뺐다 붙였다 하는 부분만 없애주면 됩니다. 

 

위 코드에서 아주 약간만 수정하면 조합을 구할 수 있는데, 다음글에 이어서 정리하도록 하겠습니다.