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

저번 시간에는 순열의 개념을 알아보고 알고리즘을 구현했다.

아직 순열의 개념이 헷갈린다면 저번 포스팅을 보고오자.

알고리즘까지 구현해보고 오면 더욱 좋다.

https://fantasycodingworld.tistory.com/123

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

 

이번 시간에는 같은 순열 알고리즘이지만, 중복이 가능한 경우에 대한 알고리즘을 구현해 볼 것이다.

그에 더해, 코드에 대한 자세한 설명도 해볼 것이다.

---

순열 설명

 

우선 순열이란 아래와 같이 표현이 가능하다.

숫자 1, 2, 3 중 2개를 뽑을 경우의 수는 (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 처럼 6가지가 가능하다.

하지만, 중복이 가능할 경우에는 아래와 같이 표현이 가능하다.

(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

한 선택 묶음 안에 앞서 뽑았던 숫자를 다시 한 번 뽑아도 되는 것이다.

 

먼저, 처음의 경우를 코드로 구현할 때는 DFS를 활용해서 원하는 개수 만큼 다 뽑을 때까지 계속 재귀를 한다.

이 때 depth 변수를 사용해서 함수의 깊이를 선택한 숫자의 개수로 관리한다.

2개를 뽑을 경우 depth가 2가 되면 뽑은 숫자를 저장한 배열을 출력하고, return하여 함수를 나가 방문 확인 배열을 false 처리 후 다음 숫자를 뽑을 경우를 계산한다.

여기까지 일반적인 순열을 구하는 방법이고, 중복이 가능할 경우에는 방문 확인 배열을 사용하지 않으면 된다.

 

순열 코드 구현 (중복이 가능할 경우)

 

#include <iostream>

using namespace std;

int tmp[5];
bool check[5] = { 0, };

void permutation(int depth)
{
	if (depth == 2)
	{
		for (int i = 0; i < 2; i++)
			cout << tmp[i];
		cout << endl;
		return;
	}
	for (int i = 1; i < 4; i++)
	{
		if (!check[i])
		{
			tmp[depth] = i;
			permutation(depth + 1);
		}
	}
}
int main()
{
	permutation(0);
}

 

3개의 숫자 중 2개를 고르는 코드이다.

중복이 가능하기 때문에 check 배열을 활용하지 않는다.

그러므로 (1, 2), (1, 3) 순서로 뽑는 것이 아니라 (1, 1), (1, 2), (1, 3) 와 같이 뽑을 수 있는 것이다.

그 외에는 일반적인 순열을 구하는 방법과 동일하다.

숫자는 2개를 고르기 때문에 depth 변수를 활용해서 깊이를 파악한다.

처음 0을 넣어서 첫 번째 숫자를 tmp 배열의 0번째에 저장하고, 다음 함수를 호출할 때 depth+1을 인자로 준다.

그러면 depth가 1이 되었을 때 두 번째 숫자를 골라 tmp 배열의 1번째에 저장하고 depth+1을 인자로 함수를 호출해 depth가 2가 도니다.

2개를 고르기 때문에 depth가 2가 되었을 경우 지금까지 뽑은 숫자를 모두 출력하고 return한다.

---

오늘은 순열에 대한 복습과 중복이 가능할 경우의 순열을 구하는 코드를 구현해 보았다.

순열의 개념을 이해하면 중복이 가능하지 않을 경우와 가능할 경우의 코드 구현을 하는데 도움이 될 것이다.