[C/C++] 순열과 조합 알고리즘 구현하기 4

이번 시간은 순열과 조합 마지막 시간이다.

순열, 중복이 가능한 순열, 조합, 중복이 가능한 조합 순서로 포스팅을 했고, 이번이 바로 중복이 가능한 조합의 순서이다.

조합의 개념이 궁금하다면 앞의 강의를 보고 오자.

https://fantasycodingworld.tistory.com/125

[C/C++] 순열과 조합 알고리즘 구현하기 3

---

조합의 개념

 

조합의 개념을 복습하자면 아래와 같다.

n개 중에서 r개를 고르는데, 순서를 고려하지 않고 고르기 때문에 (1, 2)와 (2, 1)은 같은것으로 본다.

그래서 1, 2, 3에서 2개를 고르는 경우는 (1, 2), (1, 3), (2, 3)으로 3가지 경우의 수가 나온다.

그럼 중복이 가능하면 어떻게 될까?

(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)으로 6가지 경우의 수가 나올 것이다.

오늘인 중복이 가능한 조합을 알고리즘으로 구현해보자.

 

조합 알고리즘

 

조합의 알고리즘은 DFS를 활용한다.

재귀함수를 통해 숫자를 1개 고르고, 다음 숫자를 고르기 위해 같은 함수를 다시 호출한다.

그리고 다음 숫자를 고른 후 원하는 개수를 모두 골랐을 떄 지금까지 고른 숫자를 모두 출력하고 return 한다.

그럼 가장 마지막에서 두 번째 숫자를 고른 직후로 return 되는데, 이 때 방금 마지막으로 골랐던 숫자 다음 숫자를 고르는 방식으로 함수가 진행된다.

자세한건 아래 코드를 통해 살펴보자.

int tmp[5];

 

가장 먼저 선택한 숫자를 저장할 배열을 생성하자.

정수를 저장할 것이기 때문에 int형 배열 tmp를 생성했고, 길이는 5로 했다.

void combination(int depth, int next)
{
	...
}

 

다음으로 combination 함수이다.

인자로 int형 변수 depth와 next를 준다.

depth는 선택한 숫자의 개수를 알기 위함이고, next는 현재 호출된 함수 이전에 어느 숫자까지 선택했는지 알기 위함이다.

void combination(int depth, int next)
{
	if (depth == 2)
	{
		for (int i = 0; i < 2; i++)
			cout << tmp[i] << " ";
		cout << endl;
		return;
	}
	for (int i = next; i < 3; i++)
	{
		tmp[depth] = i + 1;
		combination(depth + 1, i);
	}
}

 

combination 함수의 내용을 보자.

가장 먼저 나오는 코드는 depth가 2일 경우 데이터를 출력하는 것인데, 이 코드로 알 수 있는 것은 depth가 선택한 숫자의 개수라는 것이다.

2개 숫자를 선택했다면 데이터를 모두 출력하라는 의미이다.

그리고 return하면 마지막 숫자를 선택하기 위해 호출한 함수가 종료된 라인으로 간다.

for문은 1부터 3까지 숫자를 순차적으로 고르기 위한 것이다.

i가 next부터 시작해서 3이 되기 전까지 1씩 증가한다.

이 때 depth에 따라서 i+1을 저장하는데, depth가 0일 경우 첫 번째 숫자를 골랐다는 의미이고, 1일 경우 두 번째 숫자를 골랐다는 의미가 된다.

그래서 depth가 2일 경우 2개의 숫자를 고른 것이 되는 것이다.

tmp에 데이터를 저장하고, combination 함수를 다시 호출한다.

depth+1을 넘겨줌으로써 숫자를 하나 골랐다는 의미가 된다.

그리고 next로 i값을 주는데, 이번에는 중복이 가능한 경우이기 때문에 i+1로 다음 숫자를 고르게 하는 것이 아닌, 현재 골랐던 숫자도 고를 수 있또록 하는 것이다.

그러므로 depth가 0일 때 1을 저장하고 combination(1, 0)을 호출하면 depth가 1일 때 또 1을 저장하게 된다.

그러면 가장 첫 번째로 고른 숫자의 조합은 (1, 1)이 된다.

이 조합을 출력하고 return 되면 i 값은 1 다음 2가 되므로 다음 조합은 (1, 2)가 된다.

이런 방식으로 중복이 가능한 조합을 출력할 수 있다.

#include <iostream>

using namespace std;

int tmp[5];

void combination(int depth, int next)
{
	if (depth == 2)
	{
		for (int i = 0; i < 2; i++)
			cout << tmp[i] << " ";
		cout << endl;
		return;
	}
	for (int i = next; i < 3; i++)
	{
		tmp[depth] = i + 1;
		combination(depth + 1, i);
	}
}

int main()
{
	combination(0, 0);
}

 

전체 코드이다.

메인 함수에서 시작은 인자로 0, 0을 준다.

아무것도 고르지 않은 상태에서 0번째 숫자부터 고르겠다는 의미이다.

for문 내에서 combination의 DFS 구현 방식을 이해하면서 코드를 작성해보자.

---

이렇게 해서 순열과 조합의 알고리즘을 구현해 보았다.

첫 번째 순열 포스팅부터 시작해서 순열과 조합의 개념을 이해하고, 각 알고리즘을 구현하면서 어떤 차이가 있는지 이해해보면 좋겠다.