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


좌표평면에서 x와 y좌표가 주어졌을 때 그 점이 x축과 이루는 각을 구해보자


환경

  • C, C++
  • 삼각함수 및 역함수에 대한 이해


tangent란?

기본적으로 삼각함수를 알고 있다는 가정하에 x,y좌표가 주어졌을 때 x축과 이루는 각을 θ라고 하면 다음과 같이 tan(θ) = y/x라고 볼 수 있습니다.


atan(arctangent)란?

그렇다면 θ를 구할 때는 위에 있는 tan(θ) = y/x에 대해서 역함수를 취해주면 각 θ를 구할 수 가 있게됩니다.

그 역함수가 arctangent이며 tan-1(x)=arctan(x)=atan(x)=θ로 표현합니다.


C언어에서 atan2()를 이용해서 각도 구하기

C언어에서 atan()atan2()가 있지만 atan2()-π부터 π까지이기 때문에 즉, 음의 값 또한 표현 가능하기 때문에 atan2()를 사용한 예제입니다.

return 값들은 Radian 값이기 때무에 각도를 구하려면 180/π를 곱해줘야 합니다.

HelloWorld.c


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.1415926535

double getDegree(double y, double x){
   return atan2(y,x) * 180 / PI;
}

int main()
{
   printf("%lf\n", getDegree(1,1));
   printf("%lf\n", getDegree(1,-1));
   printf("%lf\n", getDegree(-1,1));
   printf("%lf\n", getDegree(-1,-1));

    return 0;
}


결과는 아래와 같습니다.

Result