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 ] 14499번 : 주사위 굴리기문제 : https://www.acmicpc.net/problem/14499[ 문제 ]크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 24 1 3 5 6주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다.지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 ..

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

[ BOJ ] 1991번 : 트리 순회문제 : https://www.acmicpc.net/problem/1991[ 문제 ]이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.[ 입력 ]첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 ..

ㅠ[ 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..