jayyhkwon의 개발공부로그

BOJ 1182번 부분수열의 합

14 Mar 2020 | Algorithm 


import java.util.Scanner;

public class BOJ_1182 {

    static int[] num;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int s = sc.nextInt();

        num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }

        int answer = 0;

        for (int i = 1; i < (1 << n); i++) {
            int sum = 0;
            for (int k = 0; k < n; k++) {
                if ((i & (1 << k)) != 0)
                    sum += num[k];
            }

            if(sum == s)
                answer++;
        }
        System.out.println(answer);

    }

}

소켓 프로그래밍

13 Mar 2020 | Network

소켓

​ 네트워크 상에 연결되어 있는 컴퓨터 간에 데이터를 주고받기 위해 필요한 추상화된 장치이다.

​ 유저 공간에 존재하는 프로세스(서버,클라이언트)는 커널 공간에 의해 생성된 소켓을 통해 데이터를 송수신 할 수 있다

socket program


​ 소켓은 로컬 IP주소와 Port번호, 원격 IP주소와 Port 번호, 그리고 수신버퍼와 송신버퍼가 존재한다.

socket


소켓 연결과 생성과정

server_client_socket

  • 서버
    • 클라이언트로부터의 연결요청도 하나의 데이터 전송이다. 따라서 연결 요청을 받아들이기 위해 하나의 소켓이 필요하고 이 소켓을 가리켜 서버소켓 또는 리스닝 소켓이라고 한다. listen 함수의 호출은 소켓을 리스닝 소켓으로 만든다.
    • accept 함수의 결과로 서버소켓을 통해 클라이언트로부터 연결요청을 받으면, 연결요청 정보를 참조하여 클라이언트 소켓과의 통신을 위한 별도의 소켓을 하나 더 추가로 생성한다. 그리고 이렇게 생성된 소켓을 대상으로 데이터의 송수신이 진행된다.
  • 클라이언트
    • 소켓을 생성하고 연결 요청을 위해서 connect 함수를 호출하는 것이 전부이다
    • 서버의 listen 함수 호출 이후에야 connect 함수 호출이 유효하다


서버 소켓의 역활

클라이언트에서 서버로 요청이 들어오면 서버는 클라이언트별로 소켓을 생성하여 요청을 처리한다(1대1 연결)

img


C언어로 구현한 간단한 서버&클라이언트 구조

  • C언어를 이용해 echo server& client를 구현한다.

  • 코드 한줄 한줄의 흐름보다는 소켓을 이용한 네트워크 통신에 초점을 맞춰 설명 할 예정이다

    linux

    리눅스에서 모든 것은 파일로 관리되므로 소켓 또한 하나의 파일로 간주된다.

    더 정확히는 파일 디스크립터로 생성되어 관리된다.

    파일 디스크립터란?

    • 운영체제가 만든 파일 또는 소켓을 구분하기 위해 부여하는 숫자

    • 저 수준 입출력 함수는 입출력을 목적으로 파일 디스크립터가 필요하다

    • 저수준 입출력 함수에 소켓의 파일 디스크립터를 전달하면, 소켓을 대상으로 입출력을 진행한다

​

echo-server.c


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define BUFFER_SIZE 1024

void error_handling(char *message);

int main(int argc, char*argv[])
{
    int serv_sock;
    int clnt_sock;

    struct sockaddr_in serv_addr;
    struct sockaddr_in clnt_addr;
    socklen_t clnt_addr_size;

    char message[BUFFER_SIZE];

    int str_len;

    if(argc != 2)
    {
        printf("Usage : %s <port> \n",argv[0]);
        exit(1);
    }

    // 1. 소켓을 생성한다
    serv_sock = socket(PF_INET, SOCK_STREAM, 0);
    if(serv_sock == -1)
        error_handling("socket() error");

    memset(&serv_addr, 0, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET; //
    serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);
    serv_addr.sin_port = htons(atoi(argv[1]));


    // 2. 소켓에 IP와 Port 번호를 할당한다
    if(bind(serv_sock, (struct sockaddr*)&serv_addr, sizeof(serv_addr)) == -1)
        error_handling("bind() error");

    // 3. 서버 소켓을 연결요청 가능 상태로 변경한다 (socket -> listening socket)
    //    5개의 연결요청 대기큐를 생성하여 클라이언트의 요청을 하나씩 처리한다
    if(listen(serv_sock, 5) == -1)
        error_handling("listen() error");

    clnt_addr_size = sizeof(clnt_addr);

    for(int i=0; i<5; i++)
    {
        // 4. 클라이언트의 접속 요청을 수락한다 (클라이언트와 연결된 새로운 socket이 생성된다)
        clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_addr, &clnt_addr_size);
        if(clnt_sock == -1)
            error_handling("accept() error");
        else
            printf("Connected client %d \n", i+1);

        // 5. 클라이언트와 송수신 한다
        while ((str_len=read(clnt_sock, message, BUFFER_SIZE)) != 0)
            write(clnt_sock, message, str_len);

        // 6. 송수신이 끝난 클라이언트 소켓을 닫는다
        close(clnt_sock);
    }

    // 7. 서버 소켓을 닫는다
    close(serv_sock);
    return 0;
}

void error_handling(char *message)
{
    fputs(message, stderr);
    fputc("\n", stderr);
    exit(1);
}

echo_client.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define BUF_SIZE 1024
void error_handling(char *message);

int main(int argc, char *argv[]) {
    // 파일 디스크립터를 위한 변수
    int sock;
    char message[BUF_SIZE];
    int str_len;
    struct sockaddr_in serv_adr;

    if (argc != 3) {
        printf("Usage : %s <IP> <port>\n", argv[0]);
        exit(1);
    }

    // 1. socket 하나를 생성한다.
    sock = socket(PF_INET, SOCK_STREAM, 0);
    if (sock == -1)
        error_handling("socket() error");

    memset(&serv_adr, 0, sizeof(serv_adr));
    serv_adr.sin_family = AF_INET;
    serv_adr.sin_addr.s_addr = inet_addr(argv[1]);
    serv_adr.sin_port = htons(atoi(argv[2]));

    // 2. socket을 이용해 server의 server socket(listen socket)에 연결을 요청한다.
    if (connect(sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr)) == -1)
        error_handling("connect() error!");
    else
        puts("Connected...........");

    while(1) {
        fputs("Input message(Q to quit): ", stdout);
        fgets(message, BUF_SIZE, stdin);

        if (!strcmp(message,"q\n") || !strcmp(message,"Q\n"))
            break;

        // 3. 연결된 socket을 통해 server로부터 데이터를 송수신한다.
        write(sock, message, strlen(message));
        str_len = read(sock, message, BUF_SIZE-1);
        message[str_len] = 0;
        printf("Message from server: %s", message);
    }

    close(sock);
    return 0;
}

void error_handling(char *message) {
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}


문제점

  • for문을 이용하여 클라이언트의 요청을 처리하는 위 코드는 동시에 여러 명의 클라이언트의 요청을 처리할 수없고 하나의 클라이언트와 연결이 끊어질 때까지 다른 클라이언트들은 기다려야 하는 문제가 발생한다.


해결방안

위의 문제점을 해결하기 위한 해결방안으로 크게 3가지가 있다

  • 멀티프로세스 기반 서버 - 클라이언트의 요청마다 프로세스를 생성하여 처리한다
  • 멀티플렉싱 기반 서버 - 입출력 대상을 묶어서 관리하는 방식으로 처리한다
  • 멀티스레드 기반 서버 - 클라이언트의 요청마다 스레드를 생성하여 처리한다



멀티 프로세스 기반 서버

​ 멀티프로세스 기반의 서버는 클라이언트의 요청마다 프로세스를 생성하는 방식으로 서비스를 제공한다

multi_process_server

  1. 부모 프로세스는 리스닝 소켓으로 accept 함수를 통해 연결요청을 수락한다
  2. 이때 얻게 되는 소켓의 파일 디스크립터를 자식 프로세스를 생성해서 넘겨준다
  3. 자식 프로세스는 전달받은 파일 디스크립터를 바탕으로 서비스를 제공한다


echo_multi_process_server.c


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define BUF_SIZE 30
void error_handling(char *message);
void read_childproc(int sig);

int main(int argc, char *argv[]) {
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;

    pid_t pid;
    struct sigaction act;
    socklen_t adr_sz;
    int str_len, state;
    char buf[BUF_SIZE];
    if (argc != 2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }

    act.sa_handler = read_childproc;
    sigemptyset(&act.sa_mask);
    act.sa_flags = 0;
    state = sigaction(SIGCHLD, &act, 0);
    // 1. socket 하나를 생성한다.
    serv_sock = socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0, sizeof(serv_adr));
    serv_adr.sin_family = AF_INET;
    serv_adr.sin_addr.s_addr = htonl(INADDR_ANY);
    serv_adr.sin_port = htons(atoi(argv[1]));

    // 2. socket에 IP와 Port 번호를 할당한다.
    if (bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr)) == -1)
        error_handling("bind() error");
    // 3. 생성한 socket을 server socket(listen socket)으로 등록한다.
    if (listen(serv_sock, 5) == -1)
        error_handling("listen() error");

    while(1) {
        adr_sz = sizeof(clnt_adr);
        // 4. 부모 프로세스는 리스닝 소켓으로 accept 함수 호출을 통해서 연결요청을 수락한다.
        clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
        if (clnt_sock == -1)
            continue;
        else
            puts("new client connected...");
        // 5. 이때 얻게 되는 소켓의 파일 디스크립터(클라이언트와 연결된 연결 소켓)를 자식 프로세스를 생성해 넘겨준다.
        pid = fork();
        if (pid == -1) {
            close(clnt_sock);
            continue;
        }
        if (pid == 0) {
            close(serv_sock);
            // 6. 자식 프로세스는 전달받은 파일 디스크립터를 바탕으로 서비스를 제공한다.
            while((str_len = read(clnt_sock, buf, BUF_SIZE)) != 0)
                write(clnt_sock, buf, str_len);

            close(clnt_sock);
            puts("client disconnected...");
            return 0;
        }
        else
            close(clnt_sock);
    }
    close(serv_sock);
    return 0;
}

void read_childproc(int sig) {
    pid_t pid;
    int status;
    pid = waitpid(-1, &status, WNOHANG);
    printf("removed proc id: %d \n", pid);
}
void error_handling(char *message) {
    fputs(message, stderr);
    fputc('\n', stderr);
    exit(1);
}
  • 장점
    • 프로그램의 흐름이 단순하기 때문에 이해하기 쉽다
    • 안정적인 실행이 가능하다. 독립적인 메모리 공간을 가지므로 다른 프로세스끼리 영향을 끼치지 않는다
  • 단점
    • 프로세스의 생성에 많은 비용이 발생한다
    • fork()를 이용하여 부모 프로세스를 복사하므로 한 소켓에 대한 파일 디스크립터도 복사된다. 따라서 하나의 소켓에 두 개의 파일 디스크립터가 존재하므로 두 개의 파일 디스크립터를 종료해야 해당 소켓을 제거할 수 있다
    • 서로 다른 독립적인 메모리 공간을 가지므로 프로세스간 정보 교환이 어렵다



멀티 스레드 기반 서버

​ 멀티스레드 기반의 서버는 클라이언트의 요청마다 스레드를 생성하여 서비스를 제공한다

multi_thread_server

  1. 메인 스레드는 리스닝 소켓으로 accept 함수를 통해서 연결요청을 수락한다
  2. 이때 얻게 되는 소켓의 파일 디스크립터를 워커 스레드를 생성하여 넘겨준다
  3. 워커 스레드는 전달받은 파일 디스크립터를 바탕으로 서비스를 제공한다

echo_multi_thread_server.c


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <sys/wait.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <pthread.h>

#define BUF_SIZE 30

void * handle_clnt(void * arg);
void error_handling(char * msg);

int main(int argc, char *argv[]) {
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;

    pthread_t t_id;
    socklen_t adr_sz;
    int str_len, state;
    char buf[BUF_SIZE];
    if (argc != 2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }

    // 1. socket 하나를 생성한다.
    serv_sock = socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0, sizeof(serv_adr));
    serv_adr.sin_family = AF_INET;
    serv_adr.sin_addr.s_addr = htonl(INADDR_ANY);
    serv_adr.sin_port = htons(atoi(argv[1]));

    // 2. socket에 IP와 Port 번호를 할당한다.
    if (bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr)) == -1)
        error_handling("bind() error");
    // 3. 생성한 socket을 server socket(listen socket)으로 등록한다.
    if (listen(serv_sock, 5) == -1)
        error_handling("listen() error");

    while(1) {
        adr_sz = sizeof(clnt_adr);
        // 4. 메인 스레드는 리스닝 소켓으로 accept 함수 호출을 통해서 연결요청을 수락한다.
        clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);

        if (clnt_sock == -1)
            continue;

        puts("new client connected...");

        // 5. 클라이언트와 연결된 소켓의 파일 디스크립터를 워커 스레드를 생성해 넘겨준다.
        pthread_create(&t_id, NULL, handle_clnt, (void*)&clnt_sock);
        pthread_detach(t_id);
    }

    close(serv_sock);
    return 0;
}

void * handle_clnt(void * arg) {
    int clnt_sock=*((int*)arg);
    int str_len=0, i;
    char buf[BUF_SIZE];

    // 6. 워커 스레드는 전달받은 파일 디스크립터를 바탕으로 서비스를 제공한다.
    while((str_len = read(clnt_sock, buf, BUF_SIZE)) != 0)
        write(clnt_sock, buf, str_len);

    close(clnt_sock);
    return NULL;
}

void error_handling(char * msg) {
    fputs(msg, stderr);
    fputc('\n', stderr);
    exit(1);
}


  • 장점
    • 프로세스를 생성하는 비용보다 스레드를 생성하는 비용이 적다
    • 스레드간 공유한느 메모리를 갖기 때문에, 스레드간 정보 교환이 쉽다
  • 단점
    • 하나의 프로세스에 다수의 스레드가 존재하므로 하나의 스레드에 문제가 생긴다면 프로세스에 영향을 미쳐 의도치 않은 문제가 발생할 수 있다



멀티 플렉싱 기반 서버

​ 멀티 플렉싱 기반 서버는 입출력 대상을 묶어서 관리하는 방식으로 처리한다.

입출력 다중화 하나의 프로세스 혹은 스레드가 입력과 출력을 모두 다루는 기술을 말한다. 커널에서는 하나의 스레드가 여러 개의 소켓을 핸들링 할 수 있는 select, poll, epoll과 같은 시스템 콜을 제공한다

​ 한 개의 프로세스 혹은 스레드가 하나의 클라이언트에 대한 입출력만 처리할 수 있었던 이유는 입출력 함수가 blocked 되기 때문이다. 입출력 데이터가 준비될 때까지 무한정 봉쇄되어 여러 클라이언트가 입출력을 처리할 수 없기 때문이다.

​ 그러나 멀티플렉싱 기법을 사용하면 여전히 입출력 함수는 blocked되지만, 입출력 함수를 호출하기 전에 어떤 소켓에서 입출력이 준비되었는지 알 수 있다.

멀티 스레드 기반 서버와 차이점

  • 각 클라이언트 마다 별도의 스레드를 생성하는 것이 아닌 하나의 스레드에서 다수의 클라이언트에 연결된 소켓(파일 디스크립터)을 괸리하고 소켓에 이벤트(read/write)가 발생할 경우에만 별도의 스레드를 만들어 해당 이벤트를 처리하도록 구현할 수 있다


1. select

​ fd_set이라는 구조체로 파일 디스크립터들을 묶어서 관리하며 이벤트(입력,출력,에러)가 발생한 경우

​ 이벤트가 발생한 파일 디스크립터 갯수를 리턴한다

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout)

  • nfds: 검사 대상이 되는 파일 디스크립터의 수
  • readfs: 읽기 이벤트를 검사할 파일 디스크립터의 목록
  • writefds: 쓰기 이벤트를 검사할 파일 디스크립터의 목록
  • exceptfds: 예외 이벤트를 검사할 파일 디스크립터의 목록
  • timeout: 이벤트를 기다릴 시간 제한
  • 반환 값: 이벤트가 발생한 파일의 갯수


echo_select_server.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/select.h>

#define BUF_SIZE 100
void error_handling(char *buf);

int main(int argc, char *argv[]) {
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;
    struct timeval timeout;
    // 파일 상태 테이블 선언
    fd_set reads, cpy_reads;

    socklen_t adr_sz;
    int fd_max, str_len, fd_num, i;
    char buf[BUF_SIZE];
    if (argc != 2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }

    serv_sock = socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0, sizeof(serv_adr));
    serv_adr.sin_family = AF_INET;
    serv_adr.sin_addr.s_addr = htonl(INADDR_ANY);
    serv_adr.sin_port = htons(atoi(argv[1]));

    if (bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr)) == -1)
        error_handling("bind() error");
    if (listen(serv_sock, 5) == -1)
        error_handling("listen() error");

    FD_ZERO(&reads); // fd_set 테이블을 초기화한다.
    FD_SET(serv_sock, &reads); // 서버 소켓(리스닝 소켓)의 이벤트 검사를 위해 fd_set 테이블에 추가한다.
    fd_max = serv_sock;

    while(1) {
        cpy_reads = reads;
        timeout.tv_sec = 5;
        timeout.tv_usec = 5000;

        // result
        // -1: 오류 발생
        // 0: 타임 아웃
        // 1 이상 : 등록된 파일 디스크립터에 해당 이벤트가 발생하면 이벤트가 발생한 파일 디스크립터의 수를 반환한다.
        if ((fd_num = select(fd_max+1, &cpy_reads, 0, 0, &timeout)) == -1)
            break;

        if (fd_num == 0)
            continue;

        for (i=0; i<fd_max+1; i++) {
            if (FD_ISSET(i, &cpy_reads)) { // fd_set 테이블을 검사한다.
                // 서버 소켓(리스닝 소켓)에 이벤트(연결 요청) 발생
                if (i == serv_sock) {     // connection request!
                    adr_sz = sizeof(clnt_adr);
                    clnt_sock= accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
                    FD_SET(clnt_sock, &reads); // fd_set 테이블에 클라이언트 소켓 디스크립터를 추가한다.
                    if (fd_max < clnt_sock)
                        fd_max = clnt_sock;
                    printf("connected client: %d \n", clnt_sock);
                }
                // 클라이언트와 연결된 소켓에 이벤트 발생
                else {   // read message!
                    str_len = read(i, buf, BUF_SIZE);
                    if (str_len == 0) {   // close request!
                        FD_CLR(i, &reads); // fd_set 테이블에서 파일 디스크립터를 삭제한다.
                        close(i);
                        printf("closed client: %d \n", i);
                    } else {
                        write(i, buf, str_len);    // echo!
                    }
                }
            }
        }
    }

    close(serv_sock);
    return 0;
}

void error_handling(char *buf) {
    fputs(buf, stderr);
    fputc('\n', stderr);
    exit(1);
}
  • 장점
    • 단일 프로세스(스레드)에서 여러 파일의 입출력 처리가 가능하다
    • 대부분 OS를 지원하여 이식성이 좋다 (POSIX 기준)
  • 단점
    • select 함수를 호출할 때 마다 관찰대상에 대한 정보를 운영체제에 전달해야 한다 -> 비용이 크다
    • 어떤 파일 디스크립터에서 이벤트가 발생했는지 알 수 없으므로 fd_set에 존재하는 모든 파일 디스크립터를 검사해야 한다
    • fd 개수에 제한이 있다 (1,024개)
    • select 호출 때마다 데이터를 복사해야 한다 (select 함수를 호출한 후 이벤트를 처리할 때 fd_set 테이블 변경이 필요하기 때문에 미리 복사가 필요하다)


POSIX란?

POSIX(Portable Operating System Interface)는 이식 가능 운영 체제 인터페이스의 약자로, 서로 다른 UNIX OS의 공통 API를 정리하여 이식성이 높은 유닉스 응용 프로그램을 개발하기 위한 목적으로 IEEE가 책정한 애플리케이션 인터페이스 규격입니다.


2. epoll

​ select 함수의 단점을 보완하여 처음에 커널에 관찰대상에 대한 정보를 알려주고, 관찰 대상의 범위 또는 내용에 변경이 있을때만 변경사항을 알려주는 방식

​ 리눅스에서는 epoll, 윈도우에서는 IOCP, FreeBSD(맥)에서는 Kqueue로 운영체제별로 구현체가 다르다.

int epoll_create(int size); //size는 epoll_fd의 크기정보를 전달한다.
// 반환 값 : 실패 시 -1, 일반적으로 epoll_fd의 값을 리턴


int epoll_ctl(int epoll_fd,             // epoll_fd              
							int operate_enum,         // 어떤 변경을 할지 결정하는 enum값              							 int enroll_fd,            // 등록할 fd              
							struct epoll_event* event // 관찰 대상의 관찰 이벤트 유형              ); // 반환 값 : 실패 시 -1, 성공시 0
							

int epoll_wait(int epoll_fd,              // epoll_fd               								 struct epoll_event* event, // event 버퍼의 주소               							 int maxevents,             // 버퍼에 들어갈 수 있는 구조체 최대 개수            int timeout                // select의 timeout과 동일 단위는 1/1000               
							 );
// 성공시 이벤트 발생한 파일 디스크립터 개수 반환, 실패시 -1 반환

epoll_create : epoll 파일 디스크립터 저장소 생성

epoll_ctl : 저장소에 파일 디스크립터 등록 및 삭제

epoll_wait : select 함수와 마찬가지로 파일 디스크립터의 변화를 대기한다.

epoll_create를 통해 생성된 epoll 인스턴스에 관찰대상을 저장 및 삭제하는 함수가 epoll_ctl이고, epoll 인스턴스에 등록된 파일 디스크립터를 대상으로 이벤트의 발생 유무를 확인하는 함수가 epoll_wait이다.

echo_epoll.server.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
// 리눅스에서만 사용 가능
#include <sys/epoll.h>

#define BUF_SIZE 100
#define EPOLL_SIZE 50
void error_handling(char *buf);

int main(int argc, char *argv[]) {
    int serv_sock, clnt_sock;
    struct sockaddr_in serv_adr, clnt_adr;
    socklen_t adr_sz;
    int str_len, i;
    char buf[BUF_SIZE];

    struct epoll_event *ep_events;
    struct epoll_event event;
    int epfd, event_cnt;

    if (argc != 2) {
        printf("Usage : %s <port>\n", argv[0]);
        exit(1);
    }

    serv_sock = socket(PF_INET, SOCK_STREAM, 0);
    memset(&serv_adr, 0, sizeof(serv_adr));
    serv_adr.sin_family = AF_INET;
    serv_adr.sin_addr.s_addr = htonl(INADDR_ANY);
    serv_adr.sin_port = htons(atoi(argv[1]));
    if (bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr)) == -1)
        error_handling("bind() error");
    if (listen(serv_sock, 5) == -1)
        error_handling("listen() error");

    // 커널이 관리하는 epoll 인스턴스라 불리는 파일 디스크립터의 저장소 생성
    // 성공 시 epoll 파일 디스크립터, 실패시 -1 반환
    epfd = epoll_create(EPOLL_SIZE);
    ep_events = malloc(sizeof(struct epoll_event)*EPOLL_SIZE);

    event.events = EPOLLIN;
    event.data.fd = serv_sock;
    // 파일 디스크립터(serv_sock)를 epoll 인스턴스에 등록한다. (관찰대상의 관찰 이벤트 유형은 EPOLLIN)
    epoll_ctl(epfd, EPOLL_CTL_ADD, serv_sock, &event);

    while(1) {
        // 성공 시 이벤트가 발생한 파일 디스크립터이의 수, 실패 시 -1 반환
        // 두 번째 인자로 전달된 주소의 메모리 공간에 이벤트 발생한 파일 디스크립터에 대한 정보가 들어있다.
        event_cnt = epoll_wait(epfd, ep_events, EPOLL_SIZE, -1);
        if (event_cnt == -1) {
            puts("epoll_wait() error");
            break;
        }

        for (i=0; i<event_cnt; i++) {
            if (ep_events[i].data.fd == serv_sock) {
                adr_sz = sizeof(clnt_adr);
                clnt_sock= accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
                event.events = EPOLLIN;
                event.data.fd = clnt_sock;
                // 파일 디스크립터(clnt_sock)를 epoll 인스턴스에 등록한다. (관찰대상의 관찰 이벤트 유형은 EPOLLIN)
                epoll_ctl(epfd, EPOLL_CTL_ADD, clnt_sock, &event);
                printf("connected client: %d \n", clnt_sock);
            } else {
                str_len = read(ep_events[i].data.fd, buf, BUF_SIZE);
                if (str_len == 0) { // close request!
                    epoll_ctl(epfd, EPOLL_CTL_DEL, ep_events[i].data.fd, NULL);
                    close(ep_events[i].data.fd);
                    printf("closed client: %d \n", ep_events[i].data.fd);
                } else {
                    write(ep_events[i].data.fd, buf, str_len);    // echo!
                }
            }
        }
    }

    close(serv_sock);
    close(epfd);
    return 0;
}

void error_handling(char *buf) {
    fputs(buf, stderr);
    fputc('\n', stderr);
    exit(1);
}
  • 장점
    • select 방식과는 달리 이벤트가 발생한 경우 전체 파일디스크립터를 검사할 필요가 없다
    • select 함수에 대응하는 epoll_wait 함수 호출시, 커널에서 상태정보를 유지하기 때문에 관찰대상의 정보를 매번 전달할 필요가 없다
  • 단점
    • 운영체제에 따라 구현체가 다르므로 이식성이 좋지 않다


ref. 멀티 플렉싱 서버로 가기까지

ref. 열혈 TCP/IP 프로그래밍

BOJ 2529번 부등호

13 Mar 2020 | Algorithm 


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ_2529 {

    static String[] arr;
    static boolean[] number = new boolean[10];
    static List<String> answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        arr = new String[n];
        answer = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.next();
        }

        solve(n, 0, "");
        System.out.println(answer.get(answer.size() - 1));
        System.out.println(answer.get(0));
    }

    private static void solve(int n, int index, String s) {

        String result;

        if (index == n + 1) {
            if (check(n, s))
                answer.add(s);
            return;
        }

        for (int i = 0; i <= 9; i++) {

            if (number[i])
                continue;

            result = s + i;

            number[i] = true;
            solve(n, index + 1, result);
            number[i] = false;
        }
    }

    private static boolean check(int n, String answer) {
        for (int i = 0; i < n; i++) {
            char[] chars = answer.toCharArray();
            if (arr[i].equals(">")) {
                if (chars[i] > chars[i + 1])
                    continue;
                return false;
            }
            if (arr[i].equals("<")) {
                if (chars[i] < chars[i + 1])
                    continue;
                return false;
            }
        }
        return true;
    }

    private static int factorial(int n) {
        int answer = 1;
        for (int i = 1; i <= n; i++) {
            answer *= i;
        }
        return answer;
    }

}

BOJ 15661번 링크와 스타트

13 Mar 2020 | Algorithm 


import java.util.Arrays;
import java.util.Scanner;

public class BOJ_15661 {

    static int[][] s;
    static int answer = Integer.MAX_VALUE;
    static boolean[] startTeam;
    static boolean[] linkTeam;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        s = new int[n][n];
        startTeam = new boolean[n];
        linkTeam = new boolean[n];
        for (int i = 0; i < n; i++) {
            s[i] = Arrays.stream(sc.nextLine().split("\\s")).mapToInt(Integer::parseInt).toArray();
        }


        solve(n, 0, 0, 0);
        System.out.println(answer);
    }

    private static void solve(int n, int startCount, int linkCount, int index) {



        if (n == index) {

            if (startCount < 1 || linkCount < 1)
                return;

            int startSum = 0;
            int linkSum = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (startTeam[i] == true && startTeam[j] == true)
                        startSum += s[i][j];

                    if (linkTeam[i] == true && linkTeam[j] == true)
                        linkSum += s[i][j];
                }
            }

            int temp = Math.abs(startSum - linkSum);
            if (answer > temp)
                answer = temp;

            return;
        }

        startTeam[index] = true;
        solve(n, startCount + 1, linkCount, index + 1);
        startTeam[index] = false;
        linkTeam[index] = true;
        solve(n, startCount, linkCount + 1, index + 1);
        linkTeam[index] = false;

    }
}

BOJ 14889번 스타트와 링크

13 Mar 2020 | Algorithm 


import java.util.Arrays;
import java.util.Scanner;

public class BOJ_14889 {

    static int[][] s;
    static int answer = Integer.MAX_VALUE;
    static boolean[] startTeam;
    static boolean[] linkTeam;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        s = new int[n][n];
        startTeam = new boolean[n];
        linkTeam = new boolean[n];
        for (int i = 0; i < n; i++) {
            s[i] = Arrays.stream(sc.nextLine().split("\\s")).mapToInt(Integer::parseInt).toArray();
        }


        solve(n, 0, 0, 0);
        System.out.println(answer);
    }

    private static void solve(int n, int startCount, int linkCount, int index) {

        if (startCount > n / 2 || linkCount > n / 2)
            return;

        if (startCount == n / 2 && linkCount == n / 2 && n == index) {
            int startSum = 0;
            int linkSum = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (startTeam[i] == true && startTeam[j] == true)
                        startSum += s[i][j];

                    if (linkTeam[i] == true && linkTeam[j] == true)
                        linkSum += s[i][j];
                }
            }

            int temp = Math.abs(startSum - linkSum);
            if (answer > temp)
                answer = temp;

            return;
        }

        startTeam[index] = true;
        solve(n, startCount + 1, linkCount, index + 1);
        startTeam[index] = false;
        linkTeam[index] = true;
        solve(n, startCount, linkCount + 1, index + 1);
        linkTeam[index] = false;

    }
}