J_3s

[ BOJ ] 16397번 : 탈출문제 : https://www.acmicpc.net/problem/16397[ 문제 ]홍익이는 홍익대학교 프로그래밍 경진대회의 출제진이다. 홍익이는 새벽에 문제를 만들던 도중 뒤통수에 느껴지는 고통과 함께 정신을 잃었다.홍익이는 좁은 방에서 눈을 떴다. 주변을 살펴보니 벽면에는 LED로 된 다섯 자리 십진수 N이, 그 옆에 T, G라는 알파벳과 함께 또 다른 정수 두 개가 쓰여 있었고, 벽 앞에는 버튼 A, B 두 개가 있었다.버튼을 이리저리 눌러보던 똑똑한 홍익이는 어떻게 해야 방을 탈출할 수 있을지 금방 눈치챘다.버튼과 수에 대해 홍익이가 알아낸 것은 다음과 같다.버튼 A를 누르면 N이 1 증가한다.버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자..

[ BOJ ] 17352번 : 여러분의 다리가 되어 드리겠습니다!문제 : https://www.acmicpc.net/problem/17352[ 문제 ]선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.어제까지는 그랬다. "왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다!안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다.일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다. 그런데 그 ..

[ BOJ ] 11725번 : 트리의 부모 찾기문제 : https://www.acmicpc.net/problem/11725[ 문제 ]루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.[ 입력 ]첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.[ 출력 ]첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.[ 문제 접근 및 풀이 ]DFS를 통해서 now라는 변수로 현재 노드를 나타냈으며양방향 간선이기에 현재 노드에서 부모 노드로 갈 수도 있으므로 현재 노드의 부모 노드도포함시켜 사이클이 도는 것을 방..

ㅠ[ BOJ ] 1240번 : 노드사이의 거리문제 : https://www.acmicpc.net/problem/1240[ 문제 ] $N$개의 노드로 이루어진 트리가 주어지고 $M$개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.[ 입력 ]첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.[ 출력 ] $M$개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. [ 제한 ]$2≤N≤1\,000$ $1≤M≤1\,000$ 트리 상에 연결된 두 점과 거리는 $10\,000$ 이하인 자연수이다..

[ BOJ ] 15681번 : 트리와 쿼리문제 : https://www.acmicpc.net/problem/15681[ 문제 ]간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.[ 입력 ]트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.이어 Q..

[ BOJ ] 13244번 : Tree문제 : https://www.acmicpc.net/problem/13244[ 문제 ]One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.Trees are the subset of graphs that have the following 3 properties: It is connected: for every node you can reach every other node following edges.If a..

[ BOJ ] 3584번 : 가장 가까운 공통 조상문제 : https://www.acmicpc.net/problem/3584[ 문제 ]루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장..

[ BOJ ] 10451번 : 순열 사이클문제 : https://www.acmicpc.net/problem/10451[  문제  ]1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다.예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다.또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.순열을 배열을 이용해 \(\begin{pmatrix} 1 & \dots & i & \dots &n \\  \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix..