문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 언뜻 보면 백트래킹 문제 같은데, 그리디 문제였다. 이 문제의 경우, 만약에 '-'연산자가 하나라도 있으면 뒤에 나오는 피연산자(숫자)들을 모조리 빼주는 것이 최적의 방식이었다. 다음의 예시를 보자. 55-50+40 -> 55-(50+40) = 55-50-40 = -35 55-50+40-20+30 -> 55-(50+40)-(20+30) = 55-55-40-20-30 = -85 이 ..
문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 그리디 알고리즘 문제였다. n이 최대 100,000이므로 관건은 O(nlogn) 안에 풀어야 한다는 것이었는데, 이 문제의 경우 O(n) 안에 풀이가 가능했다. "첫 번째 점수인 서류심사 성적순으로 정렬을 하고, 두 번째 점수인 면접 성적을 비교해서 합격자를 결정하면 된다."라는 기본적인 아이디어는 모두 비슷할 것이다. 하지만 두 번째 점수인 면접 성적을 비교하는 ..
동기(Synchronous)와 비동기(Asynchronous) 동기/비동기는 주로 어플리케이션에서 자주 다뤄지는 개념이며, 다음 작업이 요청되는 시간과 관련되어 있다. 동기(Synchronous) 현재 작업의 응답이 끝남과 동시에 다음 작업이 요청된다. 함수를 호출하는 곳에서 호출되는 함수가 결과를 반환할 때까지 기다린다. 작업 완료 여부를 계속해서 확인한다. 비동기(Asynchronous) 현재 작업의 응답이 끝나지 않은 상태에서 다음 작업이 요청된다. 함수를 호출하는 곳에서 결과를 기다리지 않고, 다른 함수(callback)에서 결과를 처리한다. 작업 완료 여부를 확인하지 않는다. 동기 예시 function run(a, b) { return a + b } const result = run(1, 2);..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 처음엔 그래프만 보고 바로 너비 우선 탐색으로 풀었는데, 시간초과가 떴다. 다시 보니 치킨 거리를 구하는 데엔 O(1)로 충분하기 때문에 그래프 탐색이 필요없는 문제였다. 입력을 받을 때 집(1)과 치킨집(2)의 좌표를 저장한다. 조합을 이용해 m개의 치킨집(2)을 선택한 후, 각 집마다의 치킨 거리를 구한다(여기선 m이 작기 때문에 min함수를 이용했다). 그 다..
문제 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 분류는 구현으로 되어 있었는데, 그래프 탐색으로도 풀 수 있는 문제였다. 문제의 힌트가 중요한데, 친구의 친구까지만 결혼식에 초대가 가능하다는 점이다. 따라서 1번 노드(상근이)를 시작으로 너비 우선 탐색을 진행하면서 거리(dist)가 2 이하인 노드들만 개수를 세주면 된다. 코드 import sys from collections import defaultdict, deq..
