[C/C++] 순열 / 조합 구현하기

c언어 알고리즘 문제를 풀면서 재귀함수 파트를 풀다보면 피할 수 없는 파트이다.

지금까지는 재귀 학습 자체를 안하다가 요즘 하게 되었는데 이제는 피할 수 없는 숙명이라고 받아들이고

이왕 공부하는 거 다시는 찾아보지 않도록 내 블로그에 내가 정리해보려고 한다.

 

1. 순열이란,

- 순열이란 서로 다른 n개 중에서 r개를 택하여 배열하는 경우를 말한다.

기호로는 nPr로 나타낼 수 있다.

 

- 순열의 예)

1)  1, 2, 3, 4, 5가 적혀 있는 숫자 카드가 있다, 이를 이용하여 세자리 수를 만들 수 있는 방법은 몇가지 인가?

-> 이 문제를 풀 때 어떻게 할 것인가. 세자리수면 백의 자리, 십의 자리, 일의 자리가 존재하고 각 자리에 올 수 있는 카드의 개수를 곱해줄 것이다. 즉, 백의 자리에는 카드의 개수 5개가 올 수 있고, 십의 자리에는 백의 자리로 넣은 카드 한개를 제외한 4개, 일의 자리는 백의 자리와 십의 자리 카드를 제외한 3개가 올 수 있으므로 답은 5 X 4 X 3이 된다.

 

2) n개의 수를 사용해서 가능한 순열을 모두 구하라. 

예를 들어 1, 2, 3을 나열하는 방법은 모두 6가지이다. 

      123     132     213     231     312     321

 

-> 순열은 n개 중에서 r개를 뽑아 배열하는 경우라고 하였고, 배열한다는 경우는 뽑은 것을 다르게 취급한다는 것이다.

즉, 순서를 고려한다는 뜻이다.

 

순열은 순서를 고려하여 뽑는 경우의 수  1) 일렬로 늘어서는 경우  2) 순서를 생각하여 나열하는 방법의 수  3) 상대적으로 다른 곳에 배열하는 경우

<순열 코드 - 중복허용>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int dep[20];
int n;

void rec(int x) {
	if (x == n) {
		for (int i = 0; i < n; i++) 
			printf("%d ", dep[i]);
		printf("\n");
		return;
	}

	for (int i = 0; i < n; i++) {
		dep[x] = i + 1;
		rec(x + 1);
	}
}

int main() {
	scanf("%d", &n);
	rec(0);

	return 0;
}



<순열 코드 - 중복허용x>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int dep[20];
bool visited[20];
int n;

void rec(int x) {
	if (x == n) {
		for (int i = 0; i < n; i++) {
			printf("%d ", dep[i]);
		}
		printf("\n");
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!visited[i + 1]) {
			dep[x] = i + 1;
			visited[i + 1] = true;
			rec(x + 1);
			visited[i + 1] = false;
		}
	}
}

int main() {
	scanf("%d", &n);
	rec(0);
	return 0;
}

 

2. 조합이란,

- 조합이란, 서로 다른 n개의 원소 중에서 순서에 상관 없이 r개를 택하는 것

기호로는 nCr로 나타낼 수 있고, 순열과 가장 큰 차이점! 바로 순서에 구애받지 않는 다는 것이다.

 

예제) n과 r을 입력받아 n개의 숫자 중 r개를 택하는 조합을 구하는 프로그램

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int arr[20];
bool visited[20];
int N, M;

void depth(int c,int t) {
	if (c == M) {
		for (int i = 0; i < M; i++)
			printf("%d ", arr[i]);
		printf("\n");
        return;
	}

	for (int i = t; i < N; i++) {
		if (!visited[i]) {
			arr[c] = i+1;
			visited[i] = true;
			depth(c + 1,i);
			visited[i] = false;
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	depth(0,0);

	return 0;
}

 

 

<수정> 

---

 

위 조합에 대한 코드는 사실 불필요한 부분이 존재한다. 바로 visited부분이다.

왜냐하면 순열과 달리 조합은 depth()함수 안 for문의 인덱스 시작 위치가 재귀함수를 할 때마다 달라진다.

즉, 전에 선택한 값에 의해 인덱스 시작 위치가 좌지우지 되고 이로 인해 방문 여부를 검사할 필요가 없다. 선택만 하면 된다.

 

따라서, 코드를 아래와 같이 간결하게 작성하여도 결과는 동일하다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, M;
int arr[20];
bool visited[20 + 1];

void depth(int index, int start){
    if(index == M){
        for(int i=0;i<M;i++){
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i=start;i<=N;i++){
        arr[index] = i;

        depth(index+1, i+1);
    }
}

int main(){
    fastio;
    cin >> N >> M;
    depth(0,1);

    return 0;
}