251025

lililllilillll·2025년 10월 25일

개발 일지

목록 보기
335/350

✅ 한 것들

  • 백준
  • NC 코테
  • 윤성우의 열혈 TCP/IP 소켓 프로그래밍


📝 배운 것들

🏷️ 두 점 사이의 거리

  • brute force는 O(n^2)
  • 왼쪽 오른쪽 재귀로 2분할 해서 각각의 최소 거리를 구한다
  • 칸 안에 점 2개면 그대로 반환, 점 3개면 거리 3번 비교해서 반환
  • 두 칸을 합쳐서 최소 거리를 구해야 함
    • 두 칸에서 구한 최소 거리가 d라고 할 때, 중간 선 기준으로 만큼 떨어진 원소들만 고려
    • 그것들을 y축에 대해 정렬
    • (아래 그림 참고) 두 칸 각각에서 구한 최소 거리가 d 이므로, 각 원소에 대한 다음 원소는 7개까지만 거리 비교해주면 됨
      • 원래는 y차가 d 이상이 되기 전까지 구하는 건데, 기하학적으로 7개로 제한됨.
  • 재귀 끝나면 그게 최소 거리

Q. strip의 d가 길어서 strip을 침범해버리면 어떡함?
: d는 strip 왼쪽과 오른쪽 점들의 최소 거리이므로, 그럴 일 없다.

코드 + 상세 해설 : https://www.youtube.com/watch?v=6u_hWxbOc7E
백준 문제 : https://www.acmicpc.net/problem/2261

🏷️ c++ 정렬

bool compare(const pii& p1, const pii& p2)
{
	return p1.first < p2.first;
}

int main()
{
	vp test = { {2,1}, { 1,9 },{1,1} };
	sort(test.begin(), test.end(), compare);
	for (pii t : test)
		cout << t.first << ' ' << t.second << '\n';

	cout << '\n';
	vp test2 = { {2,1}, { 1,9 },{1,1} };
	stable_sort(test2.begin(), test2.end(), compare);
	for (pii t : test2)
		cout << t.first << ' ' << t.second << '\n';
}

// 출력 결과 : { 1,9 },{ 1,1 },{ 2,1 }
  • sort()당한 test는 원소의 개수가 많아지면 안정성이 깨질 수 있다.
  • stable_sort()당한 test2는 원소의 개수가 많아져도 안정성이 유지된다.
  • compare을 인자로 전달 안 하면 pair의 기본 비교자 때문에 알아서 두번째 요소까지 비교하여 정렬된다.


⚔️ 백준

  • 17845 수강 과목 : 배낭 연습

14569 시간표 짜기

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;

int main()
{
	int N, k, t, M, p, q;
	cin >> N; // 총 과목의 수
	vl lect = vl(N+1);
	for (int i = 0; i < N; i++)
	{
		int tCnt; cin >> tCnt;
		for (int j = 0; j < tCnt; j++)
		{
			int onLect; cin >> onLect;
			lect[i] |= (1LL << onLect);
		}
	}
	cin >> M; // 학생 수
	for (int i = 0; i < M; i++)
	{
		ll schedule = 0;
		cin >> p; // 비어있는 교시 수
		while (p--)
		{
			cin >> q; // 비어있는 교시
			schedule |= (1LL << q);
		}
		int cnt = 0;
		// 비어있는 교시는 1로 표시됨, 과목 별 필요한 교시도 1로 표시됨
		// 두 숫자를 비트 연산 & 했는데, 결과가 필요한 교시와 같으면 cnt++
		for (ll l : lect)
		{
			if ((l & schedule) == l) cnt++;
		}
		cout << cnt-1 << '\n';
	}
	cout << ' ';
}

비트마스킹 연습



📖 윤성우의 열혈 TCP/IP 소켓 프로그래밍

Chapter 17 select보다 나은 epoll

17-1 epoll의 이해와 활용

select는 성능 구리다. 리눅스에선 대신 epoll을 사용한다.

  • select는 모든 파일 디스크립터를 대상으로 반복문 돌기 때문
  • select 함수 호출할 때마다 인자로 관찰대상 정보 제공해야 하기 때문

운영체제에 관찰 대상 정보 매번 전달하는게 반복문보다 성능 병목

  • 운영체제에게 관찰 대상 정보 한 번만 알려주고, 변경 있을 때만 변경 사항만 알려주게 하면 개선 가능
  • 리눅스에선 이를 epoll이라 하고, 윈도우에선 IOCP라 한다
  • 성능 상관 없고, 운영체제 이식성 좋아야 한다면 select 쓰는 것도 좋음

epoll 구현에 필요한 함수와 구조체

epoll 장점

  • 상태 변화 확인하기 위한 전체 파일 디스크립터 반복문 없어도 됨
  • select에 대응되는 epoll_wait() 호출 시 관찰 대상 매번 전달 필요 없음

epoll 서버 구현 필요한 함수

  • epoll_create() : epoll 파일 디스크립터 저장소 생성
  • epoll_ctl() : 저장소에 파일 디스크립터 등록 및 삭제
  • epoll_wait() : 파일 디스크립터 변화 대기

select에선 fd_set 변수 변화를 통해 상태 변화 확인하지만,
epoll에선 epoll_event 구조체 기반으로 상태변화 발생한 파일 디스크립터가 별도로 묶인다
(epoll_event는 이벤트 유형 등록할 때도 사용된다)

epoll_create()

  • size 매개변수는 완전히 무시됨
  • 생성된 리소스는 파일 디스크립터 반환. 나중에 close() 해줘야 함.

epoll_ctl()

  • 2번째 인자 전달 가능 상수
    • EPOLL_CTL_ADD : 파일 디스크립터를 epoll 인스턴스에 등록
    • EPOLL_CTL_DEL : 파일 디스크립터를 epoll 인스턴스에서 삭제
    • EPOLL_CTL_MOD : 등록된 파일 디스크립터의 이벤트 발생상황 변경
  • 호출 예시
    • epoll_ctl(A, EPOLL_CTL_ADD, B, C) : epoll 인스턴스 A에, 파일 디스크립터 B를 등록하되, C를 통해 전달된 이벤트의 관찰을 목적으로 등록
    • epoll_ctl(A, EPOLL_CTL_DEL, B, NULL) : epoll 인스턴스 A에서 파일 디스크립터 B를 삭제한다

epoll_wait() : 이벤트 발생하면 두번째 인자로 전달한 버퍼에 이벤트 발생한 파일 디스크립터 묶인다

	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");

	epfd = epoll_create(EPOLL_SIZE);
	ep_events=malloc(sizeof(struct epoll_event)*EPOLL_SIZE);

	event.events=EPOLLIN; // 수신할 데이터가 존재하는 상황
	event.data.fd=serv_sock;
	epoll_ctl(epfd, EPOLL_CTL_ADD, clnt_sock, &event);
	
	while(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;
				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);
				}
			}
		}
	}
	close(serv_sock);
	close(epfd);
  • 소켓 만든 후에 epoll에 등록
  • epollwait한 후에
    • 서버 소켓에 뭔가 잡혔으면 accept
    • 연결 소켓에 뭔가 잡혔으면 읽거나 연결 종료

17-2 레벨 트리거와 엣지 트리거

레벨 트리거 : 입력 버퍼에 데이터 남아있는 동안 계속해서 이벤트 등록됨
엣지 트리거 : 입력 버퍼 데이터 수신됐을 때 한 번만 이벤트 등록

레벨 트리거 기반 서버

위 예제 코드 for문 앞에 puts("return epoll_wait")를 넣고, 버퍼 크기를 4로 줄이면 이벤트가 여러 번 발생한다.
기본적으로 레벨 트리거 방식이라, 버퍼 크기에 맞추어 이벤트가 나누어 발생한다

클라 소켓을 event.events=EPOLLIN|EPOLLET으로 바꾸면 엣지 트리거로 바꿀 수 있다.
대신 버퍼에 남아있는 나머지 결과는 출력하지 못한다.

엣지 트리거 기반 서버

엣지 트리거 구현에 있어 필요한 2가지

변수 errno를 이용한 오류 원인 확인 방법

  • 리눅스 소켓 관련 함수는 오류 나면 -1 반환
  • 오류 관련 추가 정보는 전역 변수 errno 확인하면 됨
  • errno 접근하려면 errno.h 포함해야됨
  • 오류 발생 시 errno에 저장되는 값이 달라짐
  • 지금 알아야 할 것
    • read()는 입력 버퍼에 데이터 비었을 때 -1을 반환
    • 이때 errno에는 상수 EAGAIN 저장됨

Non-blocking IO를 위한 소켓 특성 변경 방법

  • fcntl() : 파일 특성 변경 및 참조
  • 인자로 F_GETFL 전달하면 첫 번째 인자로 전달한 파일 디스크립터 특성 정보를 int로 얻을 수 있다
  • 인자로 F_SETFL 전달하면 특성 정보 변경할 수 있다
  • 파일 넌-블로킹 모드 변경 방법
    • int flag=fcntl(fd, F_GETFL, 0); : 기존 특성 가져온 뒤
    • fcntl(fd, F_SETFL, flag|O_NONBLOCK); : NONBLOCK 추가하여 재설정
    • 이제 read, write 호출해도 데이터 유무 관계없이 블로킹 안된다

클라 소켓을 non-blocking 모드로 설정하고,
버퍼에 아무것도 안 남을 때까지 while문으로 read한다.

		puts("return epoll_wait");
		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);
				setnonblockingmode(clnt_sock);
				event.events=EPOLLIN|EPOLLET;
				event.data.fd=clnt_sock;
				epoll_ctl(epfd, EPOLL_CTL_ADD, clnt_sock, &event);
				printf("connected client: %d \n", clnt_sock);
			}
			else
			{
				while(1)
				{
					str_len = read(ep_events[i].data.fd, buf, BUF_SIZE);
					if(str_len==0)
					{
						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);
						break;
					}
					else if(str_len < 0)
					{
						if(errno==EAGAIN) break;
					}
					else {
						write(ep_events[i].data.fd, buf, str_len); // echo!
					}
				}
			}
		}

이번 예제는 123456789 보내면 이벤트가 한 번만 발생하는 대신,
while문을 계속 돌면서 read가 non-blocking으로 소켓을 확인한다
데이터 다 없어지면 (EAGAIN 뜨면) while문 탈출한다.
non-blocking 안 해두면 EAGAIN을 확인할 수가 없어서 탈출 불가.

(그리고 이번 예제도, 저번 예제도 이벤트 횟수만 다른거지, 수신 측에선 echo를 전부 받는다.
wirte() 자체는 4개씩 나누어서 하지만, 수신 측에서 read()할 때 알아서 합쳐지기 때문이다.)

엣지 트리거의 장점 : 데이터의 수신과 데이터 처리 시점을 분리할 수 있다. 레벨 트리거는 데이터 남으면 계속 깨워서 처리 미루기 곤란.



profile
lililllilillll
너 정말 **핵심**을 찔렀어
이전 포스트

251024

다음 포스트

251026

0개의 댓글