2015년 8월 18일 화요일

Delete Coment(주석 제거 프로그램).

간단한 주석을 제거하는 프로그램을 구현해 보았다.

프로그램 하다보면 '//' 같은 한줄 주석  '/*' 같은 여러줄 주석을 많이 사용한다.

이런 주석이 달린 파일을 받아서 주석을 제거한 파일을 만들어 보았다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stddef.h>
#define IN 0 // in 일때는 주석안에 들어갔을때
#define OUT 1 // out 일때는 주석밖으로 나왔을때
typedef unsigned int UINT;
char* AllocateInput(FILE*fp, UINT size); // 파일에 있는 문자전체를 메모리로 복사하는 함수
void DeleteComent(char*arr, UINT size, char* newArr);// 주석을 제거하는 함수
int main() {
UINT size;
char* arr;
char* newArr = NULL;
FILE* fp;
fp = fopen("test.c", "r");
if (fp != NULL) {
fseek(fp, 0l, SEEK_END); // 파일의 마지막 을 가르키게 한다
size = (UINT)ftell(fp); //마지막을 가르키고있는 파일포인터를 size 로 받는다
rewind(fp); // 다시 파일포인터를 파일의 처음주소로 가르킨다. 
arr = AllocateInput(fp, size);  
newArr = (char*)calloc(size + 1, sizeof(char));
DeleteComent(arr, size, newArr);
fclose(fp);
free(arr);
fp = fopen("main_rmc.txt", "w");
fprintf(fp, "%s", newArr);
fclose(fp);
free(newArr);
}
return 0;
}
char* AllocateInput(FILE* fp, UINT size) { 
char* arr = NULL;
int i = 0;
arr = (char*)calloc(size + 1, sizeof(char)); // 동적 메모리 할당( main에서 받아온 size+1 만큼)
while (!feof(fp)) { //파일의 끝까지의 문자들을 만들어진 메모리에 저장
arr[i] = fgetc(fp);
i++;
}
return arr; // 메모리 주소 반환
}
void DeleteComent(char* arr, UINT size, char* newArr) {
int state = OUT;  // 처음 상태 는 OUT
char* p = arr; // 캐릭터 포인터 p 가 문자열이 저장된 배열의 첫번째를 가르킴
int i = 0;
while ((*p) != '\0') { //p가 널문자를 만날때까지 반복
if (*p == '/'&& *(p + 1) == '/') { // 한줄 주석을 만나면 IN 으로 상태를 바꿈
state = IN;  
while ((*p) != '\n') { //개행문자를 만날때까지 포인터가 간다.
p++;
}
state = OUT; // 개행문자를 만나면 다시 OUT으로 상태를 바꿈
}
else if (*p == '/' && *(p + 1) == '*') {  // 여러줄 주석을 만나면 IN 으로바꿈
state = IN;
}
else if (*p == '*'&&*(p + 1) == '/') { // 여러줄 주석의 끝을 만나면 OUT
state = OUT;
p = p + 2;  // 마지막 '*/' 를 복사하지않기 위해 포인터를 2만큼이동
}
if (state == OUT) {
newArr[i] = *p; // 새로운 배열에 p가 참조하는 값을 복사.
i++;
}
p++; // p 는 1씩증가.
}
}



실행 해보면 다음과 같이 주석이 제거된 파일을 볼 수 있다.


2015년 8월 7일 금요일

Divide and Conquer(분할 정복)


분할 정복이란 컴퓨터가 큰 데이터를 한번에 처리할 수 없기 때문에,  작은 단위로 나누어

데이터나 문제를 해결(정복) 하는 알고리즘이다. 일단 이론은 다음그림을 보면  

    이해가 쉽다. 






자그럼 다음 과 같이 배열이 있다.  과연 연속된 수들중 가장 큰 연속을 찾고

싶을 때 어떻게 할것인가 ?  


정답은 4 -1 3 2 4 -7 10 2 로 연속된 배열이가장 큰배열이다. 이것을 분할 정복을 통해

찾아보자. 우선 그림처럼 가장 작은단위 까지 분할 하고 그수들 중 큰 값을 가져와 서로

비교한다. 재귀 함수를 이용해 왼쪽 오른쪽 가운데  값들의 연속을 작은단위부터 가져와

비교하는 것이다.  위그림과 설명이 이해가 안 간다면 코드를 보자. (파란색 펜으로 그린 배

열은 MidMax 함수로 찾은 최대값)



 

C language 2048_game

2048 게임을 작성해보았다.

2048게임이란 같은숫자를 계속 더해나가서 2048 이라는 블럭이 나오면 승리하는게임이다.

2048을 만들기전에 화면에 숫자들이 가득차서 더이상 움직일 수 없다면 게임에 패배한다.

간단한 함수 몇개 만 소개하자.


먼저 입력을 받는 함수를 짜기 전에 enum 으로 왼쪽 오른쪽 위쪽 아래쪽을 초기화 선언

해준다.


먼저 키보드 방향키(→,←,↑,↓)를  입력 받는 함수다. 방향키는 합성 코드로 찾아보면

두개의 수를 입력을 받는다.

왼쪽(224,75) 오른쪽(224,77)  위쪽(224,72) 아래쪽 (224,80) 이렇게 입력이 들어온다

그러므로 처음 224 가 들어올때까지 키보드 입력을 받고 다음 입력은 각각 방향키 고유의

숫자들을 받아준다.


각각 의 리턴값을 모와서 각 방향에따라 다른 함수를 호출해주는 함수.


위 함수는 왼쪽을 눌렀을때 호출되는 함수이다.  인접한 벽돌이 서로 같은숫자일 때와

테두리(벽쪽)에 숫자를 옮길수 있는 공간이 있을때 숫자를 합쳐주고 옮겨주는 코드이다.


랜드함수를 이용해, 숫자가 없는 빈 공간에 1/4의 확률로 '4' 3/4확률로 2를 생성하는 함수

다음은 게임 실행 화면이다. 


이렇게 원하는 게임 칸수를 정하면 칸수*칸수 만큼의 게임판이 나온다



게임을 진행하면 스코어도 나온다. 



숫자들이 보드를 가득채우고 더이상 움직이지 못하면 게임을 패배한다.

코드를 다운해서 컴파일 해보자.



2015년 8월 3일 월요일

Baseball Game(베이스볼, 야구 게임)

어렸을때 하던 베이스볼 게임을 간단히 코딩해 보았다.

베이스볼 게임이란, 4자리 숫자가 있으면, 그  숫자와 자릿수를 같이 맞추는 게임이다.

만약 숫자만 맞고 자리가 다르다면 ball,  숫자와 자릿수가 같으면 strike 이다.

간단히 한번의 진행에 strike 와 ball 의 갯수만 보여주는 코드를 작성해 보았다.

 1. 배경지식

숫자와 자리가 같으면 strike 를 카운트

같은 숫자만 있다면 ball 을 카운트

둘다 아니면 아무것도 아님;

2. 처리과정

  1) 정답인 숫자 4개를 배열에 입력 받는다. (배열 answer)

  2) 도전해볼 4개의 숫자를 입력할 배열을 만들어 입력받는다. (배열 in) 

  3) 반복문을 돌린다(i,j)
     
   -answer[j]와 in[i]가 같고 i와 j가 같으면 strike 를 카운트

   -answer[j] 와 in[i]가 같지만 i != j 이면 ball을 카운트 

  4) 카운트 한값을 출력

  5) 종료.


위는 스트라이크 와 볼을 판단해 각각의 갯수를 늘려주는 코드 이다.


실행 하면 먼저 정답(answer)을 입력한다.


그다음 자신이 도전해볼 수(in)를 입력한다


결과 : 5와 4 는 숫자는 있지만 자리가 달라 ball 이고 9는 둘다 같기 때문에 strike

따라서 1strike 2ball 이 된다.


Classify Number(숫자 구분하기)

이 코드 내용은

갯수를 입력하고, 입력받은 갯수만큼 숫자를 입력한다.

그리고 입력받은 숫자들 중에 홀수, 짝수, 양수, 음수의 갯수가 몇개있는지 보여주는

간단한 알고리즘이다.


위와 같이 갯수를 입력한다.


갯수 만큼 원하는 숫자를 입력한다.


입력한 숫자들중에서 혹수, 짝수, 양수, 음수의 갯수를 출력한다.

1. 배경지식

음수, 양수, 짝수, 홀수를 찾는다.

먼저, 짝수는 x%2==0, 즉 2로 나눴을때 나머지가 0이면 짝수다. 하지만 0은 2로 나눠지지만

짝수가 아니므로  (x%2==0&&x!=0)이어야 한다.

다음, 홀수는 반대로 짝수를 구분하고나서 (x%2!=0) 이면 홀수임을 알 수 있다.

양수는 x>0 

음수는 x<0

2. 처리과정
   
  1) 배열을 만든다. (크기가 100인 배열으로 만들어 보자)

  2) 원하는 갯수만큼 배열에 입력을 받는다

  3) 반복문을 원소의 갯수만큼 돌면서 음수, 양수, 짝수, 홀수의 갯수를 각각 세준다.



위의 코드는 차례로 짝수, 홀수, 양수, 음수의 갯수를 세주는 함수다.


2015년 8월 2일 일요일

원하는 숫자의 갯수 구하기(count number)

이번 알고리즘은 자신이 원하는 숫자가 총 몇개나 들어갔는지 찾는 알고리즘이다.

예를들어, 1~200 까지중에 7이라는 숫자가 몇번들어갈까?

뒤에 자리수가 7인것을 197 까지 새면 20개 가 되는가?

아니다. 77, 177, 71 등 7이 두 개이상 들어 가거나 7이 10의 자리, 100의 자리등 어디든지

올 수 있기 때문이다. 이모든 경우의 수를따져 숫자 7이 어디에 들어가던지 그 총 갯수를

찾는 코드를 구현해 보았다.

1. 선행 지식

각자리수 마다 7을 찾는 방법을 알아야한다.

그래서 생각한 방법이. 각자리수를 10의 배수로 나누고 그나머지를 일의 자리로 만들어

그 값이 7이면 그 수의 7이 들어가는 갯수를 알수있다.

예를들어 , 1777이라는 숫자가있으면 10000으로 나눴을때 몫이 0 이고 나머지가 1777이다.

이때, 이값을 10000보다 한 자리 작은 자릿수 1000 으로 나누면  1000의자리가 1임을 안다.

동일한 방법으로 자릿수를 낮춰 1000으로 나눴을때 몫이 1이 되고 나머지는 777 이된다.

나머지 777을 다시 100 으로 나누면 100의자리가 7이라는 것을 알 수 있다.

나머지 자릿수 도 동일한 방법으로 연산하면 각자릿수에 7이 몇번 들어가는지 알 수 있다.

2. 처리과정

1) 값을 입력받는다.

2) 입력받은 값을 '1.선행과정'의 내용대로 원하는 숫자(7)를 찾는다.

3) 원하는 숫자(7)을 찾을때 마다 count 를 늘려준다.

밑의 코드는 처리과정을 코딩 해본 것이다.

코드를 실행 해보자.
위 와 같이 숫자 를 입력받는다. 77을 넣어보자.

그렇다면 답은 7 , 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77 까지 총 16개가 나와야한다. 



값이 정확하게 나온다.






2015년 7월 30일 목요일

SumPrime Algorithm(서로 다른 두수 사이의 소수들의 합)

서로다른 두 자연수 사이의 '소수'들의 합을 구하는 알고리즘이다.

위와 같이 두수 2와 11을 입력하면


그 두수들(2와 11)사이의 소수들(2,3,5,7,11)의 합 (28)이 출력되는 알고리즘이다. 


1. 선행지식

1) 소수를 구한다.
 
   소수들의 합을 구하려면 먼저 그 소수들을 찾아야한다.

   그 소수들을 찾는다면 그 합을 구하는 것은 어렵지 않을것 이다.



2. 처리과정

1)두 수를 입력 받는다.

2)두 수 사이의 소수를 찾는다.

3)'2)'의 과정에서 찾은 소수들을 더한다.


그렇다면 먼저 어떤 수가 소수인지 어떻게 알것인가?

일단 소수(prime)란 어떤수를 자기자신 보다 낮은 수부터 차례대로 하나씩 나눴을때

나머지가 '0'  즉, 나눠지는 수가,  1과 자기 자신 밖에 없는 수를 말한다.

컴퓨터로 구현할때는 count라는 변수를 선언해서.  어떤 value 값을 1부터 자기자신(value)

까지의 값으로 나눴을때 나머지가 0인수(약수)가(value%i ==0) 있을 때 마다 count 를 늘려

준다.

그과정이 끝나고 count를 확인해 봤을 때 count값이 2라면 그 뜻은 나머지가 0인 값(약수)

이 자기자신과 1밖에 없다는 의미이고, 그말은 count=2인 값(value)은 소수라는 걸 알 수있

다.

코드를 보면 이해하기 쉽다.


  위의 함수는 받은 인자의 값이 소수인지 아닌지 판별 하는 함수 코드이다.

소수를 판별 하는 함수를 만들었을때 나머지 과정은 어렵지 않았다.


위 Calculate 함수를 보면 알수 있듯이 작은수(num1)부터 큰수(num2)사이까지의

수들을 하나씩 소수판별하면서 그값이 소수일 경우 SUM 에  계속 더해주기만 하면된다.

이렇게 어렵지않게 두수 사이의 소수들을 알고  그 수들을 합하는 프로그램을 만들어 보았

다. 이 과정에서 BOOL 이라는 용어를 정의하고 함수로 쓰는것, 삼항연산자로 결과값을 반

환해주는 것 등등 여러가지 기술을 익힐수 있엇다.

다음 c파일을 다운받아서 컴파일 해보면 알기 쉽다.

main.c

Coin Change Algorithm(거스름돈 알고리즘)

알고리즘 공부를 시작한게 된 건 컴퓨터적인 사고방식을 키우고자 함이다.


알고리즘을 컴퓨터로 구현하기 위해서는 선행지식과 처리과정을 알고있어야한다.


첫째로 거스름돈 알고리즘을 짜보았다.

거스름돈 알고리즘이란, 우리가 보통 돈을받고 거스름돈을 줄때 가장 큰 단위의 지폐부터

주고 그 다음 큰 단위 그다음 그다음 이런식으로 차례로 화폐를 교환 해주는것을 컴퓨터로

계산하게 만든 알고리즘을 말한다.

예를들어 9700원을 효율적으로 주려면, 5000원 짜리 1장, 1000원짜리 4장, 5원짜리 1개,

100원짜리 2개로 거슬러 주는것이다.



 위와 같이 코인을 입력받으면


이렇게 가장효율적으로 거슬러주는 프로그램이다.


다음은 이 알고리즘을 컴퓨터로 구현하는 과정

1. 선행지식

이 알고리즘을 구현하기 위해 필요한 선행지식으로는 우리는 가장 큰 단위의 화폐부터

작은 단위의 화폐 순으로 계산해 나가야 한다는 선행지식을 알아야한다.



2. 처리과정 [동전(500원, 100원, 50원, 10원) 으로만 바꿔주는 프로그램을 짜봤다]

1) 입력받은돈을 500원으로 나눠 나오는 몫이 500원의 갯수

2) 500원으로 나누고 남은 나머지 에서 100으로 나눠서 나오는 몫이 100 원의 갯수

3) 2)의 과정처럼 100으로 나머지 연산하고 남은 값을 50으로 나오는 몫이 50원의 갯수

4) 3)의 과정과 같이 10원의 갯수를 구한다.

다음은 위의 선행지식과 처리과정을 이용해 코딩을 한것이다.























Calculate 함수를 보면 2.처리과정을 잘 이해할 수있다.




2015년 7월 29일 수요일

Linked List

List Class 를 C 를 이용해 만들어보았다.


(연필로 하나 씩 짜보니 많은 코딩 실력에 향상에 도움을 주었다 . 이렇게 보니 뿌듯ㅎㅎ)

벡터는 자료를 삽입, 추가 , 제거 하는데 모두 시간복잡도가 n이지만,

리스트는 자료 삽입, 추가, 제거가 벡터와 달리 복잡도 1이라는 용이한점을 가진다.

이유는 리스트의 구조에 있다 . 밑의 그림을 보면 리스트를 이해하기 쉽다.

먼저 리스트의 구조는 위의 사진과 같다.

헤드라는 포인터가 가장첫번째 자료를 갖는 Node 형 구조체를 가르킨다.

Node 형 구조체는 다음(next) 과 전(previous) Node 형 구조체와 연결 할 수있는 포인터를 

가지고 있다. 

다음 사진은 새로운 자료(data)를 갖는 구조체를 추가할때의 과정이다.


4라는 자료를 연결하기 위해서 우선, Node*(노드의 포인터형) current 를 선언하고 

Current에 malloc 함수를 통해 Node 형 공간을 할당하고 4라는 값의 Data 를 넣어준다. 

위의 그림과 같다.

그리고 나서 Tail의 다음(Next)포인터를 Current 에 연결 해주고 Current 의 이전(Previous)

또한 Tail 에 연결해 준다. 그리고 Current 의 다음(Next)은 당연히 NULL 값을 준다.

그리고 마지막으로


Tail 을 current 가 가르키는 곳과 같은 곳을 가르키게 이어주면 4라는 값(Data)를 갖는

연결리스트로 만들수있다. 위의 과정은 많은 리스트 클래스 중에 PushBack 과정을

그림으로 그려 본것이다. 


위의 사진은 클래스를 만들때 쓰였던 . 헤더 파일 과 c파일 



2015년 7월 23일 목요일

Vector(c 자료구조 벡터)


2015/07/23 수업 3일차

벡터란 .,, 한마디로 동적배열이다.

오늘 처음으로 c로 클래스를 구현해 보았다.

객체지향이라는 의미를 몸소 느낄수 있는 코딩시간이었다.

c를 객체 지향적으로 만드는일은 매우 번거롭다. 구조체 안에 변수만 넣을 수 있다.

그래서, visual studio에서 구조체 접근 연산자인 '.' 을 찍으면 멤버 변수를 볼 수 있다.

만일 여기에, 함수를 넣을 수 있다면? c++언어의 클래스와 비슷한 기능을 사용할 수 있다.

하지만, c에서는 함수를 구조체에 넣을 수 없기 때문에, 함수 포인터를 사용하였다.

------------------------------------------------------------------------------------------------


벡터의 동작원리



위와 같이,[1,2,3] 인 크기가 3개인 배열이있다.  이때 , 4를 추가로 넣고싶다.


이럴땐, 크기가 기존보다 큰 임시의 배열을 생성한다.

기존의 [1,2,3]을 임시배열에 모두 복사한다.

넣고자하는 값을 임시배열에 추가한다.

기존 배열을 가르키는 포인터가 임시배열을 가르키면, 배열의 크기가 더 커진 상태가 된다.

C/C++은 기존 배열을 메모리 해제  해줘야 하지만, JAVA의 경우는 단순히 이동만 하면 된

다.


위와 같이 , C로 클래스를 만들어 보았다.

vector.c 다운로드

vector.h 다운로드

vector sample 다운로드