c++) 조합 구현하기

조합이란 순서에 상관없이 n개중에 r개를 선택하는 것입니다.

 

• 중첩 반복문 사용하기

0번부터 차례대로 번호가 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드입니다.

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    for(int i=0; i<7; i++)
        for(int j=i+1; j<7; j++)
            for(int k=j+1; k<7; k++)
                for(int l=k+1; l<7; l++)
                    printf("%d %d %d %d\n",i,j,k,l);
 }

 

만약 다섯개 여섯개를 골라야 하는 경우라면?

 

5중 6중 for문을 사용해야 할 것입니다.

 

아래와 같이 재귀함수를 사용하여 작업을 나누면 더욱 간결하게 사용할 수 있습니다.

 

• 재귀함수 사용하기

#include <iostream>
#include <vector>
using namespace std;

vector <int> answer;
bool selected[10];

void printAnswer() {
	for(int i=0; i<answer.size(); i++) printf("%d ",answer[i]);
	printf("\n");
}

// 파라미터 차례로 "원본 배열" / "현재 인덱스" / "선택한 개수" / "선택할 개수" 
void solution(vector <int> &v, int idx, int cnt, int size) {
	// 원하는 개수가 선택되었으면 출력
	if(cnt == size) {
		printAnswer();
		return;
	}
	for(int i=idx; i<v.size(); i++) {
		// 선택된적 없는 숫자라면 저장 후 재귀호출
		if(selected[i] == false) {
			selected[i] = true;
			answer.push_back(v[i]);
			solution(v,i+1,cnt+1,size);
			answer.pop_back();
			selected[i] = false;
		}
	}
}

int main() {
	vector <int> test;
	test.push_back(1);
	test.push_back(2);
	test.push_back(3);
	test.push_back(4);

	// 4개중에 3개 고르기
	solution(test,0,0,3);
}

결과

1. solution 함수에서 전달한 파라미터에 따라 조합을 생성해줍니다.

1-1. 파라미터는 차례로 (전체 배열, 선택할 첫 인덱스, 선택한 개수, 선택할 개수) 입니다.

2. 만약 "선택한 개수 == 선택할 개수" 가 된다면 원하는 개수를 선택한 것이므로 출력을 하는 등 원하는 작업을 합니다.

3. 그렇지 않다면 선택할 첫 인덱스부터 차례로 선택한 적이 없는 항목에 대해 재귀호출을 하며 저장해나갑니다. 

 

이와 같이 재귀 호출을 사용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 아주 쉽게 작성할 수 있습니다.