#알고리즘의 정의

 

 알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다. 


#알고리즘의 조건

 

 입력 

 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.

 출력 

 알고리즘은 최소 1개 이상의 결과를 가진다.

 명확성 

 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.

 유한성 

 알고리즘은 단계들을 유한한 횟수로 거친 후 문제가 해결되고 종료되어야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.

 효과성 

 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다



#좋은 알고리즘


 알고리즘이 위의 조건들을 모두 만족한다면 문제를 풀 수 있다고 할 수 있지만, '효과적으로' 풀어낸다고 할 수는 없다. 위에서 말한 유한한 시간이 몇 달 혹은 몇 년이 될 수도 있기 때문이다. 따라서 우리는 알고리즘을 효율성으로 평가하게 되고, 컴퓨터에서는 시간과 메모리라는 두 자원을 얼마나 소모하는지가 효율성의 중점이 된다.


평가기준

-시간 복잡도(time complexity) : 얼마나 적은 시간안에 문제를 풀어 내는가

-공간 복잡도(space complexity) : 얼마나 적은 공간(메모리)을 활용해서 문제를 물어 내는가



#공부할 사이트



https://www.digitalculture.or.kr/koi/StudyOnline.do


공부할 사이트는 한국 정보 올림피아드 라는 사이트로



정보올림피아드 대회를 위한 

문제해결을 위한 창인적인 알고리즘 강좌들을 

두루 제공하는데

강좌 내용이 아주 고급지고 알맹이만 있어서

이미 C언어에 익숙하고 알고리즘을 조금 짜본 사람에게는

매우매우 효과적인 사이트이다.


강좌는 중급과 고급편이 각각 12편씩 총 24편으로 구성되어있다.

(편당 약 20분 정도)



중급에는 주로 여러가지 자료 탐색 알고리즘을 배우고





고급에서는 재귀함수의 확장, 동적 테이블 응용, 이분 탐색, 자료구조를 이용한 알고리즘 고속화 및 문제해결 등이 있다.


알고리즘을 깊숙히 배워볼 생각이 있으면 꼭 한번 쯤 듣고 따라 쳐봤으면좋겠다.





reference:https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



WRITTEN BY
Who1sth1s

,

1. 필요성

 

 보통 운영체제에서는 커널모드와 유저모드 두가지 프로세서 접근모드를 지원한다. 그 이유는 유저 어플리케이션이 함부로 운영체제의 치명적인 데이터를 수정하거나 삭제하지 못하게 하기 위해서 이다. 커널모드는 모든 시스템과 메모리에 접근이 허가된 프로세스 실행 모드이다. 유저모드보다 커널모드에 더 높은 권한을 줌으로써 유저모드에서 에러가 발생했을 때 시스템 전체의 안전성을 보장해 준다.



2. 구조


.

 .커널모드와 유저모드의 구조는 위와 같다. 사용자가 직접적으로 하드웨어 장치를 제어한다면 큰 문제 발생할 수 있기 때문에 사용자 애플리케이션은 System Call 을 통해 직접적인 하드웨어 요청이나 중요한 시스템 요청을 한다. 요청을 하면 유저 애플리케이션은 유저모드에서 커널모드로 잠시 전환 되었다가 커널모드에서 작업을 실행한뒤 응답을 유저 애플리케이션에 반환하면서 다시 유저모드로 되돌아가게 된다.





 

이러한 구조를 갖춤으로써 사용자 프로세스가 운영체제와 데이터를 함부로 들여다보거나 변경하지 못하게 보호한다.



3. 특징


유저모드

1. 사용자 애플리케이션의 코드가 실행 됨.

2. 시스템 데이터에 제한된 접근만이 허용, 하드웨어 직접 접근 불가.

3. 시스템 서비스 호출 시 유저모드에서 커널모드로 잠시 전환됨.

4. 스레드는 자신만의 유저모드 스택을 가짐.


커널모드

1. 모든 시스템 메모리에 접근할 수 있고 모든 CPU명령 실행 가능.

2. 운영체제 코드나 디바이스 드라이버 같은 커널모드 코드를 실행한다.



참고 : 

http://lapislazull.tistory.com/

http://www.scitech.co.kr/upload/book_image/s_402/ESDP-Ch06.PDF




WRITTEN BY
Who1sth1s

,

-프로젝트 멤버


Layer7 15기 - 전현성, 김수민, 장동건, 박상원




-USB 자료 터트리기 알고리즘

 

1. 프로그램이 실행되면 시작프로그램에 자동 등록.

2. 콘솔창을 안보이게 함.

3. 외부 디스크가 있나 체크.

3. 외부 디스크가 있으면 디스크 폴더를 모두 탐색.

4. 탐색하다가 Hwp, pptx, c, html 파일이 나오면 파일을 새로 쓰기 해서 자료를 초기화 시킴.

5. 모든 작업이 끝나면 프로그램을 껏다가 다시 실행시킴(빠르게 껏다 켜서 작업 관리자에서 프로세스 종료 못하도록)

6. 무한 반복 -> 새로운 USB가 꽂히자 마자 자료가 날라감.





-구현방법 (소스)






-레지스트리를 이용하여 시작 프로그램에 등록.

-파일 입출력 함수의 에러 반환을 활용하여 외부 디스크 체크.

-재귀 함수를 활용하여 USB내의 모든 폴더와 확장자를 탐색

-Win Api의 CreateFile 함수로 파일을 새로 쓰기하여 데이터를 지움



공부용으로 사용하시고, 

#악용하지 마세요#

##악용 시 법적책임은 본인에게 있습니다## 

virus.exe



-프로젝트 역할분담


전현성 : 함수화 및 재귀함수를 통한 파일 탐색

김수민 : 콘솔 창 안보이게, 콘솔창 다시 열기

장동건 : 파일 생성, 외부 디스크 체크

박상원 : 시작프로그램 등록



WRITTEN BY
Who1sth1s

,

-프로젝트 멤버


Layer7 15기 - 전현성, 김수민, 문호현, 박상원




-심심이란?



http://www.simsimi.com/talk.htm

사람들이 가르쳐주는 대로 대답을 하는 시스템을 가지고 있다.

원작 심심이 해보기 위 링크


-콘솔창으로 심심이 구현해보기












-구현방법 (소스)






-체계적인 함수화.

-Input과 Output을 동적할당으로 저장함으로서 메모리 절약.

-text를 이용한 데이터의 저장과 불러오기(파일 입출력)

-strstr을 통한 유사 질문 찾기구현.

-Win Api를 통한 콘솔창 디자인




-프로젝트 역할분담


전현성 : Main함수 제작, 함수수정 및 함수화, search함수 제작

김수민 : 파일 입력 및 출력, Log 함수, 아이디어

문호현 : 유사질문 찾기 및, WinApi 함수

박상원 : 콘솔창 입력 및 출력, WinApi 디자인


WRITTEN BY
Who1sth1s

,

-2048 게임이란?


http://gabrielecirulli.github.io/2048/

백번 말하는것 보다 한번 해보는것이 훨 났다.


-콘솔창으로 2048 구현하기








-구현방법 (소스)


 구현할 때 가장 고민한 것이 방향키를 눌러서 같은 수 들을 합쳐줄 때, 방향이 총 4가지가 있는데 어떻게 이것을 처리할 것인가 고민을 하다가 배열을 가상으로 돌리는 방법을 사용해서 해결했다. 

 배열을 해당하는 방향으로 돌렸을 때 열과 행 그리고 방향을 인자로 주면 해당하는 배열에 해당하는 주소를 반환하는 합수를 만들었다.





#include stdio.h
#include time.h
#include conio.h
#include windows.h
#define LEFT 75
#define RIGHT 77
#define UP 72
#define DOWN 80
 
void gotoxy(int x, int y);
void game_start(int map[][17]);
void game_print(int map[][17]);
void number_print(int arr[][4], int score);
void create(int arr[][4]);
int create_check(int arr[][4]);
int dmove(int arr[][4], int d, int *score);
int *arr_tc(int arr[][4],int i,int j,int d);
void game_over(int *score);
 
void main() {
	gotoxy(10, 5); printf("2048 시작하기");
	gotoxy(12, 6); printf("PRESS ANY KEY"); getch();
	int map[17][17];
	game_start(map);//map초기화
	while (true) {//게임 종료시 다시 시작
		int score = 100, input;
		int arr[4][4] = { 0, 2, 2 ,};
		system("cls");//map을 새로그림
		game_print(map);//map을 draw함
		while (true) {//조작
			if (kbhit()) {
				if (getch() == 224) {//특수키
					switch (getch()) {//방향키를 입력받음
					case LEFT:  input = 1; break;
					case UP:    input = 2; break;
					case RIGHT: input = 3; break;
					case DOWN:  input = 4; break;
					}
//더이상 움직일 수없고 배열이 꽉참 -> 게임 오버 -> 게임 재시작
					if (dmove(arr, input, &score)) break;
				}
				number_print(arr, score);//프린트 갱신
			}
		}
	}
}
 
 
 //프린트할 위치
void gotoxy(int x, int y) {
	COORD Pos = { x * 2, y };
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}
 
//맵을 초기화함
void game_start(int map[][17]) {
	int arr_temp[17][17] = {
		{ 11, 1, 1, 1, 22, 1, 1, 1, 22, 1, 1, 1, 22, 1, 1, 1, 12 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 21, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 23 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 21, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 23 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 21, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 23 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2, 5, 4, 4, 2 },
		{ 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2 },
		{ 14, 1, 1, 1, 24, 1, 1, 1, 24, 1, 1, 1, 24, 1, 1, 1, 13 }
	};
	int i, j;
	for (i = 0; i < 17; i++)
	for (j = 0; j < 17; j++)
		map[i][j] = arr_temp[i][j];
}
 
//맵을 프린트함
void game_print(int map[][17]){
	int i = 0, j = 0;
	printf("\n    score : %d\n\n", 100);
	for (int i = 0; i < 17; i++){
		printf("      ");
		for (int j = 0; j < 17; j++){
			switch (map[i][j]) {
			case 0: printf("  "); break;
			case 1: printf("─"); break;
			case 2: printf("│"); break;
			case 3: printf("┼"); break;
			case 5: printf("      ");break;
			case 11: printf("┌"); break;
			case 12: printf("┐"); break;
			case 13: printf("┘"); break;
			case 14: printf("└"); break;
			case 21: printf("├"); break;
			case 22: printf("┬"); break;
			case 23: printf("┤"); break;
			case 24: printf("┴"); break;
			}
		}
		printf("\n");
	}
}
 
//숫자를 프린트함
 void number_print(int arr[][4], int score){
	 int i,j;
	 gotoxy(6, 1);
	 printf("%d", score);
 
	 for(i=0;i<4;i++){
		 for(j=0;j<4;j++){
			gotoxy(4+j*4, 6+i*4);
			if (arr[i][j] != 0) {
				printf("%5d ", arr[i][j]);
			}
			else {
			printf("      ");
			}
		 }
	 }
 }
 
//새로운 숫자 생성
void create(int arr[][4]) {
	int locate, number;
	srand(unsigned(time(NULL)));//rand함수 랜덤설정
	if (rand() % 10 < 8) number = 2;//80퍼로 2생성
	else number = 4;// 20퍼로 4생성
	do{
		locate = rand() % 16;
	} while (arr[locate / 4][locate % 4] != 0);//빈칸나올때까직 랜덤
	arr[locate / 4][locate % 4] = number;
}
 
//create가 가능한지 체크
int create_check(int arr[][4]) {
	int i, cnt = 0;
	for (i = 0; i < 16; i++) {
		if (arr[i / 4][i % 4] != 0)
			cnt++;
	}
	if (cnt == 16) return 0;//배열이 꽉참 -> create불가
	else return 1;//creeate가능
}
 
//방향키이동
int dmove(int arr[][4], int d, int *score){
	int i,j, s, check = 0;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 4; j++) {
			if (*arr_tc(arr, i, j, d) != 0) {
				for (s = j + 1; s < 4; s++) {//뒤와 합치기
					if (*arr_tc(arr, i, j, d) == *arr_tc(arr, i, s, d)) {
						*arr_tc(arr, i, j, d) *= 2;//
						*arr_tc(arr, i, s, d) = 0;
						*score += *arr_tc(arr, i, j, d);//점수 추가
						check++;
						break; 
					}
					else if (*arr_tc(arr, i, s, d) != 0) break;//뒤에 합치지 못하면 종료
				}
 
 
				for (s = j - 1; s >= 0; s--) {//앞에 이동할수 있나 체크
					if (*arr_tc(arr, i, s, d) != 0) {
						break;
					}
				}
				s++;
				if (j != s) {//앞에 이동할수 있으면 정렬
					*arr_tc(arr, i, s, d) = *arr_tc(arr, i, j, d);
					*arr_tc(arr, i, j, d) = 0;
					check++;
				}
			}
 
		}
	}
	// check == 0 -> 더 이상 움직일 수 없음 -> create 안함
	if (create_check(arr)) {
		if (check != 0) {
			create(arr);
		}
	}
	else//더이상 create 불가 시
	{
		game_over(score); 
		return 1;//다시시작
	}
	return 0;
}
 
//배열을 돌림 -> 방향키가 달라도 같은 코드로 조작 가능
int *arr_tc(int arr[][4], int i, int j, int d){
	int ti, tj;
	switch (d) {
	case 1: ti = i; tj = j;   break;
	case 2: ti = j; tj = 3 - i; break;
	case 3: ti = i; tj = 3 - j; break;
	case 4: ti = 3 - j; tj = 3 - i; break;
	}
	return &arr[ti][tj];
}
 
//게임 오버
void game_over(int *score) {
	system("cls");
	gotoxy(10, 5); printf("Game Over");
	gotoxy(10, 6); printf("Score : %d", *score);
	gotoxy(12, 7); printf("PRESS ANY KEY");
	getch();
	getch();
}



WRITTEN BY
Who1sth1s

,

-스택 리스트





-결과






WRITTEN BY
Who1sth1s

,

1. 연결리스트(Linked List)란?


 연결 리스트의 사전적 의미는

연결 리스트링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 연결리스트란 각 노드에 데이터와 링크를 가지고 마치 비엔나 소세지 처럼 한줄로 연결되어 있는 데이터 저장 방식이다.




2. 연결리스트의 쓰임(용도)


배열과 연결리스트의 차이점

-배열의 특성은 메모리공간에서 연속이라는 점이다. 그래서 첨자연산으로 빠른 속도가 보장되지만, 메모리가 연속이어야하기 때문에, 삽입과 삭제가 번거롭다. 하지만 연결리스트는 메모리상에 연속이지 않아도 된다. 왜냐하면 다음데이터에 대한 링크정보를 지니고 있기 때문이다.


연결리스트의 장점과 단점

-장점 : 배열과는 다르게 맨처음 선언시 데이터의 길이를 몰라도 사용이 가능하고 노드(자료)의 추가, 삽입, 삭제가 매우 용이하다. 노드가 추가될 때 마다 메모리 동적할당을 함으로써 메모리공간을 낭비하지 않는다.


-단점 : 배열과 달리 각 노드에 Index가 주어지지 않아서 탐색할때 처음(head)부터 탐색해야 됨으로 속도가 느리다. 따라서 특정 위치의 요소접근이 힘들다.


용도(사용처)

-조회는 드물고 추가, 삽입, 삭제가 잦은곳에서 자주 사용 된다.

ex) 반 아이들의 정보를 출석번호로 나열(추가, 삭제)




3. 연결리스트의 구조 및 구현


-구조





[그림 7-12] 연결 리스트의 예

[네이버 지식백과]연결 리스트 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))



-구현예제




-결과




+) 스택 리스트





-결과






WRITTEN BY
Who1sth1s

,

ㅇㅇㅇㅇㅇ


WRITTEN BY
Who1sth1s

,

1. 구조체란?


 구조체란 연관성이 있는 서로 다른 자료형을 하나의 집합으로 묶어 새롭게 정의한 사용자 정의 료형이다. 


2. 구조체는 언제, 왜 필요할까?

  구조체는 성적 자료와 같이 학번, 이름, 점수 등 과 같이 다른 자료형을 하나의 집합으로 만드는 상황에서 매우 유용하다. 구조체를 사용하지 않는다면 다음과 같이 선언 하게 된다 


int hakbun;

char  name[10];

int   kor, eng, mat, total;

float  avg;


위와 같이 선언 할텐데 막약에 학생이 1명이 아니라 여러명일 경우 어떻게 선언해야 할까? 


int hakbun1;

char  name1[10];

int   kor1, eng1;


int hakbun2;

char  name2[10];

int   kor2, eng2;


물론 위와 같이 선언할 수도 있다 하지만 너무 비효율적이지 않은가 하지만 구조체를 사용하면 굉장히 실플하고 간단하게 선언해줄 수있다.


3. 구조체의 사용방법


-구조체의 형식은 다음과같다.


struct  구조체이름{     

    자료형  멤버명_1;

    자료형  멤버명_2;

     

    자료형  멤버명_n;

}; //구조체선언에서는 마지막에 꼭 세미콜론(;)을 써야한다.



-위를 참고해서 성적자료를 선언하면 다음과 같다.


struct   sungjuk{

       int hakbun;

      char  name[10];

       int   kor, eng;

};





-그렇다면 구조체를 선언했으니 구조체 변수선언 방법을 알아보자.


형식

struct   구조체이름  변수명_1, 변수명_2, …;

     또는

struct  구조체이름{     

    자료형  멤버명_n;

}변수명_1, 변수명_2; 


성적자료 선언

struct   sungjuk  student1, student2, …;

    또는

struct  sungjuk{     

    자료형  멤버명_n;

}student1, student2; 



-이제 구조체변수 선언도 했으니 구조체를 초기화 해보자

구조체변수의 멤버 값을 참조할때는 ' . ' 점을 사용한다.


student1.hakbun = 1;

student1.name= "홍길동";

student1.kor = 92;

student1.eng = 96;


student2.hakbun = 2;

student2.name= "심청이";

student2.kor = 75;

student2.eng = 100;


또는

struct  sungjuk  student1={1, "홍길동", 92, 96};

struct  sungjuk  student2={2, "심청이", 75, 100};

또는

struct  sungjuk  student[2]={{1, "홍길동", 92, 96},

  {2, "심청이", 75, 100}};


-위 예제를 간단하게 합치면 다음과 같다.

struct   sungjuk{

       int hakbun;

      char  name[10];

       int   koreng;

}student1={1, "홍길동", 92, 96}, student2={2, "심청이", 75, 100};






WRITTEN BY
Who1sth1s

,

함수호출-값에 의한 호출(Call-by-Value)


 일반적인 함수호출의 예를들면 다음과 같다.

  결과 : 


 input1과 input2를 add함수의 a, b에 전달하고 실행시키는 과정을 함수의 호출이라고 한다. 

 위와같이 그냥 input이라는 값만 함수에 전달하는 방법을 값에 의한 호출(Call-by-Value)라고 한다.

값에 의한 호출(Call-by-Value)이라는 호출방식은 일반적으로 쓰인다. 하지만 다음과 같은 소스에서는 적합하지 않다.


-값에 의한 호출(Call-by-Value)의 한계

  결과 : 


위 소스는 print할때 input의 값을 서로 바꾸어 출력하기 위해 만든 소스이다. 하지만 결과 값은 이상하게도 input이 서로 바뀌지 않았다.

그 이유는 당연하다. 왜냐하면 input의 값만 함수에 전달했기 때문에 실제 input의 값이 바뀌는 것이 아니고 change라는 함수안의 input의 값만 바뀌었기 때문이다. 따라서 이런 경우에 원하는 대로 출력을 시킬려면 값에 의한 호출(Call-by-Reference) 이라는 방법을 사용해야 한다.

이 방법을 써서 다시 소스를 고쳐짜면 다음과 같다.



함수호출-참조에 의한 호출(Call-by-Reference)


 결과 : 


빨간색 밑줄친 부분을 추가했더니 원하는 대로 값이 서로 바뀌어 나오는 것을 볼 수가 있다.

 위에 추가한 빨간색 밑줄을 설명하자면 함수를 호출할때 input이라는 값만 주는것이 아니라 input자체의 주소를 전달함으로서 input의 실제 값을 참조할 수 있게 되는 것이다.

 다시 말하자면 change라는 함수를 호출할때 input의 주소값을 전달하고 change함수에서 전달받은 주소값 앞에다가 *(포인터)를 붙임으로서 input의 실제 값을 참조할 수 있게 되는 것이다.

이와 같은 방법을 값에 의한 호출, 즉 Call-by-Reference라고 불린다. 




소스




WRITTEN BY
Who1sth1s

,