오늘도 밤이야

0. 문제https://www.acmicpc.net/problem/1918 간단한 괄호가 포함된 중위 표기식을 후위 표기식으로 변환하는 문제이다. 풀이 시 연산 순서에 주의하여야 한다. 1. 아이디어문제를 보고 떠오른 것은 프로그래밍 언어 파싱 이론에서의 Parse Tree이다. 부모 노드가 연산자, 자식 노드가 피연산자가 되는 트리로, 순회 순서에 따라 전위/중위/후위 표기식으로 읽을 수 있으며, 그에 따른 실제 연산도 가능하다. 트리 구조이기 때문에 피연산자인 자식 노드가 다른 노드의 연산자, 즉 부모 노드일 수 있다.예로 A+B*C-D/E의 Parse Tree를 구성하면 다음과 같다.Post Order 순회 시 ABC*+DE/- 순서로 후위 표기식과 동일하다는 것을 확인할 수 있다.2. 풀이#inc..

0. 문제https://www.acmicpc.net/problem/1865 도로를 양방향 양수 가중치 간선으로, 웜홀을 단방향 음수 가중치 간선으로 치환하면, 그래프에서 음수 사이클이 존재 여부를 확인하는 문제이다. 1. 아이디어최단 거리 알고리즘 중 음수 사이클 존재 여부를 판단하기 쉬운 알고리즘으로 Floyd-Warshall이 먼저 떠올랐다. All-Pair Shortest Path 알고리즘이기 때문에 시간복잡도 면에서 그렇게 효율적이진 않을 수 있으나, 정점의 최대 개수 V가 500개이기 때문에 O(V^3) 알고리즘인 Floyd-Warshall도 시간 안에 동작하고, 구현이 쉽다는 장점이 있다. 2. 풀이bool check_neg_cycle(std::vector> &adjmat, int n){ ..

0. 문제https://www.acmicpc.net/problem/16283 양의 수를 x, 염소의 수를 y라고 할 때, 다음 연립방정식의 해를 구하는 문제이다.$$ \left\{\begin{matrix} x+y=n \\ ax+by=w \end{matrix}\right. $$ 주의할 점은, 양과 염소가 각각 한 마리 이상 있어야하고, 가능한 해가 두 개 이상 있는 경우 혹은 없을 경우 -1를 출력하는 것이다.1. 아이디어 2 ≤ n ≤ 1,000이므로 x+y=n인 쌍을 모두 확인하는 브루트포스 알고리즘으로 해결할 수 있으나, 선형연립방정식을 푸는 문제인만큼 수학적으로 풀어보도록 한다. 행렬을 이용하여 연립방정식의 해를 구하거나, 문제 규칙에 따른 유효성을 검증한다. 2. 풀이위 연립방정식은 행렬을 이용하..

0. 문제https://www.acmicpc.net/problem/11399 각 사람이 돈을 인출 완료하는데 필요한 시간은 (대기 시간) + (해당 사람의 인출 소요 시간)이다. 이 시간의 합이 최소가 되도록 최적화하는 문제이다. 용어 정리를 하자면,(인출을 완료하는데 필요한 시간)은 문제에서 묻는  (대기 시간) + (해당 사람의 인출 소요 시간)이고,(인출 소요 시간)은 문제에서 입력으로 주어지는, 각 사람이 대기를 마치고 나서부터 ATM에서 돈을 인출 완료하기까지, 순수하게 돈을 뽑는데 걸리는 시간이다. 1. 아이디어(대기 시간) + (해당 사람의 인출 소요 시간) 식을 보고 OS 스케줄링 기법을 연상했다.스케줄링 기법 평가 지표에서 Turnaround time은 (Completion Time) -..

*오역이 많을 수 있습니다. 직역과 의역을 섞어 번역되어 있어, 영문 문서를 기본으로 하되 참고하는 정도로 봐주시면 감사하겠습니다.* man page 참조 환경: macOS Big Sur 11.4 Apple clang version 12.0.5 (clang-1205.0.22.11) Target: x86_64-apple-darwin20.5.0 Thread model: posix KQUEUE(2) BSD System Calls Manual KQUEUE(2) NAME kqueue, kevent, kevent64 and kevent_qos -- 커널 이벤트 발생 알림 매커니즘 LIBRARY Standard C Library (libc, -lc) SYNOPSIS #include #include #include i..

kqueue는 BSD 계열에서 지원하는 Event 관리 system call로, Linux 계열에서 select를 개선한 epoll과 비슷하게 사용되고 동작한다. 여러 fd를 모니터링하고, fd에 대한 동작(read, write)이 준비되었는지 알아내는데 사용되어 I/O Multiplexing을 이용하는 서버 프로그램을 작성하는데 사용된다. 0. Concept kqueue는 커널에 할당된 폴링 공간(kernel event queue - kqueue)에 모니터링할 이벤트를 등록하고, 발생한 이벤트를 return받아 Multiple I/O Event를 처리할 수 있도록 도와준다. 이벤트 등록 및 반환은 kevent 구조체를 통해 이루어지며, 구조체 필드로 존재하는 이벤트에 대한 필터, 플래그 등을 이용해 다..

UNIX 환경에서의 대표적인 IPC(프로세스간 통신) 방법 중 하나인 pipe의 특징에 대해서 알아보자. pipe는 단방향으로만 데이터를 전달할 수 있다 pipe는 커널 메모리를 파일로써 접근할 수 있게 해주어, pipe() 사용시 배열로 두 개의 file descriptor를 발급받는다. fd[0]은 input stream, fd[1]은 output stream으로, 부모 프로세스가 fd[1]에 write한 데이터를 자식 프로세스가 fd[0]으로 read 할 수 있다. 이때 반대의 경우는 사용이 불가능하다. 부모 프로세스가 write, 자식 프로세스가 read하는 상황에서 그 pipe를 유지한 채 자식프로세스가 fd[1]에 write할 수 없다. 이런 사용을 막기 위해 pipe 사용 시 각 프로세스에서..

C++ 클래스 구조의 특징인 다중 상속에서 Dreadful Diamond(죽음의 다이아몬드) 구조 문제를 해결하기 위해 가상 상속을 사용하게 되었다. 클래스 상속 구조는 다음과 같이 구성했다. 문제는 D의 복사 생성자를 사용할 때 일어났는데, 받아온 ref 객체를 복사하지 못하고 A의 기본 생성자를 호출하는 문제가 발생했다. D에서 B와 C의 복사 생성자를 호출하고, B와 C에서 A의 복사 생성자를 호출함에도 A의 기본 생성자가 호출되었다. 작성했던 코드는 다음과 같다. #include using namespace std; class A { private: int a; public: A(); A(const A&); virtual ~A(); }; A::A() { cout