전체 글

백준 20955 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 전 나의 생각 뉴런과 시냅스가 주어질 때 모든 뉴런이 트리 구조가 될 때 까지의 연산 횟수를 구해야 한다. 조건 2 ≤ N ≤ 100,000 1 ≤ M ≤ min(N × (N – 1) / 2, 100,000) 1 ≤ u, v ≤ N u ≠ v 두 뉴런 사이에는 최대 1개의 시냅스만 존재한다. 과정 문제를 보면 뉴런은 노드고, 시냅스는 간선이라는 것을 알 수 있다. 이 문제의..

백준 1068 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 전 나의 생각 트리가 주어지고, 특정 노드를 삭제 했을 때 나올 수 있는 리프노드의 총 개수를 구해야 한다. 조건 - N은 50보다 작거나 같은 자연수 - 만약 부모가 없다면 (루트) -1이 주어진다. 과정 문제의 이름이 트리인 만큼 기본적인 트리의 풀이 방법인 DFS, BFS..등을 사용해서 리프노드에 도착했을 경우 최종값을 증가하며 풀어나가면 된다. 하지만 문제에서 요..

백준 22856 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 전 나의 생각 노드가 N개인 이진 트리가 주어질 때, 이를 중위 순회와 유사하게 순회하는 유사 중위 순회의 방식으로 순회하며 이동한 거리를 구해야 한다. 조건 1 ≤ N ≤ 100,000 1 ≤ a, b ≤ N 과정 유사 중위 순회의 방식음 다음과 같다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다. 그렇지 않고 현재 위..

백준 1240 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 풀이 전 나의 생각 N개의 노드로 이루어진 트리와 M개의 두 노드 쌍을 입력 받을 때 두 노드 사이의 거리를 구해내야 한다. 조건 2 ≤ N ≤ 1000 1 ≤ M ≤ 1000 트리 상에 연결된 두 점과 거리는 10000이하인 자연수이다. 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다. 과정 조건을 통해 알 수 있는 것은 ..

백준 15681 https://www.acmicpc.net/problem/15681 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 풀이 전 나의 생각 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력해야 한다. 조건 - (2 ≤ N ≤ 10^5, 1 ≤ R ≤ N, 1 ≤ Q ≤ 10^5) - (1 ≤ U, V ≤ N, U ≠ V) - (1 ≤ U ≤ N) 과정 입력에 관한 조건들만 존재하기 때문에 이 부분은 넘어가고 이 문제에서 중요한 것..

백준 4803 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 전 나의 생각 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성해야 한다. 조건 - n ≤ 500 - m ≤ n(n-1)/2 과정 주어진 조건들은 입출력의 값에 관한 것들이기 때문에 크게 신경쓰지 않아도 된다. 이 문제에서 신경써야할 것은 트리는 사이클이 없는 연결 요소라는 것이다. 그럼 이 문제에서 신경써야 할 부분은 트리의 사이클이 존재하는 부분을..

1. 트리의 순회란? 트리 구조 내의 모든 노드를 방문하기 위한 과정을 말한다. 종류로는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있다. 이러한 순회를 사용하는 이유는 트리 구조에서 데이터 탐색과 출력이 용이해지기 때문이다. 2. 순회 방법 전위 순회 Root - Left - Right (ABDCEFG) 중위 순회 Left - Root - Right (DBAECFG) 후위 순회 Left - Right - Root (DBEGFCA) 전위 순회(Root - Left - Right)를 예시를 들어서 설명하자면 1. Root A노드 시작 (A) 2. Root : A - 왼쪽 자식 노드 B 탐색 (AB) 3. Root : B - 왼쪽 자식 노드 D 탐색 (ABD)..

백준 1991 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 전 나의 생각 이진 트리를 입력 받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력해야 한다. 조건 - N(1 ≤ N ≤ 26) - 항상 A가 루트 노드가 된다. 과정 노드는 26개 만들 수 있기 때문에 노드의 값을 담을 배열은 데이터 타입 int, 크기를 27로 설정해준다. A가 항상 루트 노드가 되기 때문에 전위, 중위, 후위 순회의 첫 시작은 무조건 A다. ..