Partially Committed

15681번: 트리와 쿼리 (acmicpc.net) 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리에서 DP 를 사용하는 입문 문제! 문제는 단순하다. Q 개의 쿼리가 들어오면 이에 따른 출력을 해주면 된다. 쿼리는 노드 V 에 대한 서브 트리를 구성하는 노드들의 개수를 반환하는 것이다. 입력 조건을 보면, 트리의 크기도 상당히 큰 편이기도 하지만, 쿼리가 최대 100,000 개가 들어올 수 있다. 노드 V 에 대한 서브 트리를 구성하는 노드 ..

최근 풀었던 문제 중에 가장 재밌었던 것 같아서 오랜만에 백준 포스팅 😊 9019번: DSLR (acmicpc.net) 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 간단하게 요약하자면 초기값 A 목표값 B 가 주어지면 아래 4가지 연산을 통해서 B로 도달할 수 있는 경로를 출력하는 것이다. D 연산: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S 연산: S 는 n..

1162번: 도로포장 (acmicpc.net) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라 + dp 이전에 **미확인 도착지 문제**를 통해 다익스트라의 기본 형태를 구현했었다. 도로포장은 다익스트라에 dp 를 곁들인 문제다 😐 문제를 간단히 요약하면, 양방향 그래프가 주어지면 1번 노드에서 N 번 노드로 최단 경로로 움직여야 한다. 이때, 좀 더 빠르게 움직이기 위해 **도로 포장** 을 k 번 수행할 수 있다. 도로 포장을 수행하면, 해당 도로의 가중치를 ..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 재귀는 항상 어려운 것 같다.. 🥺 위 문제는 조금 특이한데, InOrder Traverse 와 PostOreder Traverse 가 주어졌을 때 PreOrder Traverse 를 출력하는 것이 요구 사항이다. 음.. 일단 Tree 의 순회에서 기준이 되는 것은 Root 노드이다. InOrder 와 PostOrder 는 주어지는데, 이로부터 Root 노드를 어떻게 찾을 수 있을까? PostOrder 는 left - ri..