C언어 - 조합 알고리즘 [nCr]

경우의 수 순열을 프로그래밍화 (나열, 카운팅)

 

조합이란?

 - 서로 다른 n개에서 순서를 고려하지 않고 r개를 선택하는 방법의 수

 

구현 방향

 - n의 원소의 갯수가 늘어날 수록 for문의 중첩이 계속 늘어나야 한다. 

 - for문으로 구현할 경우 중첩이 많아질경우 효율이 떨어지고 n과 r의 값이 변할때마다 코드를 수정해줘야한다.

 - 재귀함수를 사용해서 문제를 풀어보도록 하자.

 

코드

#include<stdio.h>

int arr[] = {1,2,3,4,5}; //전역 변수로 선언
int Copy[5]; //arr배열을 복사하기 위한 배열

void print_Comb(int count);
void Combination(int n,int r,int c);

void print_Comb(int count){
    for(int i=0;i<count;i++){
        printf("%d",Copy[i]);
    }
        printf("\n");
}
void Combination(int n,int r,int c){ //재귀함수
    if(r==0){ 
        print_Comb(c);
        return;
    }
    if(n<r){
        return;
    }
    else {
        Copy[r-1] = arr[n-1];
        Combination(n-1,r-1,c);
        Combination(n-1,r,c);
    }
}
int main(){
    Combination(5,3,3);
}

 

n과 r의 값이 변할때마다 코딩을 수정해야한다.

다음엔 동적 할당을 활용해 배열을 할당해보도록 하자!

 

재귀함수가 코딩으로만 보면 이해가 어렵기 때문에 한번쯤 3P3 혹은 3P2 간단한 수로 직접 적어가면서 흐름을 파악하는게 큰 효과가 있다.

 

C언어 - malloc, free, sizeof를 이용한 동적 할당을 이용해

 

#include<stdio.h>
#include<stdlib.h>//malloc함수를 사용하기 위함

int *arr;
int *copy;//나열할 배열
void Combination(int *arr, int *copy, int n, int r, int depth);
void print_arr(int *copy, int n);

int main(){
	int n,r,c;
	
	//n과 r을 공백을 두고 입력받는다
	scanf("%d %d",&n,&r);
	c=r;
	//n개 중에서 n개의 배열 할당
	arr = (int*)malloc(n*sizeof(int));
	//r개를 선택한것을 담기위한 배열
	copy = (int*)malloc(r*sizeof(int));

	//n배열 값 입력
	for(int i=0;i<n;i++)
		arr[i]=i+1;
	
	Combination(arr,copy,n,r,c);
	
	free(arr);
	free(copy); //동적 할당 해제
	return 0;
}
void print_arr(int *copy, int n){
	for(int i =0;i<n;i++){
		printf("%d",copy[i]);
	}
	printf("\n");
}
void Combination(int *arr, int *copy, int n, int r, int depth){
	if(r==0){
		print_arr(copy, depth);
		return;
	}	
	if(n<r){
		return;
	}else{
		copy[r-1] = arr[n-1];
		Combination(arr,copy,n-1,r-1,depth);
		Combination(arr,copy,n-1,r,depth);
	}
}

arr배열을 동적으로 할당해주며 초깃값을 설정해주고 나열한 것을 저장하기 위한 배열 copy도 동적으로 할당하며 

동적 할당을 활용해 n과 r의 값이 변함에 상관없이 효율적인 코드를 만들 수 있었다.

 

*조합에서 swap 함수를 사용할때 왜 포인터를 사용했는지 설명

C언어 - 포인터 활용, call by value, call by reference

C언어 - malloc, free, sizeof

 

C언어 - 순열 알고리즘 [nPr]