C언어 순열과 조합

최근 문제를 풀다가 계속해서 순열과 조합 문제를 보게 되었는데, 제가 재귀가 약하다보니 항상 문제를 푸는데 어려움이 있었습니다.

 

그래서 이번에 정리를 잘해서 다시는 찾아보는 일이 없도록 만들고자 포스팅을 하려 합니다.

 

우선, 순열입니다.

#include <stdio.h>

int arr[4] = { 1, 2, 3, 4 };
int len = 4;

void swap(int a, int b) {
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void permu(int N) {
	if (N == 3) {
		for (int i = 0; i < 4; i++) {
			printf("%d", arr[i]);
		}
		printf("\n");
	}
	else {
		for (int i = N; i < 4; i++) {
			swap(i, N);
			permu(N + 1);
			swap(i, N);
		}
	}
}

int main(void) {
	permu(0);
}

위 코드를 사용하면, 자기 자신을 전부 순회한 후 순열 경우의 수를 만들기 시작합니다.

 

그 다음은 조합입니다.

#include <stdio.h>

void combi(int n, int r, int st);

int vis[5];

int main(void) {
	for (int i = 1; i <= 5; i++) {
		for (int j = 0; j < 5; j++) {
			vis[j] = 0;
		}
		combi(5, i, 0);
	}
}

void combi(int n, int r, int st) {
	if (r == 0) {
		for (int i = 0; i < n; i++) {
			printf("%d ", vis[i]);
		}
		printf("\n");
	}
	else {
		for (int i = st; i < n; i++) {
			if (vis[i] == 0) {
				vis[i] = 1;
				combi(n, r - 1, i);
				vis[i] = 0;
			}
		}
	}
}

우선 둘의 차이점은 재귀 함수 내에 visited 처리를 사용하느냐 안하느냐가 있습니다.

 

조합의 경우엔 한 번 체크 했던 애를 다시 체크할 필요가 없기 때문에 따로 visited 처리를 사용해야합니다. 다만, 순열의 경우엔 모든 경우를 다 체크를 해야하기 때문에 visited 처리를 해서는 안됩니다.

 

둘의 공통점을 보겠습니다. 바로 재귀 내의 반복문이 가장 중요한 키 포인트라고 생각합니다. int i라는 변수의 시작지점을 계속해서 증가시켜주면서 재귀를 넘겨주게 된다면, for문 시작점이 달라지면서 순회를 시작할 수 있습니다.

 

즉, for문을 전체를 돌지 않고 이 전 정보를 기억해서 재귀를 순회할 수 있으니, 시간을 단축 시킬 수 있는 방법입니다.

---

이상 C언어 순열과 조합였습니다. ^_^