재귀함수를 통해서 순열을 구하고 출력해보자


환경 및 선수조건

  • C, C++
  • 순열과 재귀함수에 대한 이해


순열이란

  • 순열(Permutation) : 순열이란 n개의 원소에서 r개를 골라서 나열하는 방법을 의미합니다.


Permutation


순열의 구현 방법

  • 재귀함수를 통해서 구현을 하며 아래 코드처럼 for문을 돌면서 각각 하나하나 원소에 대해서 가장 오른쪽에 있는(배열을 기준으로) 원소와 바꾸고 재귀함수를 돌려주는 식으로 해주면 됩니다.
  • 아래 코드 주석에 보다 더 자세한 설명을 첨부합니다.


재귀를 통한 순열의 구현 - 1

  • 아래는 모든 원소에 대해서 순열을 구할 때 즉, P(n,k)에서 n=k인 경우의 코드입니다.

permutation_example.cpp

#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;
}


재귀를 통한 순열의 구현 - 2

  • 만약에 4개의 원소중에서 3개만 골라서 순열을 구하고 싶은 경우 즉, P(n,k)에서 n!=k(n>k)인 경우의 코드입니다.
  • 위의 코드와 다르게 depth라는 변수를 통해서 원소의 제일 앞에서부터 하나씩 고정해나가면서 변경합니다.

permutation_example.cpp

#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;
}


C언어에서 배열을 통해 기본적인 기능만 하는 스택과 큐를 만들어보자.


환경 및 선수조건

  • C언어 및 gcc
  • 스택과 큐의 작동원리 및 이해


C언어에서 빠르게 스택과 큐 구현하기

C에서 알고리즘이나 빠르게 코딩을 할 때 배열을 통해서 스택과 큐를 구현하고자 한다. 단, 여기서 배열의 크기는 들어갈 수 있는 최대를 가정하고 구현할 예정! 즉, 동적할당이 아니라 정적할당으로 임의로 사이즈를 정해주고 구현할겁니다.

비록 여기서 배열에 값들을 삭제하거나 하지는 않지만 추상적으로 보면 최소한의 스택과 큐의 기능을 구현합니다.

  • 스택은 LIFO(선입후출)의 구조만 top이라는 변수를 통해서 구현합니다.

  • 큐는 FIFO(선입선출)의 구조만 headtail이라는 변수를 통해서 구현합니다.


배열을 통한 스택의 구현

simple_stack_by_array.c

#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;
}


배열을 통한 큐의 구현

simple_queue_by_array.c

#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;
}


Java를 Command Line에서 실행할 때 Heap Size를 설정해서 실행하자.


환경

  • Command Line 환경에서 Java


JVM을 실행할 때 Heap(힙)메모리 사이즈를 조절하자

Java를 Command Line을 통해서 실행할 때 -Xmx[memory size] 옵션을 지정해주면 원하는 메모리 사이즈로 JVM을 실행할 수 있다. 즉 자바 프로그램 실행이 가능하다.

  • 메모리를 1024mb로 설정
$ java -Xmx1024m [your program]
  • 메모리를 1gb로 설정
$ java -Xmx1g [your program]


Heap 메모리 사이즈 설정을 통해 Weka 실행하기

실제로 Command Line에서 Weka를 실행하는 명령어를 보면 아래와 같습니다.

$ java -Xmx1024m -jar weka.jar

gcc를 통해서 cpp파일을 Linux 혹은 Mac 환경에서 컴파일해보자


환경

  • C++언어 및 컴파일러
  • gcc 및 g++


c, cpp, gcc, g++?

  • c : C언어로 만든 코드파일의 확장자명입니다.

  • cpp : C++언어로 만든 코드파일의 확장자명입니다.

  • gcc : GNU 컴파일러 모음(GNU Compiler Collection, 줄여서 GCC)으로 C언어로 만든 파일을 컴파일하기 위한 컴파일러들의 모음이라 볼 수 있습니다.

  • g++ : gcc와 마찬가지로 GNU 컴파일러들중에 하나로 C++언어로 만든 파일을 컴파일 할 때 주로 사용합니다.


gcc로 cpp파일 컴파일하기

  • gcccpp를 컴파일하면 다음 아래과 같이 symbol을 찾을 수 없다거나 clang: error: linker command failed with exit code 1와 같은 에러를 보여줍니다.

gcc compile error

  • C++을 위한 라이브러리 혹은 코드가 함께 포함되지 않아서 생기는 문제라서 다음 아래 명령어를 통해 -lstdc++ 같이 옵션으로 주면 gcc로도 cpp파일이 컴파일 가능합니다.
$ gcc -o filename filename.cpp -lstdc++


g++로 cpp파일 컴파일하기

  • 일반적으로 다음과 같이 g++를 통해서 cpp를 컴파일합니다.
$ g++ -o filename filename.cpp

n번째 피보나치 수열을 동적계획법 그리고 재귀함수를 통해서 각각 구현해보자


환경

  • C, C++
  • 동적계획법(Dynamic Programming)에 대한 이해
  • 재귀함수(Recursion)에 대한 이해


재귀함수란?

  • 재귀함수 : 재귀함수란 자신의 함수를 재호출하여 실행하는 함수를 의미합니다. 주로 분할정복과 같이 문제를 작은 부분으로 나누어서 문제를 해결할 때 많이 사용합니다.


동적계획법이란?

  • 동적계획법(DP) : 동적계획법이란 문제를 작게 쪼개서 작은 문제부터 하나하나 해결한 해를 통해 모아서 큰 문제를 해결하는 방법을 의미합니다.


재귀함수(Recursion)로 구하기

  • Top-down 방식 : 큰 문제를 작은 문제로 나누면서 해결하는 방식

fibonacci_by_recursion.c


#include <stdio.h>

int fibonacci_recursion(int n){

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

	else if(n == 1){
		return 1;
	}

	else{
		return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
	}


}

int main(){

	int i;

	for(i=0; i<20; i++){
		printf("%d ",fibonacci_recursion(i));
	}
	printf("\n");

    return 0;
}


동적계획법(Dynamic Programming)으로 구하기

  • Bottom-up 방식 : 작은 문제부터 하나씩 해결해 올라가는 방식

fibonacci_by_dp.c


#include <stdio.h>

int dp_array[100];

void fibonacci_dp(int n){

	int i;

	dp_array[0] = 1;
	dp_array[1] = 1;

	for(i=2; i< n; i++){
		dp_array[i] = dp_array[i-1] + dp_array[i-2];
	}

}


int main(){

	int i;

	fibonacci_dp(20);

	for(i=0; i<20; i++){
		printf("%d ", dp_array[i]);
	}
	printf("\n");

    return 0;
}