알고리즘 (2020 : 08 : 10 ~ )/트리 (15) 썸네일형 리스트형 [백준 / BOJ] 15681 트리와 쿼리 (Java) 문제 출처 : 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 양방향 트리의 정점의 수 N 루트 번호 R 쿼리의 수 Q 가 주어진다. 각 쿼리를 입력받았을때, 해당 루트의 서브트리의 노드수를 구하는 문제다. 풀이 노드 N이 100000 쿼리 Q가 100000 이므로, 한 쿼리마다 모든 노드를 탐색하는 방식(완전탐색)으로 구현하면 시간초과가 난다. 쿼리를 입력받기전에, 한 정점을 루트.. [백준 / BOJ] 15591 MooTube (Silver) 문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 농부 존은 MooTube라는 동영상 공유 서비스를 만들었다. MooTube의 동영상들은 트리구조로 연결되어있고, 동영상 Vi를 볼때, Vi와 연결된 모든 동영상들중에 유사도가 Ki이상인 동영상들을 추천해준다. 이때, 동영상 Vi와 다른 동영상 Vj의 유사도는 Vi와 Vj 를 연결하는 경로의 최소 유사도이다. 소가 Vi동영상을 시청하.. [백준 / BOJ] 1135 뉴스 전하기 문제 출처 : https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다. 회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다. 모든 직원들은 모두 민식이의 간접,직접적인 부하이다. 모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다. 모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다. 풀이 그리디로 풀은 문제다. 직.. [백준 / BOJ] 5639 이진 검색 트리 문제 출처 : www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리를 전위 순회한 결과가 주어졌을때, 트리를 후위순회한 결과를 출력하는문제다. 풀이 문제는 간단한데 입력은 그렇지 않았다.. 처음에는 완전이진트리를 생각하고 구현하다가 런타임에러가 떴다(배열 범위 초과). 다시 잘 읽어보니 노드가 한쪽으로 쭉 늘어날수있었다. 완전이진트리로 구현할려면, 배열의 범위가 2^10000 까지 가야해서 이 방법으로는 풀수없다. 런타임에러 코드 더보기 런타임에.. [백준 / BOJ] 1991 트리 순회 문제 출처 : www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리가 주어졌을때, 해당 트리를 전위순회, 중위순회, 후위순회한 결과를 출력하는 문제다. 풀이 트리 탐방자체는 어렵지않았는데, 입력을 트리구조로만드는게 난해한 문제였다. (순회 문제를 푼게 아니라 트리구조를 만드는 문제를 푼느낌...) 기본적인 트리구조(idx*2, idx*2+1)에 익숙해져서인지 처음엔 그런방향으로 구현하는걸 생각했었다. 입력이 위에서부터 너비우선탐색으로 입력되는것 같아서 .. [백준 / BOJ] 19581 두 번째 트리의 지름 문제 출처 : www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리가 주어졌을때 두번째로 긴 트리의 지름을 구하는 문제다. 풀이 트리의 지름을 구하는 임의의 지점에서 가장 먼지점 A를 찾고, A에서 가장 먼 지점 B를 찾으면 된다. 이걸 좀더 응용하면 되는데, 1. 임의의 지점 O 에서 가장 먼지점 A를 찾고, A에서 두번째로 먼 지점 B를 찾는다. 2. 임의의 지점 O 에서 두번째로 먼지점 C를 찾고, C에서 가장 먼 지점 D를 찾는다. 두 값.. [백준 / BOJ] 2233 사과나무 문제 출처 : www.acmicpc.net/problem/2233 2233번: 사과나무 문제 사과나무는 나무(tree)의 일종으로, 각각의 정점에 정확히 한 개의 사과가 있고, 모든 내부 정점(자식이 있는 정점)이 최소 두 개의 자식을 갖는 나무이다. 예를 들면 아래의 그림은 사과나무 www.acmicpc.net 정점의 개수와 벌레가 만드는 이진수를 입력받고, 정상적인나무를 최소화한상태로 썩은나무를 모두 없애는 정점을 구하는 문제다. 풀이 그래프 구조를 만들필요없이 해당노드의 등장 순서만 알고있다면 풀리는 문제다. 입력을 보면, 벌레가 만드는 이진수가 깊이우선탐색의 순서와동일한것을 알수있다. (해당 노드에서 끝까지 간후 더이상 갈수없을경우, 부모로 올라감) -이진수에 따라 자식과 부모관계를 만들어주기위해.. 이전 1 2 다음