Least Recently Used

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <list>
using namespace std;

int main() {
list<int> cache;
int item;
int cacheSize = 3; //Cache Size
int count = 0; //Cache Miss 횟수
while(true){
cin >> item;
if(cin.fail()) break;
cache.remove(item);
if(cache.size() < cacheSize) cache.push_back(item);
else{
cout << cache.front() << endl; //교체가 일어난 item 출력
cache.pop_front();
cache.push_back(item);
cache++;
}
}
if(count == 0) cout << 0 << endl; //Cache Miss가 0이면 0 출력
return 0;
}

ListContainer

list의 사용

#include<list>
list<[Data Type]> [변수 이름];

  • 예시) list<int> lt1; list<string> lt2;

list 반복자

list<[Data Type]>::iterator [변수 이름];

list 생성자

1
2
3
4
5
6
7
list lt;		//비어있는 list컨테이너 lt를 생성합니다.

list lt(10); //default(0)값으로 초기화 된 원소 10개를 가진 list를 생성합니다.

list lt(3, 2); //2값으로 초기화 된 원소 3개를 가진 list를 생성합니다.

list lt2(lt1); //list lt1을 lt2로 복사합니다.

list의 멤버 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
lt.assign(3, 4);	//4로 초기화된 3개의 원소를 할당한다.

lt.front(); //맨 앞의 원소를 반환(return), 참조 합니다.

lt.back(); //맨 뒤의 원소를 반환(return), 참조 합니다.

lt.begin(); //맨 앞의 원소를 가리키는 iterator를 반환합니다.

lt.end(); //맨 마지막의 다음 원소를 가리키는 iterator를 반환합니다.

lt.rbegin(); //뒤에서부터 원소를 순차적으로 접근할때 편리하게 쓰입니다.

lt.rend(); //뒤에서부터 원소를 순차적으로 접근할때 편리하게 쓰입니다.

lt.push_back(k); //뒤쪽으로 원소 k 를 삽입합니다.

lt.push_front(k); //앞쪽으로 원소 k 를 삽입합니다.

lt.pop_back(); //맨 마지막 원소를 제거합니다.

lt.pop_front(); //맨 첫번째 원소를 제거합니다.

lt.insert(iter, k); //iter가 가리키는 위치에 원소 k를 삽입합니다. 삽입한 원소를 가리키는 iterator를
반환합니다.

lt.erase(iter); //iterator가 가리키는 원소를 삭제합니다.반환값은 삭제한 원소의 다음 원소를 가리키는 iterator를 반환합니다.

lt.size(); //원소의 개수를 반환합니다.

lt.remove(k); //k와 같은 원소를 모두 제거합니다.

lt.remove_if(Predicate); //단항 조건자 predicate에 해당하는 원소를 모두 제거합니다.
bool predicate(int num){
return num>=100 && num<=200;
}

lt.reverse(); //원소들의 순차열을 뒤집습니다.

lt.sort(); //모든 원소를 default(오름차순)으로 정렬합니다.

lt.sort(greater<[Data Type]>()); //모든 원소를 내림차순으로 정렬합니다.

lt2.swap(lt1); //lt2와 lt1을 swap(바꿉)니다.

lt2.splice(iter2, lt1); //lt2에서 iter2이 가리키는 곳에 lt1의 모든 원소를 잘라 붙입니다.

lt2.splice(iter2, lt1, iter1); //lt2의 iter2가 가리키는 곳에 lt1의 iter1이 가리키는 원소를 잘라 붙입
니다.

lt2.splice(iter2, lt1, iter1_1, iter1_2); // lt2의 iter2가 가리키는 곳에 lt1의 [iter1_1 , iter1_2) 까지의 원소를 잘라 붙입니다.

lt.unique(); //인접한(양옆의) 원소가 같으면 유일하게 만듭니다.(하나만빼고 삭제)

lt2.merge(lt1);
//lt1을 lt2내부로 합병 정렬합니다. 기준은 default 오름차순 입니다.
//두번째 파라미터로 이항 조건자가 올 수 있습니다. 그때는 그 기준으로 정렬합니다.

constexpr

constexpr

constexpr은 C++11부터 지원하며, Visual Studio 2015부터 사용할 수 있다.

이번에 프로젝트 시연을 하는데, 내 개발환경은 2015 였고, 실습실은 2012 라서 시연을 못했다.

실행파일이라도 가져갔어야 했는데 멍청했다.

그리고 난 망했다..ㅜㅜ

사용법은 여기를 참고하자.

그리고 호환성 부분도 살펴보자.

(개인 프로젝트) CUDA를 이용해서 멀티 스레드로 작동하는 Image Filter 프로그램

소개

  • 인원 : 1인
  • 담당 : 프로그램 구현 전체
  • 개발 환경 : Visual Studio 2015, CUDA 9.0
  • 문제
    • Input
      • Data : 비트맵 이미지의 R, G, B 값
      • 화면 입력 : 불러올 이미지 파일 이름, 적용 필터
    • Output
      • 화면 출력 : 필터 적용에 걸린 시간, 저장된 파일 이름
      • 파일 출력 : 필터가 적용된 이미지
  • 소스코드 : CUDA를 이용해서 멀티 스레드로 작동하는 Image Filter 프로그램

내용

1. 전부 다 늘릴 때와 각각을 늘릴 때의 차이

두 필터는 RGB에 일정 비율을 곱했다는 공통점이 있습니다. 이 중에 밝기 필터는 단순하게 모든 픽셀의 RGB값을 일정 비율만큼 더하면 되지만, 저희가 만든 필터는 채도를 올리는 방식이라서 붉은 계열 색상이라면 더 붉게 만들고, 푸른 계열 색상이라면 더 푸르게 만들어야 합니다.

2. 적용 방법

RGB 값을 비교하고, 가장 많이 쓰인 색을 높이는 방식으로 필터를 구현했습니다.

3. 병렬화 부분

그리드와 블록은 단순하게 설계하였습니다, 먼저 총 픽셀 수를 구하고, 블록 당 스레드 수를 지정하게 됩니다. 그리고 각 스레드는 한 픽셀 씩 맡아서 RGB값을 처리하게 됩니다. 이렇게 스레드가 한 픽셀을 맡게 되면 동기화 문제는 해결됩니다.

5. 결과 분석 (Intel i7-7700 & GTX 1070 기준)
실행화면
실행결과
결과차트
각 필터 마다 CPU 시간을 GPU 시간으로 나누어서 계산한 차트입니다.
평균적으로 10배 이상의 성능 향상을 보이고, 그레이 필터는 다른 필터보다 더 빠른 23배 정도의 성능향상이 있었습니다.
아무래도 CPU나 GPU 둘 다 높은 성능 이라서 큰 차이가 보이지 않는 것 같습니다.

어려웠던 점


무작정 큰 값만 늘리다보니 문제가 발생했습니다. 이 주변은 하늘이라서 주로 파란색 값이 크지만, 이 부분은 구름과 겹쳐서 파란색보다 녹색이 더 많았습니다. 그래서 이 픽셀만 녹색이 더 증가하는 문제가 생기게 된다는 사실을 알았습니다.

이 문제를 해결하기 위해 허용 범위를 지정하였습니다. RGB 값의 차이가 일정 범위 이내라면 비슷한 값들을 한 번에 증가시켰습니다. 이렇게 증가시켰더니 이전 사진에서 구름 일부가 녹색으로 바뀌던 문제를 해결할 수 있었습니다.

배운 점

이전에 OpenMP만 사용할 때에는 CPU만 사용했기 때문에 스레드가 많아야 겨우 8개 정도였지만, 이번에는 그래픽 카드를 이용했기 때문에 훨씬 많은 수의 스레드를 생성하고 제어하였습니다. 이 프로젝트에서는 사진 파일이 가진 픽셀 수 만큼 스레드를 생성하였는데, 1024 X 1024의 사이즈를 가진 사진이라면 100만개 이상의 스레드를 생성하게 됩니다. 너무 많은 수의 스레드를 생성하다보니 이를 제어하는 것이 처음에는 어려웠지만, 점점 익숙해져서 잘 다룰 수 있게 되었습니다.

Linux에 C로 FTP Server와 Client 작성하기

FTP Server

컴파일 및 실행 방법

1
2
$ gcc -o server server.c
$ ./server 9999

server.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/socket.h>
#include <sys/sendfile.h>
#include <netinet/in.h>
#include <fcntl.h>

int tcp_listen(int host, int port, int backlog) {
int sd;
struct sockaddr_in servaddr;

sd = socket(AF_INET, SOCK_STREAM, 0);
if (sd == -1) {
perror("socket fail");
exit(1);
}
// servaddr 구조체의 내용 세팅
bzero((char *)&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(host);
servaddr.sin_port = htons(port);
if (bind(sd, (struct sockaddr *)&servaddr, sizeof(servaddr)) < 0) {
perror("bind fail"); exit(1);
}
// 클라이언트로부터 연결요청을 기다림
listen(sd, backlog);
return sd;
}

int main(int argc, char *argv[])
{
struct sockaddr_in server, client;
struct stat obj;
int sock1, sock2;
char buf[100], command[5], filename[20];
int k, i, size, len, c;
int filehandle;

sock1 = tcp_listen(INADDR_ANY, atoi(argv[1]), 5);

len = sizeof(client);
sock2 = accept(sock1, (struct sockaddr*)&client, &len);
while (1) {
recv(sock2, buf, 100, 0);
sscanf(buf, "%s", command);
if (!strcmp(command, "ls")) {//ls명령어를 입력받았다면
system("ls >temps.txt");
stat("temps.txt", &obj);
size = obj.st_size;
send(sock2, &size, sizeof(int), 0);
filehandle = open("temps.txt", O_RDONLY);
sendfile(sock2, filehandle, NULL, size);
}
else if (!strcmp(command, "get")) {//get명령어를 입력받았다면
sscanf(buf, "%s%s", filename, filename);
stat(filename, &obj);
filehandle = open(filename, O_RDONLY);
size = obj.st_size;
if (filehandle == -1)
size = 0;
send(sock2, &size, sizeof(int), 0);
if (size)
sendfile(sock2, filehandle, NULL, size);

}
else if (!strcmp(command, "put")) {//put명령어를 입력받았다면
int c = 0, len;
char *f;
sscanf(buf + strlen(command), "%s", filename);
recv(sock2, &size, sizeof(int), 0);

while (1) {
filehandle = open(filename, O_CREAT | O_EXCL | O_WRONLY, 0666);
if (filehandle == -1)
sprintf(filename + strlen(filename), "_1");
else break;
}
f = malloc(size);
recv(sock2, f, size, 0);
c = write(filehandle, f, size);
close(filehandle);
send(sock2, &c, sizeof(int), 0);
}
else if (!strcmp(command, "pwd")) {//pwd명령어를 입력받았다면
system("pwd>temp.txt");
i = 0;
FILE*f = fopen("temp.txt", "r");
while (!feof(f)) buf[i++] = fgetc(f);
buf[i - 1] = '\0';
fclose(f);
send(sock2, buf, 100, 0);
}
else if (!strcmp(command, "cd")) {//cd명령어를 입력받았다면
if (chdir(buf + 3) == 0) c = 1;
else c = 0;
send(sock2, &c, sizeof(int), 0);
}
else if (!strcmp(command, "bye") || !strcmp(command, "quit")) {
//종료 명령어를 입력받았다면
printf("FTP server quitting..\n");
i = 1;
send(sock2, &i, sizeof(int), 0);
exit(0);
}
}
return 0;
}

FTP Client

컴파일 및 실행 방법

1
2
$ gcc -o client client.c
$ ./client 127.0.0.1 9999

client.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/socket.h>
#include <sys/sendfile.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <fcntl.h>

#define MAXLINE 511

int tcp_connect(int af, char *servip, unsigned short port) {
struct sockaddr_in servaddr;
int s;
// 소켓 생성
if ((s = socket(af, SOCK_STREAM, 0)) < 0)
return -1;
// 채팅 서버의 소켓주소 구조체 servaddr 초기화
bzero((char *)&servaddr, sizeof(servaddr));
servaddr.sin_family = af;
inet_pton(AF_INET, servip, &servaddr.sin_addr);
servaddr.sin_port = htons(port);

// 연결요청
if (connect(s, (struct sockaddr *)&servaddr, sizeof(servaddr))
< 0)
return -1;
return s;
}

int main(int argc, char *argv[])
{
struct sockaddr_in server;
struct stat obj;
int sock;
char bufmsg[MAXLINE];
char buf[100], command[5], filename[MAXLINE], *f;
char temp[20];
int k, size, status;
int filehandle;

if (argc != 3) {
printf("사용법 : %s server_ip port\n", argv[0]);
exit(1);
}

sock = tcp_connect(AF_INET, argv[1], atoi(argv[2]));
if (sock == -1) {
printf("tcp_connect fail");
exit(1);
}

while (1) {
printf("\033[1;33m명령어 : get, put, pwd, ls, cd, quit\n");
printf("\033[1;32mclient> ");
fgets(bufmsg, MAXLINE, stdin); //명령어 입력
fprintf(stderr, "\033[97m"); //글자색을 흰색으로 변경
if (!strcmp(bufmsg, "get\n")) {//get명령어를 입력받았다면
printf("다운로드할 파일 : ");
scanf("%s", filename); //파일 이름 입력
fgets(temp, MAXLINE, stdin); //버퍼에 남은 엔터 제거
strcpy(buf, "get ");
strcat(buf, filename);
send(sock, buf, 100, 0); //명령어 전송
recv(sock, &size, sizeof(int), 0);
if (!size) {//파일이 없다면
printf("파일이 없습니다\n");
continue;
}
f = malloc(size);
recv(sock, f, size, 0);
while (1) {
filehandle = open(filename, O_CREAT | O_EXCL | O_WRONLY, 0666);
if (filehandle == -1) //같은 이름이 있다면 이름 끝에 _1 추가
sprintf(filename + strlen(filename), "_1");
else break;
}
write(filehandle, f, size, 0);
close(filehandle);
printf("다운로드 완료\n");//전송이 잘 되었다면
}
else if (!strcmp(bufmsg, "put\n")) {//put명령어를 입력받았다면
printf("업로드할 파일 : ");
scanf("%s", filename); //파일 이름 입력
fgets(temp, MAXLINE, stdin); //버퍼에 남은 엔터 제거
filehandle = open(filename, O_RDONLY);
if (filehandle == -1) {//파일이 없다면
printf("파일이 없습니다.\n");
continue;
}
strcpy(buf, "put ");
strcat(buf, filename);
send(sock, buf, 100, 0);
stat(filename, &obj);
size = obj.st_size;
send(sock, &size, sizeof(int), 0);//명령어 전송
sendfile(sock, filehandle, NULL, size);//파일 전송
recv(sock, &status, sizeof(int), 0);
if (status)//업로드가 잘 되었다면
printf("업로드 완료\n");
else
printf("업로드 실패\n");
}
else if (!strcmp(bufmsg, "pwd\n")) {//pwd명령어를 입력받았다면
strcpy(buf, "pwd");
send(sock, buf, 100, 0);
recv(sock, buf, 100, 0);
printf("--The path of the Remote Directory--\n%s", buf);
}
else if (!strcmp(bufmsg, "ls\n")) {//ls명령어를 입력받았다면
strcpy(buf, "ls");
send(sock, buf, 100, 0);
recv(sock, &size, sizeof(int), 0);
f = malloc(size);
recv(sock, f, size, 0);
filehandle = creat("temp.txt", O_WRONLY);
write(filehandle, f, size, 0);
close(filehandle);
printf("--The Remote Directory List--\n");
system("cat temp.txt"); //현재 디렉토리의 파일 출력
}
else if (!strcmp(bufmsg, "cd\n")) {//cd명령어를 입력받았다면
strcpy(buf, "cd ");
printf("이동할 경로 이름 : ");
scanf("%s", buf + 3); //위치 입력
fgets(temp, MAXLINE, stdin); //버퍼에 남은 엔터 제거
send(sock, buf, 100, 0); //명령어 전송
recv(sock, &status, sizeof(int), 0);
if (status)
printf("경로 변경 완료\n");
else
printf("경로 변경 실패\n");
}
else if (!strcmp(bufmsg, "quit\n")) {//quit명령어를 입력받았다면
strcpy(buf, "quit");
send(sock, buf, 100, 0);
recv(sock, &status, 100, 0);
if (status) {
printf("서버를 닫는 중..\n");
exit(0);
}
printf("서버 닫기 실패\n");
}
}
}

(개인 프로젝트) 파일 전송 서버와 클라이언트 제작

소개

  • 인원 : 1인
  • 담당 : 프로그램 구현 전체
  • 개발 환경 : Ubuntu 16.04 LTS, VMware Workstation 14 Player
  • 문제
    • 파일 전송 서버는 서버에서 실행중이며 클라이언트가 전달해주는 내용을 파일로 저장하고 보내주는 역할을 한다.
    • 파일 전송 클라이언트는 서버에 전송할 파일을 선택하여 전송하고, 서버에서 선택한 파일을 전송받아 저장하는 기능을 수행한다. (get : 다운로드 명령, put : 업로드 명령)
    • 클라이언트는 접속한 디렉토리에 대해서 파일을 업로드, 다운로드 하도록 함.
    • 서버에 전송한 파일을 저장하는 디렉토리는 서버 프로세스가 실행되는 곳으로 함.
    • 다운로드할 수 있는 파일은 전체 디렉토리를 대상으로 가능함.
      (퍼미션을 고려하여 다운로드 가능한 파일)
    • text 파일, binary 파일 모두 전송이 가능하도록 함.
  • 소스코드 : Linux에 C로 FTP Server와 Client 작성하기
  • 사용법 : Linux에 C로 FTP Server와 Client 작성하기

내용

컴퓨터의 수가 부족하여 부득이하게 로컬에서 서버와 클라이언트를 함께 실행하였습니다.


이 중에 위에 있는 터미널은 서버, 아래에 있는 터미널은 클라이언트 입니다.
클라이언트는 6가지의 명령을 사용할 수 있습니다.

  • get : 서버에서 파일 다운로드
  • put : 서버로 파일 업로드
  • pwd : 현재 디렉토리 위치
  • ls : 현재 디렉토리의 파일 목록
  • cd : 디렉토리 이동
  • quit : 접속 해제

어려웠던 점

평소에는 터미널에서 고작 문자나 주고받는 소켓프로그래밍을 하였지만, 이번에 파일을 통째로 전송해야해서 처음에 어떻게 구현을 해야할지 막막했습니다. 그래서 다른 사람의 소스코드를 참고해가면서, 파일 사이즈를 먼저 전송하고 그 이후에 파일을 전송하는 방식으로 문제를 해결했습니다.

배운 점

TCP 부분을 응용해서 구현해야하는 프로젝트였습니다. 처음에는 이 문제를 어떻게 해결해야 할지 고민이 많았지만 하나씩 차근차근 해결해나가다 보니 프로그램이 완성되어 있는 것을 볼 수 있었습니다.
기본적인 기능 구현 이외에 사용자 편의성을 높이기 위해서 더욱 직관적인 사용법을 도입하였고, 색을 통한 구분으로 가독성이 뛰어나도록 더욱 깔끔한 출력을 하기 위해서 많은 시간을 투자하였습니다. 이를 통해 사용자는 보다 편리한 사용이 가능하고, 손쉽게 파일을 주고받을 수 있습니다.
이렇게 사용자를 배려한 프로그램을 구현하다보니 평소에 습득하지 못했던 지식을 더욱 알아갈 수 있는 계기가 되었고, 실력향상에 많은 도움이 되었던 것 같습니다.

Typora

이 블로그를 작성할 때에는 Markdown 언어를 사용해야 한다.
Markdown 문서를 쉽게 작성할 수 있는 툴로 Typora가 있다.
변환된 모양을 바로 볼 수 있어서 편리하다.

CUDA_INDEX

1D grid of 1D blocks

1
2
3
4
__device__
int getGlobalIdx_1D_1D(){
return blockId.x * blockDim.x + threadIdx.x;
}

1D grid of 2D blocks

1
2
3
4
5
__device__
int getGlobalIdx_1D_2D(){
return blockIdx.x * blockDim.x * blockDim.y
+ threadIdx.y * blockDim.x + threadIdx.x;
}

1D grid of 3D blocks

1
2
3
4
5
6
__device__
int getGlobalIdx_1D_3D(){
return blockIdx.x * blockDim.x * blockDim.y * blockDim.z
+ threadIdx.z * blockDim.y * blockDim.x
+ threadIdx.y * blockDim.x + threadIdx.x;
}

2D grid of 1D blocks

1
2
3
4
5
__device__ int getGlobalIdx_2D_1D(){
int blockId = blockIdx.y * gridDim.x + blockIdx.x;
int threadId = blockId * blockDim.x + threadIdx.x;
return threadId;
}

2D grid of 2D blocks

1
2
3
4
5
6
7
__device__
int getGlobalIdx_2D_2D(){
int blockId = blockIdx.x + blockIdx.y * gridDim.x;
int threadId = blockId * (blockDim.x * blockDim.y)
+ (threadIdx.y * blockDim.x) + threadIdx.x;
return threadId;
}

2D grid of 3D blocks

1
2
3
4
5
6
7
8
__device__
int getGlobalIdx_2D_3D(){
int blockId = blockIdx.x + blockIdx.y * gridDim.x;
int threadId = blockId * (blockDim.x * blockDim.y * blockDim.z)
+ (threadIdx.z * (blockDim.x * blockDim.y))
+ (threadIdx.y * blockDim.x) + threadIdx.x;
return threadId;
}

3D grid of 1D blocks

1
2
3
4
5
6
7
__device__
int getGlobalIdx_3D_1D(){
int blockId = blockIdx.x + blockIdx.y * gridDim.x
+ gridDim.x * gridDim.y * blockIdx.z;
int threadId = blockId * blockDim.x + threadIdx.x;
return threadId;
}

3D grid of 2D blocks

1
2
3
4
5
6
7
8
__device__
int getGlobalIdx_3D_2D(){
int blockId = blockIdx.x + blockIdx.y * gridDim.x
+ gridDim.x * gridDim.y * blockIdx.z;
int threadId = blockId * (blockDim.x * blockDim.y)
+ (threadIdx.y * blockDim.x) + threadIdx.x;
return threadId;
}

3D grid of 3D blocks

1
2
3
4
5
6
7
8
9
__device__
int getGlobalIdx_3D_3D(){
int blockId = blockIdx.x + blockIdx.y * gridDim.x
+ gridDim.x * gridDim.y * blockIdx.z;
int threadId = blockId * (blockDim.x * blockDim.y * blockDim.z)
+ (threadIdx.z * (blockDim.x * blockDim.y))
+ (threadIdx.y * blockDim.x) + threadIdx.x;
return threadId;
}

(개인 프로젝트) Python을 이용한 팩맨 프로젝트 중 Search와 Multiagent Search 구현

소개

내용

1. Search

위에 보이는 것처럼 미로에서 팩맨이 어떻게 하면 최단거리로 먹이를 찾을 수 있을 지에 대한 것을 구현한 것입니다. 이를 구현하기 위해서 DFS, BFS, UCS, A* 알고리즘을 사용하였고, 각 알고리즘을 서로 비교해보았습니다.

2. Multiagent Search

위에 보이는 것처럼 팩맨은 유령을 피하면서 먹이를 먹는 여러 대상을 고려한 알고리즘을 구현하였습니다. 이를 구현하기 위해서 minimax, Alpha-Beta Pruning, Expectimax 를 사용하였습니다.

어려웠던 점

인공지능을 공부하면서 파이썬을 처음으로 접하게 되었는데, 평소에 사용하던 언어와 다르게 스크립트 기반의 언어라서 어색했습니다. 그래도 이 프로젝트를 진행한 덕분에 파이썬을 더욱 잘 다룰 수 있게 되었습니다.

배운 점

이론적으로만 알고 있던 알고리즘들을 직접 구현해보니 상황에 따라 어떤 알고리즘을 사용해야하는 지 장단점을 직접 볼 수 있어서 도움이 많이 되었습니다. 이전에 알고리즘 과목을 수강했을 때에는 단일 대상으로부터의 검색 알고리즘 만을 배웠었지만, 이번에는 여러 대상이 있을 때에도 사용 가능한 검색 알고리즘을 익히게 되어서 더욱 다양한 환경에도 적용할 수 있게 되었습니다.

Linux에서 Socket으로 채팅구현하기

서버를 구동시킨 후 클라이언트를 실행합니다.
클라이언트는 2개 이상 실행이 가능하며 단체 대화방 처럼 사용이 가능합니다.
서버에서 지원하는 명령어는 아래와 같습니다.
help num_user num_chat ip_list

Server

컴파일 및 실행 방법

1
2
$ gcc -o server server.c -lpthread
$ ./server 9999

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <fcntl.h>
#include <sys/socket.h>
#include <sys/file.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <time.h>
#include <pthread.h>

#define MAXLINE 511
#define MAX_SOCK 1024 // 솔라리스의 경우 64

char *EXIT_STRING = "exit"; // 클라이언트의 종료요청 문자열
char *START_STRING = "Connected to chat_server \n";
// 클라이언트 환영 메시지
int maxfdp1; // 최대 소켓번호 +1
int num_user = 0; // 채팅 참가자 수
int num_chat = 0; // 지금까지 오간 대화의 수
int clisock_list[MAX_SOCK]; // 채팅에 참가자 소켓번호 목록
char ip_list[MAX_SOCK][20]; //접속한 ip목록
int listen_sock; // 서버의 리슨 소켓

// 새로운 채팅 참가자 처리
void addClient(int s, struct sockaddr_in *newcliaddr);
int getmax(); // 최대 소켓 번호 찾기
void removeClient(int s); // 채팅 탈퇴 처리 함수
int tcp_listen(int host, int port, int backlog); // 소켓 생성 및 listen
void errquit(char *mesg) { perror(mesg); exit(1); }

time_t ct;
struct tm tm;

void *thread_function(void *arg) { //명령어를 처리할 스레드
int i;
printf("명령어 목록 : help, num_user, num_chat, ip_list\n");
while (1) {
char bufmsg[MAXLINE + 1];
fprintf(stderr, "\033[1;32m"); //글자색을 녹색으로 변경
printf("server>"); //커서 출력
fgets(bufmsg, MAXLINE, stdin); //명령어 입력
if (!strcmp(bufmsg, "\n")) continue; //엔터 무시
else if (!strcmp(bufmsg, "help\n")) //명령어 처리
printf("help, num_user, num_chat, ip_list\n");
else if (!strcmp(bufmsg, "num_user\n"))//명령어 처리
printf("현재 참가자 수 = %d\n", num_user);
else if (!strcmp(bufmsg, "num_chat\n"))//명령어 처리
printf("지금까지 오간 대화의 수 = %d\n", num_chat);
else if (!strcmp(bufmsg, "ip_list\n")) //명령어 처리
for (i = 0; i < num_user; i++)
printf("%s\n", ip_list[i]);
else //예외 처리
printf("해당 명령어가 없습니다.help를 참조하세요.\n");
}
}

int main(int argc, char *argv[]) {
struct sockaddr_in cliaddr;
char buf[MAXLINE + 1]; //클라이언트에서 받은 메시지
int i, j, nbyte, accp_sock, addrlen = sizeof(struct
sockaddr_in);
fd_set read_fds; //읽기를 감지할 fd_set 구조체
pthread_t a_thread;

if (argc != 2) {
printf("사용법 :%s port\n", argv[0]);
exit(0);
}

// tcp_listen(host, port, backlog) 함수 호출
listen_sock = tcp_listen(INADDR_ANY, atoi(argv[1]), 5);
//스레드 생성
pthread_create(&a_thread, NULL, thread_function, (void *)NULL);
while (1) {
FD_ZERO(&read_fds);
FD_SET(listen_sock, &read_fds);
for (i = 0; i < num_user; i++)
FD_SET(clisock_list[i], &read_fds);

maxfdp1 = getmax() + 1; // maxfdp1 재 계산
if (select(maxfdp1, &read_fds, NULL, NULL, NULL) < 0)
errquit("select fail");

if (FD_ISSET(listen_sock, &read_fds)) {
accp_sock = accept(listen_sock,
(struct sockaddr*)&cliaddr, &addrlen);
if (accp_sock == -1) errquit("accept fail");
addClient(accp_sock, &cliaddr);
send(accp_sock, START_STRING, strlen(START_STRING), 0);
ct = time(NULL); //현재 시간을 받아옴
tm = *localtime(&ct);
write(1, "\033[0G", 4); //커서의 X좌표를 0으로 이동
printf("[%02d:%02d:%02d]", tm.tm_hour, tm.tm_min, tm.tm_sec);
fprintf(stderr, "\033[33m");//글자색을 노란색으로 변경
printf("사용자 1명 추가. 현재 참가자 수 = %d\n", num_user);
fprintf(stderr, "\033[32m");//글자색을 녹색으로 변경
fprintf(stderr, "server>"); //커서 출력
}

// 클라이언트가 보낸 메시지를 모든 클라이언트에게 방송
for (i = 0; i < num_user; i++) {
if (FD_ISSET(clisock_list[i], &read_fds)) {
num_chat++; //총 대화 수 증가
nbyte = recv(clisock_list[i], buf, MAXLINE, 0);
if (nbyte <= 0) {
removeClient(i); // 클라이언트의 종료
continue;
}
buf[nbyte] = 0;
// 종료문자 처리
if (strstr(buf, EXIT_STRING) != NULL) {
removeClient(i); // 클라이언트의 종료
continue;
}
// 모든 채팅 참가자에게 메시지 방송
for (j = 0; j < num_user; j++)
send(clisock_list[j], buf, nbyte, 0);
printf("\033[0G"); //커서의 X좌표를 0으로 이동
fprintf(stderr, "\033[97m");//글자색을 흰색으로 변경
printf("%s", buf); //메시지 출력
fprintf(stderr, "\033[32m");//글자색을 녹색으로 변경
fprintf(stderr, "server>"); //커서 출력
}
}

} // end of while

return 0;
}

// 새로운 채팅 참가자 처리
void addClient(int s, struct sockaddr_in *newcliaddr) {
char buf[20];
inet_ntop(AF_INET, &newcliaddr->sin_addr, buf, sizeof(buf));
write(1, "\033[0G", 4); //커서의 X좌표를 0으로 이동
fprintf(stderr, "\033[33m"); //글자색을 노란색으로 변경
printf("new client: %s\n", buf);//ip출력
// 채팅 클라이언트 목록에 추가
clisock_list[num_user] = s;
strcpy(ip_list[num_user], buf);
num_user++; //유저 수 증가
}

// 채팅 탈퇴 처리
void removeClient(int s) {
close(clisock_list[s]);
if (s != num_user - 1) { //저장된 리스트 재배열
clisock_list[s] = clisock_list[num_user - 1];
strcpy(ip_list[s], ip_list[num_user - 1]);
}
num_user--; //유저 수 감소
ct = time(NULL); //현재 시간을 받아옴
tm = *localtime(&ct);
write(1, "\033[0G", 4); //커서의 X좌표를 0으로 이동
fprintf(stderr, "\033[33m");//글자색을 노란색으로 변경
printf("[%02d:%02d:%02d]", tm.tm_hour, tm.tm_min, tm.tm_sec);
printf("채팅 참가자 1명 탈퇴. 현재 참가자 수 = %d\n", num_user);
fprintf(stderr, "\033[32m");//글자색을 녹색으로 변경
fprintf(stderr, "server>"); //커서 출력
}

// 최대 소켓번호 찾기
int getmax() {
// Minimum 소켓번호는 가정 먼저 생성된 listen_sock
int max = listen_sock;
int i;
for (i = 0; i < num_user; i++)
if (clisock_list[i] > max)
max = clisock_list[i];
return max;
}

// listen 소켓 생성 및 listen
int tcp_listen(int host, int port, int backlog) {
int sd;
struct sockaddr_in servaddr;

sd = socket(AF_INET, SOCK_STREAM, 0);
if (sd == -1) {
perror("socket fail");
exit(1);
}
// servaddr 구조체의 내용 세팅
bzero((char *)&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(host);
servaddr.sin_port = htons(port);
if (bind(sd, (struct sockaddr *)&servaddr, sizeof(servaddr)) < 0) {
perror("bind fail"); exit(1);
}
// 클라이언트로부터 연결요청을 기다림
listen(sd, backlog);
return sd;
}

Client

컴파일 및 실행 방법

1
2
$ gcc -o client client.c
$ ./client 127.0.0.1 9999 nick

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <fcntl.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <sys/time.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <time.h>

#define MAXLINE 1000
#define NAME_LEN 20

char *EXIT_STRING = "exit";
// 소켓 생성 및 서버 연결, 생성된 소켓리턴
int tcp_connect(int af, char *servip, unsigned short port);
void errquit(char *mesg) { perror(mesg); exit(1); }

int main(int argc, char *argv[]) {
char bufname[NAME_LEN]; // 이름
char bufmsg[MAXLINE]; // 메시지부분
char bufall[MAXLINE + NAME_LEN];
int maxfdp1; // 최대 소켓 디스크립터
int s; // 소켓
int namelen; // 이름의 길이
fd_set read_fds;
time_t ct;
struct tm tm;

if (argc != 4) {
printf("사용법 : %s sever_ip port name \n", argv[0]);
exit(0);
}

s = tcp_connect(AF_INET, argv[1], atoi(argv[2]));
if (s == -1)
errquit("tcp_connect fail");

puts("서버에 접속되었습니다.");
maxfdp1 = s + 1;
FD_ZERO(&read_fds);

while (1) {
FD_SET(0, &read_fds);
FD_SET(s, &read_fds);
if (select(maxfdp1, &read_fds, NULL, NULL, NULL) < 0)
errquit("select fail");
if (FD_ISSET(s, &read_fds)) {
int nbyte;
if ((nbyte = recv(s, bufmsg, MAXLINE, 0)) > 0) {
bufmsg[nbyte] = 0;
write(1, "\033[0G", 4); //커서의 X좌표를 0으로 이동
printf("%s", bufmsg); //메시지 출력
fprintf(stderr, "\033[1;32m"); //글자색을 녹색으로 변경
fprintf(stderr, "%s>", argv[3]);//내 닉네임 출력

}
}
if (FD_ISSET(0, &read_fds)) {
if (fgets(bufmsg, MAXLINE, stdin)) {
fprintf(stderr, "\033[1;33m"); //글자색을 노란색으로 변경
fprintf(stderr, "\033[1A"); //Y좌표를 현재 위치로부터 -1만큼 이동
ct = time(NULL); //현재 시간을 받아옴
tm = *localtime(&ct);
sprintf(bufall, "[%02d:%02d:%02d]%s>%s", tm.tm_hour, tm.tm_min, tm.tm_sec, argv[3], bufmsg);//메시지에 현재시간 추가
if (send(s, bufall, strlen(bufall), 0) < 0)
puts("Error : Write error on socket.");
if (strstr(bufmsg, EXIT_STRING) != NULL) {
puts("Good bye.");
close(s);
exit(0);
}
}
}
} // end of while
}

int tcp_connect(int af, char *servip, unsigned short port) {
struct sockaddr_in servaddr;
int s;
// 소켓 생성
if ((s = socket(af, SOCK_STREAM, 0)) < 0)
return -1;
// 채팅 서버의 소켓주소 구조체 servaddr 초기화
bzero((char *)&servaddr, sizeof(servaddr));
servaddr.sin_family = af;
inet_pton(AF_INET, servip, &servaddr.sin_addr);
servaddr.sin_port = htons(port);

// 연결요청
if (connect(s, (struct sockaddr *)&servaddr, sizeof(servaddr))
< 0)
return -1;
return s;
}