99코딩

풀이 방법

1. 각 큐의 합을 구한다

2. 각 큐의 합을 더했을 때 값이 홀수라면 두 큐의 값을 같게 만들 수 없으므로 -1을 리턴

3. 큐의 사이즈를 qSize 변수에 담고 while문의 조건에 이동 횟수가 qSized * 4를 넘어가지 않도록 한다

4. 각 큐의 합이 같다면 count를 리턴하고 그렇지 않다면 각각 pop과 insert를 수행해준다.

5. 만약 while문이 끝날 때까지 각 큐의 합이 같아지지 않았다면 -1을 리턴

#include <string>
#include <vector>

using namespace std;

long count, sum1, sum2, goal, idx1, idx2;

int solution(vector<int> queue1, vector<int> queue2) {
    for(int i = 0; i < queue1.size(); i++)
        sum1 += queue1[i];
    
    for(int j = 0; j < queue2.size(); j++)
        sum2 += queue2[j];
    
    goal = sum1 + sum2;
    
    if(goal % 2 == 1)
        return -1;
    
    int qSize = queue1.size();
    
    while(count < qSize * 3) {
        if(sum1 == sum2) return count;
        else if(sum1 < sum2) {
            queue1.push_back(queue2[idx2]);
            sum1 += queue2[idx2];
            sum2 -= queue2[idx2];
            queue2[idx2++] = 0;
        }
        else {
            queue2.push_back(queue1[idx1]);
            sum1 -= queue1[idx1];
            sum2 += queue1[idx1];
            queue1[idx1++] = 0;
        }
        count++;
    }
    
    return -1;
}

윈도우 운영체제의 소켓 함수

#include <winsock2.h>

SOCKET socket(int af, int type, int protocol);

• 인자의 종류와 의미는 리눅스의 socket 함수와 동일
• 반환형은 리눅스의 int형과 달리 SOCKET형
• 성공 시 소켓 핸들, 실패 시 INVALID_SOCKET 반환

윈도우 기반 TCP 소켓 예제

#define  _WINSOCK_DEPRECATED_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <winsock2.h>

void ErrorHandling(char* message);

int main(int argc, char* argv[]) {
	WSADATA wsaData;
	SOCKET hSocket;
	SOCKADDR_IN servAddr;

	char message[30];
	int strLen = 0;
	int idx = 0, readLen = 0;

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

	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0)
		ErrorHandling("WSAStartup() Error!");

	hSocket = socket(PF_INET, SOCK_STREAM, 0);

	if (hSocket == INVALID_SOCKET)
		ErrorHandling("socket() Error!");

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

	if (connect(hSocket, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR)
		ErrorHandling("connect() Error!");

	while (readLen = recv(hSocket, &message[idx++], 1, 0)) {
		if (readLen == -1)
			ErrorHandling("read() Error!");

		strLen += readLen;
	}

	if (strLen == -1)
		ErrorHandling("read() Error!");

	printf("Message from Server: %s \n", message);
	printf("Function read call count: %d \n", strLen);

	closesocket(hSocket);
	WSACleanup();

	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputc('\n', stderr);

	exit(1);
}

프로토콜

컴퓨터 상호간의 대화에 필요한 통신규약

소켓의 생성

#include <sys/socket.h>

int socket(int domain, int type, int protocol);

• domain: 소켓이 사용할 프로토콜 체계(Protocol Family) 정보 전달
• type: 소켓의 데이터 전송방식에 대한 정보 전달
• protocol: 두 컴퓨터간 통신에 사용되는 프로토콜 정보 전달

프로토콜 체계(Protocol Family)

소켓의 타입(Type)

소켓의 전송 방식을 의미

연결지향형 소켓(SOCK_STREAM)

중간에 데이터가 소멸되지 않고 목적지로 전송

전송 순서대로 데이터가 수신

전송되는 데이터의 경계(Boundary)가 존재하지 않음

신뢰성 있는 순차적인 바이트 기반의 연결지향 데이터 전송 방식의 소켓

비 연결지향형 소켓

전송된 순서에 상관없이 가장 빠른 전송을 지향

전송된 데이터는 손실 또는 파손의 우려가 있음

전송되는 데이터의 경계 존재

한번에 전송할 수 있는 데이터의 크기 제한

신뢰성과 순차적 데이터 전송을 보장하지 않는, 고속의 데이터 전송을 목적으로 하는 소켓

프로토콜의 최종선택

하나의 프로토콜 체계 안에 데이터의 전송방식이 동일한 프로토콜이 둘 이상 존재하는 경우 세 번째 인자를 통해 원하는 프로토콜 정보를 구체화

리눅스 기반 tcp 소켓 예제

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

void error_handling(char* message);

int main(int argc, char* argv[]) {
	int sock;
	struct sockadddr_in serv_addr;
	char message[30];
	int str_len;
	int idx = 0, read_len = 0;

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

	sock = socket(PF_INET, SOCK_STREAM, 0);

	if (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 = inet_addr(argv[1]);
	serv_addr.sin_port = htons(atoi(argv[2]));

	if (connect(sock, (struct sockaddr*) & serv_addr, sizeof(serv_addr)) == -1)
		error_handling("connect() error!");

	while (read_len = read(sock, &message[idx++], 1)) {
		if (read_len == -1)
			error_handling("read() Error!");

		str_len += read_len;
	}

	printf("Message from server : %s \n", message);
	printf("Function read call count: %d \n", str_len);
	close(sock);

	return 0;
}

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

• 각 칸의 숫자는 해당 칸에서 최대 며칠 머물 수 있는지 나타냄
• 이어진 땅들은 하나의 무인도
• X는 갈 수 없음

> bfs를 이용한 풀이

#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> answer;

char board[101][101] = {'0'};
bool check[101][101] = {false};

int dx[4] = {1, 0 , -1, 0};
int dy[4] = {0, -1, 0 , 1};

void bfs(int posX, int posY, int width, int height) {
    queue<pair<int, int>> q;
    q.push({posX, posY});
    check[posX][posY] = true;
    
    int sum = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        sum += board[x][y] - '0';
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = x + dx[i];
            int curY = y + dy[i];
            
            if(curX < 0 || curX >= width || curY < 0 || curY >= height || check[curX][curY] || board[curX][curY] == 'X') continue;
            
            check[curX][curY] = true;
            q.push({curX,curY});
        }
    }
    
    answer.push_back(sum);
}

vector<int> solution(vector<string> maps) {
    int width = maps.size();
    int height = maps[0].size();
    
    for(int i = 0; i < width; i++)
        for(int j = 0; j < height; j++)
            board[i][j] = maps[i][j];
    
    for(int i = 0; i < width; i++) {
        for(int j = 0; j < height; j++) {
            if(!check[i][j] && maps[i][j] != 'X')
                bfs(i, j , width, height);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    if(answer.empty()) {
        answer.push_back(-1);
        return answer;
    }
    else
        return answer;
}

윈도우 소켓(Windows Socket API)

윈도우 운영체제에서 네트워크 프로그래밍을 위한 API

헤더 파일 winsock2.h

ws2_32.lib 라이브러리 링크 필요

윈도우 소켓의 초기화

윈도우 소켓 프로그래밍을 위해선 초기화가 필요

#include <winsock2.h>

int WSAStartup(WORD wVersionRequested, LPWSADATA lpwSAData);

• wVersionRequested: 프로그래머가 사용할 윈도우 소켓의 버전정보 전달
• lpWSAData: WSADATA라는 구조체 변수의 주소 값 전달

윈도우 기반 소켓관련 함수

소켓 생성

#include <winsock2.h>

SOCKET socket(int af, int type, int protocol);

IP주소와 PORT번호 할당

#include <winsock2.h>

int bind(SOCKET s, const struct sockaddr * name, int namelen);

연결 요청 허용 가능 상태로 변경

#include <winsock2.h>

int listen(SOCKET s, int backlog);

연결 요청 수락

#include <winsock2.h>

SOCKET accept(SOCKET s, struct sockaddr * addr, int * addrlen);

클라이언트에서 연결 요청 시

#include <winsock2.h>

int connect(SOCKET s, const struct sockaddr * name, int namelen);

소켓 닫기

#include <winsock2.h>

int closesocket(SOCKET s);

파일 핸들과 소켓 핸들

리눅스의 파일 디스크립터와 마찬가지로 윈도우에서는 핸들(Handle)을 반환

윈도우는 리눅스와는 달리 파일 핸들과 소켓 핸들을 구분

윈도우 기반 서버 예제

#include <stdio.h>
#include <stdlib.h>
#include <WinSock2.h>
void ErrorHandling(char* message);

int main(int argc, char* argv[])
{
	WSADATA wsaData;
	SOCKET hServSock, hClntSock;
	SOCKADDR_IN servAddr, clntAddr;

	int szClntAddr;
	char message[] = "Hello World!";
	if (argc != 2)
	{
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}
	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0)
		ErrorHandling("WSAStartUp() error!");

	hServSock = socket(PF_INET, SOCK_STREAM, 0);
	if (hServSock == INVALID_SOCKET)
		ErrorHandling("socket() error");

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

	if (bind(hServSock, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR)
		ErrorHandling("bind() error");

	if (listen(hServSock, 5) == SOCKET_ERROR)
		ErrorHandling("listen() error");

	szClntAddr = sizeof(clntAddr);
	hClntSock = accept(hServSock, (SOCKADDR*)&clntAddr, &szClntAddr);
	if (hClntSock == INVALID_SOCKET)
		ErrorHandling("accept() error");

	send(hClntSock, message, sizeof(message), 0);
	closesocket(hClntSock);
	closesocket(hServSock);
	WSACleanup();
	return 0;
}

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

윈도우 클라이언트 기반 예제

#define  _WINSOCK_DEPRECATED_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <winsock2.h>

void ErrorHandling(char* message);

int main(int argc, char* argv[]) {
	WSADATA wsaData;
	SOCKET hSocket;
	SOCKADDR_IN servAddr;

	char message[30];
	int strLen;

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

	if (WSAStartup(MAKEWORD(2, 2), &wsaData) != 0)
		ErrorHandling("WSAStartup() Error!");

	hSocket = socket(PF_INET, SOCK_STREAM, 0);

	if (hSocket == INVALID_SOCKET)
		ErrorHandling("socket() Error!");

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

	if (connect(hSocket, (SOCKADDR*)&servAddr, sizeof(servAddr)) == SOCKET_ERROR)
		ErrorHandling("connect() Error!");

	strLen = recv(hSocket, message, sizeof(message) - 1, 0);

	if (strLen == -1)
		ErrorHandling("read() Error!");

	printf("Message from Server: %s \n", message);

	closesocket(hSocket);
	WSACleanup();
	
	return 0;
}

void ErrorHandling(char* message) {
	fputs(message, stderr);
	fputc('\n', stderr);

	exit(1);
}

윈도우 기반 입출력 함수

데이터 전송

#include <winsock2.h>

int send(SOCKET s, const chat *buf, int len, int flags);

데이터 수신

#include <winsock2.h>

int recv(SOCKET s, const char * buf, int len, int flags);

리눅스는 소켓을 파일의 일종으로 구분

리눅스에서 독립적으로 제공하는 함수를 통해 소켓을 데이터 송수신에 사용 가능

파일 디스크립터를 인자로 하여 입출력을 진행

• 파일 디스크립터: 시스템으로부터 할당 받은 파일 또는 소켓에 부여된 정수

파일 입출력 함수

파일 열기

#include <sys/types.h>
#include <sys/stat.h>
#include <fcnt1.h>

int open(const char *path, int flag);

• 성공 시 파일 디스크립터, 실패 시 -1 리턴

파일 닫기

#include <unistd.h>

int close(int fd);

• 성공 시 0, 실패 시 -1 리턴

파일에 데이터 쓰기

#include <unistd.h>

ssize_t write(int fd, const void * buf, size_t nbytes);

• 성공 시 전달한 바이트 수, 실패 시 -1 리턴

파일에 저장된 데이터 읽기

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t nbytes);

• 성공 시 수신한 바이트 수, 실패 시 -1 리턴

파일 디스크립터와 소켓

#include <stdio.h>
#include <fcnt1.h>
#include <unistd.h>
#include <sys/socket.h>

int main() {
	int fd1, fd2, fd3;
    fd1 = socket(PF_INET, SOCK_STREAM, 0);
    fd2 = open("test.dat", O_CREAT|O_WORNLY|O_TRUNC);
    fd3 = socket(PF_INET, SOCK_DGRAM, 0);
    
    printf("file descriptor 1: %d\n", fd1);
    printf("file descriptor 2: %d\n", fd2);
    printf("file descriptor 3: %d\n", fd3);
    
    close(fd1);
    close(fd2);
    close(fd3);
    
    return 0;
}

1. 시작점을 찾는다.

2. routes를 순회하며 각 방향으로 지정된 횟수만큼 {curX, curY}를 이동하며 범위를 벗어나는지, 도중에 X가 있는지 체크한다.

3. 순회가 끝난 후 { nowCoordinate.first, nowCoordinate.second }를 리턴한다.

#include <string>
#include <vector>
#include <map>

using namespace std;

map<char, int> m = {{'E', 0}, {'W', 1}, {'S', 2}, {'N', 3}};
int dirX[4] = {0, 0, 1, -1};
int dirY[4] = {1, -1, 0, 0};

vector<int> solution(vector<string> park, vector<string> routes) {
    pair<int, int> nowCoordinate;
    
    int height = park.size();
    int width = park[0].size();
    
    for(int i = 0; i < height; i++)
        for(int j = 0; j < width; j++)
            if(park[i][j] == 'S') {
                nowCoordinate = {i, j};
                break;
            }
    
    for(int i = 0; i < routes.size(); i++) {
        int dir = m[routes[i][0]];
        int dis = routes[i][2] - 48;
        
        int curX = nowCoordinate.first;
        int curY = nowCoordinate.second;
        
        for(;dis > 0; dis--) {
            curX += dirX[dir];
            curY += dirY[dir];
            
            if(curX >= height || curX < 0 || curY >= width || curY < 0 || park[curX][curY] == 'X') break;
        }
        
        if(dis <= 0) nowCoordinate = {curX, curY};
    }
    
    return { nowCoordinate.first, nowCoordinate.second };
}

네트워크 프로그래밍

• 네트워크로 연결되어 있는 서로 다른 두 컴퓨터가 데이터를 주고받을 수 있도록 하는 것
• 소켓 프로그래밍이라고 불리기도 함

소켓

• 운영체제 차원에서 제공하는 네트워크상에서의 데이터 송수신에 사용할 수 있는 소프트웨어적인 장치
• 네트워크 망의 연결에 사용하는 도구
• 네트워크를 통한 두 컴퓨터의 연결을 의미하기도 함

소켓의 구현

• 소켓을 사용하기 위해선 소켓을 먼저 생성해주어야 함
• 성공 시 파일 디스크립터, 실패 시 -1 리턴

#include <sys/socket.h>
int socket(int domain, int type, int protocol);

• 소켓 생성 후에는 생성한 소켓에 주소정보(IP, 포트번호)를 할당해주어야 함
• 성공 시 0, 실패 시 -1 리턴

#include <sys/socket.h>
int bind(int sockfd, struct sockaddr *myaddr, socklen_t addrlen);

• 소켓에 주소정보가 할당되었으면 소켓을 연결요청이 가능한 상태로 만들어줘야 함
• 성공 시 0, 실패 시 -1 리턴

#include <sys/socket.h>
int listen(int sockfd, int backlog);

• 연결요청이 왔다면 해당 요청에 대한 수락을 해줘야 함
• 성공 시 파일 디스크립터, 실패 시 -1 리턴

#include <sys/socket.h>
int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);

• 클라이언트에서는  소켓 생성과 서버로의 연결요청 과정만 존재
• 성공 시 0, 실패 시 -1 리턴

#include <sys/socket.h>
int connect(int sockfd, struct sockaddr* serv_addr, socklen_t addrlen);

위 내용을 통해 네트워크 프로그래밍에서 연결요청을 허용하는 소켓의 생성과정을 아래와 같이 정리할 수 있다.

• 1단계: 소켓 생성
• 2단계: IP주소와 포트번호 할당
• 3단계: 연결요청 가능상태로 변경
• 4단계: 연결요청에 대한 수락

서버와 클라이언트

• 연결요청을 수락하는 기능의 프로그램을 가리켜 서버(Server)라 함
• 서버 프로그램에 연결요청을 하는 프로그램을 클라이언트(Client)라 함
• 아래 두 코드는 리눅스 기반에서 컴파일 및 실행을 해야 함

hello_server.c

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

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

	char message[] = "Hello World!";

	if (argc != 2) {
		print("Usage : %s <port>\n", argv[0]);
		exit(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]));

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

	if (listen(serv_sock, 5) == -1)
		error_handling("listen() error");

	clnt_addr_size = sizeof(clnt_addr);
	clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_addr, *clnt_addr_size);

	if (clnt_sock == -1)
		error_handling("accept() error");

	write(clnt_sock, message, sizeof(message));
	close(clnt_sock);
	close(serv_sock);

	return 0;
}

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

hello_client.c

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

void error_handling(char* message);

int main(int argc, char* argv[]) {
	int sock;
	struct sockadddr_in serv_addr;
	char message[30];
	int str_len;

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

	sock = socket(PF_INET, SOCK_STREAM, 0);

	if (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 = inet_addr(argv[1]);
	serv_addr.sin_port = htons(atoi(argv[2]));

	if (connect(sock, (struct sockaddr*) & serv_addr, sizeof(serv_addr)) == -1)
		error_handling("connect() error!");

	str_len = read(sock, message, sizeof(message) - 1);

	if (str_len == -1)
		error_handling("read() error!");

	printf("Message from server : %s \n", message);
	close(sock);

	return 0;
}

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

문제 이해

• 최소한의 이동 거리로 모든 파일을 드래그
• '.'은 빈칸, '#'은 문서

문제 풀이

• string 벡터를 돌며 해당 인덱스의 원소가 '#'인 경우에 해당 위치의 좌표를 각각 비교해서 조건에 맞다면 삽입
• 반복문이 끝난 후 출력

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    int luX = 51, luY = 51;
    int rdX = 0, rdY = 0;
    int colLength = wallpaper.size();
    int rowLength = wallpaper[0].size();
    
    for(int i = 0; i < colLength; i++) {
        for(int j = 0; j < rowLength; j++) {
            if(wallpaper[i][j] == '#') {
                if(i < luX) luX = i;
                if(j < luY) luY = j;
                if(i + 1 > rdX) rdX = i + 1;
                if(j + 1 > rdY) rdY = j + 1;
            }
        }
    }
    
    return {luX, luY, rdX, rdY};
}

문제 조건

• 이름을 불린 선수는 앞의 선수를 추월
• 1등인 선수의 이름은 불리지 않음

문제 풀이

1. map에 각 선수의 등수를 저장하고 선수의 이름이 불릴 때마다 pos에 삽입
2. 두 선수의 순서를 바꿔주고 map에 저장된 각 선수의 등수를 조정
3. callings.size()만큼 반복 후 players 배열 리턴

#include <string>
#include <vector>
#include <map>

using namespace std;

map<string, int> m;

vector<string> solution(vector<string> players, vector<string> callings) {
    for(int i = 0; i < players.size(); i++)
        m[players[i]] = i;
    
    for(int i = 0; i < callings.size(); i++) {
        string temp = "";
        int pos = m[callings[i]];
      
        m[players[pos]]--;
        
        temp = players[pos];
        players[pos] = players[pos - 1];
        players[pos - 1] = temp;
        
        m[players[pos]]++;
    }
    
    return players;
}