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

고등학생 때 배우는 내용 중 순열과 조합이 있다.

흔히 nCr, nPr이라고 부르는데, 오늘은 순열에 대해서 먼저 공부하자.

---

최근 조합론을 공부하면서 순열과 조합에 대해서 다시 살펴보게 되었다.

한 번 공부해두면 프로그래밍을 하는데 큰 도움이 되니 꼭 숙지하도록 하자.

순열 nPr

 

순열은 Permutation이라고도 하며, n개의 숫자 중 r개를 고를 경우의 수를 의미한다.

예를 들어 1, 2, 3 중 2개의 숫자를 고른다고 가정해보자.

(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 총 6개의 경우의 수가 있다.

앞에서부터 한 개를 고르고, 나머지 숫자 중에서 차례대로 두 번째 숫자를 고른다.

1을 고른 뒤 2, 3을 순차적으로 한 뒤에 2로 시작할 때 다시 1, 3을 고른다.

r개를 고를 때 중복되게 고르지는 않지만, 앞에서 r개를 고를 때 뽑았던 숫자를 다시 안 뽑는 것은 아니다.

정리하자면, (1, 2)를 뽑았다면 다음 번에 (1, 2)는 다시 뽑지 않는다.

하지만 (1, 2)를 뽑았더라도 (2, 1)로는 다시 뽑을 수 있는 것이다.

그러므로 6개의 경우의 수를 나타낼 수 있다.

이것을 식으로 바꿔보면 아래와 같다.

nPr 공식

 

3개 중에서 2개를 골라 나열하는 경우의 수는 3!/(3-2)!로 구할 수 있다.

(3x2x1) / 1 = 6

이게 이해가 되었다면 이제 코드로 구현해보자.

 

코드 구현 전 잠시 쉬어가면서 하는 이야기인데, 최근 유튜브 같은데서 개발자들을 보면 기계식 키보드를 많이 쓰는 것 같다.

기계식 키보드의 탱글거리는 키감(?)이 좋다고 해서 써보신 분들의 후기 덧글로 남겨주시면 매우 감사.

아래는 쿠팡에서 기계식 키보드 검색해서 링크 걸어 보았다.

https://link.coupang.com/a/b6wiWm

앱코 옵티컬 기계식 게이밍 유선 일반형 키보드 클릭 - 유선키보드 | 쿠팡

색감이 예뻐서 찾은건데, 유명한 기계식 키보드나 블루투스 키보드를 찾는 중.

 

그럼 이제 코드를 구현해보자.

Permutation은 깊이 우선 탐색법 즉, DFS를 통해 구현할 수 있다.

순열 코드

#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])
		{
			check[i] = true;
			tmp[depth] = i;
			permutation(depth + 1);
			check[i] = false;
		}
	}
}
int main()
{
	permutation(0);
}

 

permutation 함수는 인자로 깊이를 받는다.

여기서 깊이란, 몇 개의 숫자를 뽑을지를 의미한다.

배열 tmp에 몇 개의 숫자를 저장할 건지가 되는데, 깊이가 0일 경우 배열의 제일 첫 번째 칸, 1일 경우 제일 두 번째 칸에 뽑은 숫자를 저장한다.

그리고 깊이가 충족되면 원하는 만큼 숫자를 모두 뽑았음을 의미하므로 그대로 출력한다.

출력 결과는 아래와 같다.

1 2
1 3
2 1
2 3
3 1
3 2

 

이처럼 순열를 구현한 코드는 깊이 우선 탐색법을 통해 깊이가 0일 때 첫 번째 숫자, 1일 때 두 번째 숫자를 뽑는 식으로 진행된다.

그리고 충분한 숫자를 뽑으면 배열 출력 후 return하여 check 배열의 마지막으로 뽑은 숫자의 인덱스를 false 처리 후 다시 다른 숫자를 뽑는 방식으로 실행된다.

---

오늘 학습한 내용은 순열의 기본 개념과 알고리즘 구현 방법이다.

nPr의 개념과 공식을 이해하고 이것을 코드로 구현하는 연습을 해보자.

 

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.