#include <stdio.h>

int combination(int n, int r){

	if(n==r || r==0){
		return 1;
	}

	// nCr = (n-1)C(r-1) + (n-1)C(r)
	return combination(n-1,r-1) + combination(n-1, r);

}

int main(){

	printf("%d", combination(7,4));

}

#include <stdio.h>

#define MAX_SIZE 1000

int combination(int n, int r){

	int arr[1000][1000];

	// nCr = (n-1)C(r-1) + (n-1)C(r)
	for(int i=0;i<=n;i++){
		for(int j=0; j<=r;j++){

			if(i==j || j==0)
				arr[i][j] = 1;
			else
				arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
		}
	}

	return arr[n][r];

}

int main(){

	printf("%d", combination(7,4));

}

#include <stdio.h>

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

void swap(int *a, int *b ){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void print_arr(){
	for(int i=0; i < sizeof(arr)/sizeof(int); i++)
		printf("%d ", arr[i]);
	printf("\n");
}

void permutation(int n, int r){

	// 탈출조건으로 r이 0이 되면 순열의 한 경우가 완료되었으므로 return합니다.
	if( r == 0){
		print_arr();
		return;
	}

	// 가장 끝에 있는 n-1의 위치의 원소와
	// 현재 보고 있는 i의 원소를 바꿔서
	// 재귀 함수에 넣어줍니다.

	// 1-2-3을 예로 들으면
	// 3(변수 i)과 3(변수 n-1)을 바꿉니다.
	// 그러면 3은 제일 뒤에 고정이고
	// 1과2를 둘이 바꾸는 경우가 생기므로
	// 1-2-3과 2-1-3이 생성됩니다.

	// 이제 다시
	// 2(변수 i)와 3(변수 n-1)을 바꿉니다.
	// 그러면 2는 제일 뒤에 고정이고
	// 1과3을 둘이 바꾸는 경우가 생기므로
	// 1-3-2와 3-1-2가 생성됩니다.

	// 숫자가 더 커지거나해도 같은 원리로 적용됩니다.
	for(int i=n-1; i>=0; i--){
		swap(&arr[i], &arr[n-1]);
		permutation(n-1, r-1);
		// 아래처럼 다시 swap을해줘야 마지막에 모두 끝났을 때 arr가 변화없게됩니다.
		swap(&arr[i], &arr[n-1]);
	}


}

int main() {
	permutation(sizeof(arr)/sizeof(int), sizeof(arr)/sizeof(int));
	return 0;
}

#include <stdio.h>

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

void swap(int *a, int *b ){
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void print_arr(int size){
	for(int i=0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

void permutation(int n, int r, int depth){

	// r과 depth의 크기가 같아지면 출력하고 반환합니다.
	// 배열 index가 0부터 depth-1까지(r-1까지)
	// 즉 r개만큼 앞에서 순열이 생성되었기에 반환합니다.
	if( r == depth){
		print_arr(depth);
		return;
	}

	// 원리는 위와 같습니다.

	// 1-2-3에서 2개를 고른다고 가정하면

	// 배열에서 1(변수 i)과 1(변수 depth)을 바꿉니다.
	// 그러면 1은 제일 앞에 고정이고
	// depth를 1을 증가시켜 다시 함수를 호출하면
	// 2와3를 둘이 바꾸는 경우가 생기므로
	// 1-2와 1-3이 생성됩니다.

	// 그 다음
	// 배열에서 2(변수 i)와 1(변수 depth)을 바꿉니다.
	// 그러면 2는 제일 앞에 고정이고
	// depth를 1을 증가시켜 다시 함수를 호출하면
	// 1과3을 둘이 바꾸는 경우가 생기므로
	// 2-1와 2-3이 생성됩니다.
	for(int i=depth; i<n; i++){
		swap(&arr[i], &arr[depth]);
		permutation(n, r, depth+1);
		swap(&arr[i], &arr[depth]);
	}


}

int main() {
	permutation(sizeof(arr)/sizeof(int), 3, 0);
	return 0;
}

#include <stdio.h>

int main (){

	// 스택에 집어넣을 값들
	int values[10] = {10,9,8,7,6,5,4,3,2,1};

	// 스택과 TOP변수
	int stack[100];
	int top=0; // <= 처음에 배열의 첫번째 원소가 top이라 볼 수 있다.

	// PUSH
	for(int i=0; i < sizeof(values)/sizeof(int); i++){
		// 아래와 같이 PUSH를 구현
		// top변수를 통해서 계속 top을 바라봅니다.
		// top - 1의 위치에 가장 최근에 넣은 값이 있습니다.
		stack[top++] = values[i];
	}

	// POP and PRINT
	for(int i=0; i < sizeof(values)/sizeof(int); i++){
		// 아래와 같이 POP을 구현합니다.
		printf("%d ", stack[--top]);
	}
	printf("\n");

	return 0;
}

#include <stdio.h>

int main (){

	// 큐에 집어넣을 값들
	int values[10] = {10,9,8,7,6,5,4,3,2,1};

	// 큐와 HEAD 그리고 TAIL변수
	int queue[100];
	int head=0,tail=0; // <= 처음에 배열의 첫번째 원소가 head와 tail이라 볼 수 있다.

	// ENQUEUE
	for(int i=0; i < sizeof(values)/sizeof(int); i++){
		// 아래와 같이 ENQUEUE를 구현
		// ENQUEUE 할때마다 tail의 위치에 값을 넣고 증가시니다.
		queue[tail++] = values[i];
	}

	// DEQUEUE and PRINT
	for(int i=0; i < sizeof(values)/sizeof(int); i++){
		// 아래와 같이 DEQUEUE을 구현합니다.
		// DEQUEUE 할때마다 head의 위치의 값을 반환하고 증가시킵니다.
		printf("%d ", queue[head++]);
	}
	printf("\n");

	return 0;
}