[TIL] 재귀로 푸는 순열과 조합

기면지·2021년 8월 3일

TIL algotirhm

TIL

목록 보기

1/10

안녕하세요!
오늘 공부한 알고리즘에 대해 간단하게 정리해보겠습니다 ~

순열

What is 순열? 🤔

순열은 서로 다른 것들 중 몇 가지를 뽑아서 한 줄로 나열하는 것 을 의미합니다.
순열의 순서는 유의미합니다.
따라서, 순서가 바뀐다면 다른 순열을 뜻합니다.

예시로, 학교 총회를 뽑는다고 했을 때 부서별로 n명 뽑는다는 것은 뽑히는 순서는 중요하지 않습니다.
뽑히느냐, 안뽑히느냐가 중요하겠죠?
그와 반대로 대학교 예비 번호를 생각해보면, 순서는 너무 중요하겠죠.
1번이라면 대학교에 붙을 수도 있지만, 1000번은 가망이 없다고 생각할 것입니다.

첫 번째 예시인 총회를 n명 뽑는다는 것은 뽑는 순서가 중요하지 않은 조합 ,
두 번째 예시인 대학교 예비 번호는 순서가 중요한 순열 입니다!

순열을 분석해보자!

순열을 수학적 식으로 나타내면, nPr 입니다.
n 은 총 요소의 개수이고, r 은 그 중에 순열로 순서지을 개수입니다.

nPr = n (n-1) … * (n-r+1)
nPn = n!

수학적으로는 위와 같은 결과가 나옵니다.
그래서 순열 알고리즘을 재귀로 구현했을 때, 시간복잡도는 O(N!) 입니다.
이 N! 은 N 이 12가 넘어가면 폭발적으로 계산량이 많아지기 때문에 결코 좋은 알고리즘이라고는 못하죠..

순열 by Java

int N;	// N까지의 수 중에 순열을 뽑는다.
int R;	// 뽑을 수
int[] numbers = new int[N];
boolean[] isSelected = new int[N];

순열을 담을 배열 numbers 와 해당 값을 사용했는지 여부를 체크해주는 isSelected 를 선언합니다.

void permutation(int count) {
	if (count == R)  {
	    System.out.println(Arrays.toString(numbers));
    }
    // ...
}

순열 알고리즘을 구현하는 perm 메소드입니다.
count 는 현재 구한 순열 요소들의 개수라고 할 수 있습니다.
count 가 입력받은 r 이라면, 더 이상 재귀를 진행하지 않습니다.

void permutation(int count) {
    // ...
    else {
    	for (int i = 1; i <= R; ++i) {
        	if (isSelected[i]) continue;
            numbers[count] = i;
            isSelected[i] = true;
            perm(count+1);
            isSelected[i] = false;
        }
    }
}

순열을 더 구해야하는 상황이라면, (count < R)
for문을 순회합니다.
numbers 에 해당 값을 무작정 저장하기 전에, 이미 앞 단계에서 뽑힌 값인지 isSelected 로 체크합니다.

만약, 이미 사용된 값이라면 continue 를 이용해 아래 수행문을 건너뛰어줍니다.

이미 사용되지 않은 값이라면, 순열 배열에 저장하고 해당 값의 isSelected 를 true 로 설정합니다.
그 후에 count+1 을 매개변수로 재귀 호출을 진행합니다.
다음 순열 값을 뽑으라고 함수에게 요청하는 것이라고 할 수 있습니다.

순열 값을 다 뽑고 함수가 return 됐다면, 이제 다음 값을 확인해야 하므로 isSelected 를 false 로 되돌려줍니다.

왜 다시 false 로 변경할까요?
다음 순열을 뽑으라고 요청한 재귀 호출이 끝나고 돌아온거라면, R 개의 요소가 모두 뽑혀서 배열을 출력한 후에 return 된 것입니다.
따라서 현재 위치에 현재 값으로 저장된 순열은 모두 구해졌다는 뜻이겠죠?
그렇기 때문에 isSelected 를 false 로 만들어줍니다.
Point. 순서가 유의미하기 때문에 다른 위치에서도 현재 값이 쓰일 수 있습니다!

조합

What is 조합?🧐

위에서 순열과 같이 설명한 조합입니다.
조합은 서로 다른 것들을 뽑는 경우의 수 라고 할 수 있겠습니다.
순열은 나열하지만, 조합은 나열하지 않습니다.
즉, 순서가 무의미합니다. 순서가 바뀌어도 같은 조합이죠!

조합을 분석해보자!

조합을 수학적 식으로 나타내면 nCr 입니다.
n 은 총 요소의 개수이고, r 은 그 중에 조합으로 뽑을 개수입니다.

nCr = n! / (n-r)! (r)!

수학적으로는 위와 같은 식이 도출됩니다.
조합 알고리즘을 재귀로 구현했을 때의 시간복잡도는 O(2^N) 입니다.
조합은 순열과 다르게 순서가 중요하지 않기 때문에, 재귀를 거듭할수록 반복문 순회 횟수가 적어지기 때문에
순열보다 효율적으로 구현된다고 할 수 있습니다.

조합 by Java

조합을 재귀 호출로 알고리즘을 구현했을 때, 순열보다 훨씬 간단합니다.
현재까지 결과로 사용한 숫자는 중요하지 않고, 단지 배열의 어디서부터 for문을 순회할 것인지만 확인하면 됩니다.

int N;	// N까지의 수 중에 조합을 뽑는다.
int R;	// 뽑을 수
int[] numbers = new int[N];

조합을 담을 배열 numbers 입니다.
순열과 다르게 isSelected 는 사용하지 않고 있습니다.

void combination(int count, int start) {
    if (cnt == R) {
        System.out.println(Arrays.toString(numbers));
    }
    
    // ...
}

매개변수가 순열에 비해 하나 추가되었습니다.
start 는 어느 숫자부터 넣을 것인지에 대한 정보입니다.
어차피 순서가 상관 없기 때문에, 앞에서부터 차근차근 넣어가자는 것이죠!

void combination(int count, int start) {
	// ...
    
    for (int i = start; i <= N; ++i) {
        numbers[count] = i;
        combination(count+1, i+1);
    }
}

그래서 start 부터 N 까지 for문을 순회하면서 차례대로 결과 배열에 넣어줍니다.
그 후에 재귀 함수를 호출해주면 끝입니다!
count 는 현재 count 의 다음부터, start 도 현재 위치의 다음부터로 설정합니다.

왜 조합에는 isSelected 가 없을까요?
왜냐면 조합은 순서가 중요하지 않기 때문에, 이미 앞에 쓴 거는 고려조차 하지 않아도 됩니다.

만약 4C3 이라고 했을 때, start 가 1일 때는 1, 2, 3, 4 모두 가능합니다.
여기서 1이 뽑혔다고 했을 때 그 다음에는? 2, 3, 4 만 가능합니다.
여기서 2가 뽑혔다면 그 다음은 3, 4 만 가능하고 123 124 등의 결과값을 도출할 수 있을 것입니다.

그래서 시간 복잡도가 O(2^N) 이 걸리는 것입니다! (점점 반복 횟수가 줄어들기 때문에)