J_3s

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

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

[ BOJ ] 7585번 : Brackets문제 : https://www.acmicpc.net/problem/7585[ 문제 ]As a C/Java programmer, you will be used to dealing with brackets. For the purpose of this problem, we will consider three type of bracket, round (), square [] and curly {}. As you know, every opening bracket must have a corresponding closing bracket, and brackets must be correctly nested. This problem will give you some pi..

[ BOJ ] 11899번 : 괄호 끼워넣기문제 : https://www.acmicpc.net/problem/11899[ 문제 ]심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다.(()(()))()()그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다.(() (( )))() ()크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.)))()승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들..