오늘도 밤이야

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) -..