전체 글 썸네일형 리스트형 BOJ 16074 Mountaineers (병렬 이분 탐색) https://www.acmicpc.net/problem/16074 16074번: Mountaineers The Chilean Andes have become increasingly popular as a destination for backpacking and hiking. Many parts of the Andes are quite remote and thus dangerous. Because of this, the Ministry of Tourism wants to help travelers plan their trips. In particular, t www.acmicpc.net 지형이 주어지고, 어느 두 지점을 이동하는 경로 중 경로상 최고 고도를 최소화하는 문제이다. 쿼리의 개수가 5만개 이므.. 더보기 BOJ 12771 Oil (ACM-ICPC 2016 WF) https://www.acmicpc.net/problem/12771 12771번: Oil The first line of input contains a single integer n (1 ≤ n ≤ 2 000), which is the number of oil deposits. This is followed by n lines, each describing a single deposit. These lines contain three integers x0, x1, and y giving the deposit’s position as www.acmicpc.net 직선을 하나 그어, x 축에 수평한 선분을 최대한 많이 지나가게 만드는 문제이다. (지나가는 선분의 합을 최대화) 직선이 선분의 끝에 닿아도 지나.. 더보기 BOJ 12766 지사 배정 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/12766 12766번: 지사 배정 입력의 첫줄은 4개의 정수 n, b, s, 그리고 r로 이루어진다. n (2 ≤ n ≤ 5 000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50 000)은 도로의 수를 www.acmicpc.net 방향그래프의 정점에 위치한 그래프들을 S개의 그룹으로 묶어, 한 그룹내에서 모든 지사들 사이에서 통신을 할 때, 총 통신비용을 최적화 하는 문제이다. 두 지사 사이의 통신은 항상 본부를 거쳐서 지나가야 한다. 따라서 본부 s에서 지사 u까지의 거리 D[s][u], 그리고 지사 u에서 본부 s까지의 거리를 D[u][s] 라고 하면.. 더보기 BOJ 5466 상인 (IOI 2009 Salesman) https://www.acmicpc.net/problem/5466 5466번: 상인 어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부 www.acmicpc.net 문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합. DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기. 위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면, 우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 .. 더보기 BOJ 17399 트리의 외심 https://www.acmicpc.net/problem/17399 17399번: 트리의 외심 첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다. 두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 www.acmicpc.net 일단 각 쿼리에 대해 트리에서 최소 공통 조상(Lowest Common Ancestor)을 log n에 구할 수 있어야 한다. 알고리즘 두 정점 a와 b에 대해, 두 정점의 가운데에 위치한 정점 x를 찾는다. a와 b 거리가 짝수여야 한다. 그렇지 않으면 가운데에 위치한 정점을 정의할 수 없다. 단계 1에서 찾은 정점 x로부터 정점 c까지의 거리를 구한다. x.. 더보기 이전 1 2 3 4 5 6 ··· 36 다음
