[알고리즘] 순열(Permutation) 및 조합(Combination) 알고리즘

중.고등학교 때 경우의 수를 통해 가짓수를 공부하게 되고 Factorial을 비롯한 수열, 조합 부분 또한 공부하게 된다. 더 나아가서 중복 순열과 중복 조합도 있다.

이 글에서는 순열과 조합을 어떠한 알고리즘을 통해 구현을 할 것인지 확인해 볼 것이다.

 

1) 순열 (Permutation)

순열은 순서가 있는 경우의 수다.

간단히 이야기 하자면 1, 2, 3 세가지 수가 나타날 수 있는 세자리 경우의 수를 구하는 문제가 되겠으며 각각의 숫자가 일의 자리, 십의 자리, 백의 자리 자릿수의 순서를 생각해야 한다.

 

즉 111 -> 112 -> 113 -> 121 -> 122 -> .... 이렇게 경우의 수를 나열 할 수 있다.

위의 예시를 코드로 구현해 보자.

#include<iostream>
#include<vector>

using namespace std;

void print(){

	for(int i=0; i<vc.size();i++){
    	cout<<vc[i]<<" ";
    }
    cout<<endl;

}
void dfs(int count){
	if(count ==3){
    	print();
    	return;
     }
    
    for(int i=1; i<4; i++){
    	vc.push_back(i);
        dfs(count+1);
        vc.pop_back();   
    }


}
int main(){
	dfs(0);
}

 

사실 순열 조합을 공부했을 때 이해 하기 어려웠떤 것은 재귀함수뒤에 vc.pop_back() 부분 이었다. 이 부분을 한번 자세히 나열해보자

 

우선 첫번째 실행되는 로직은 다음과 같다.

vc.push_back(첫번째 자리 수 1: vc[1])  --> dfs(1) --> vc.pop_back(가장 마지막 숫자 pop) -> 첫번째 자리수 push(2 and 3)일 때

 

여기서 dfs(1)이 또 어떻게 돌아가는지 보자

 

1) count ==1 이기 때문에 if 문에 걸리지 않는다.

2) vc.push_back(두번째 자리 수 1:vc[1,1]) --> dfs(2) --> vc.pop_back(가장 마지막 숫자 pop) -> 두번째 자리수 push(2 and 3)

 

다시 또 dfs(2)는

 

1) count ==2 이기 때문에 if 문에 걸리지 않는다.

2) vc.push_back(세번째 자리 수 1:vc[1,1,1]) --> dfs(3) --> vc.pop_back(가장 마지막 숫자 pop) -> 세번째 자리 수 push (2 and 3)

 

 

즉 3자리수 숫자의 첫번째 경우의 수는

 

1) vc.push_back(첫번째 자리 수 1: vc[1] )

2) vc.push_back(두번째 자리 수 1: vc[1,1] )

3) vc.push_back(세번째 자리 수 1: vc[1,1,1] )

4) dfs(3) ->return;

5) vc.pop_back(가장 마지막 숫자 pop) : vc[1,1]

6) 세번째 자리 수 push (2 and 3) --> dfs(2)

7) vc.pop_back(가장 마지막 숫자 pop) : vc[1]

8) 두번째 자리 수 push (2 and 3) --> dfs(1)

9) vc.pop_back(가장 마지막 숫자 pop) : vc[]

10) 첫번째 자리 수 push (2 and 3)

 

 

 

해당 내용 처럼 출력된다.

 

2) 조합 (Combination)

순열에서는 단순히 push와 pop을 재귀함수를 통해 구현하였다. 하지만 조합에서는 순서 상관 없이 중복이라는 것을 생각하기 때문에 이 숫자가 지금 선택 되었는지 아닌지 파악해야 한다.

 

ex. (1,2,3)과 (3,2,1)은 순열에서는 서로 다운 경우지만 조합에서는 같은 경우의 수이다.

 

한번 1 ~ 6까지의 숫자중에서 3개를 선택하는 경우의 수를 구해보자.

 

#include<iostream>
#include<vector>

using namespace std;

vector<int> vc;
bool visit[10] = {false, };
void dfs(int count, int index) {

	if(count ==3) {
    	for(int i=0; i<vc.size();i++) {
        	cout<<vc[i]<<" ";
        }
        
        cout<<endl;
    }
    
    for(int j=index; j<7; j++) {
    
    	if(visit[j] == true) continue;
        
        visit[j] = true;
        vc.push_back(j);
        dfs(count+1,j);
        visit[j] = false;
        vc.pop_back();
    
    }
 
}

int main() {

	dfs(0,1);
}

 

순열처럼 push, pop 형태는 동일하나 visit 배열을 통해 해당 숫자를 선택 했는지 안했는지를 판별하며 dfs 함수가 실행 된 후에는 다시 false로 값을 주어 그 for문 탐색시에는 허용할 수 있도록 하였다.

 

추가로 for문에서도 시작점이 1이 아니라 매개변수 index값을 추가 하여 그 숫자 이후부터 ( 그 전은 이미 push 했으니까) push 할 수 있도록 한다. 해당 코드 실행 시

 

 

해당 경우의 수가 출력된다.