트리
-
BOJ) 트리 (1068 번)알고리즘/백준 2021. 1. 29. 17:08
트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다. 먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다. 이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음) 다음으로..
-
BOJ) 트리의 지름 (1167 번)알고리즘/백준 2021. 1. 29. 16:56
트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 이전에 포스팅했던 트리의 지름과 조금 다르게 풀었다. 먼저, 트리기 때문에 어떤 지점에서 시작해도 특정 지점까지 모두 도달할 수 있다는 특징이 있다. 이 말인 즉, 가장 멀리있는 한 특정 지점을 찾을 수 있다는 말이 된다. 위의 조건에 따라, 1에서 가장 먼 vertex를 찾아주었다. 이후, 해당 vertex에서 가장 먼 거리에 있는 지점을 찾으며 최댓값을 갱신해주었다. (만약, 1 -> 찾은 지점이 가장 먼 거리라면, 찾은 지점 -> 1..
-
BOJ) 트리의 지름 (1967 번)알고리즘/백준 2021. 1. 19. 00:25
트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이진 트리인줄 알고 시간을 조금 낭비했다. 왜 틀렸는지 잘 모르겠어서 게시판 글을 읽다가, 이진 트리가 아닌 케이스를 보고 해결했다. 풀이 풀이 방법은 간단하다. 각 tree의 연결 정보를 ArrayList에 담아두고 (n이 최대 10,000가 되는데, 배열로는 메모리 초과가 발생할 것임) dp라고 선언한 배열을 통해 각 노드에서 자식 노드의 최대 weight를 메모이제이션 해주었다. 그리고 답을 찾을 때는 우선순위 큐를 통해, ..
-
BOJ) 트리 순회 (1991 번)알고리즘/백준 2021. 1. 19. 00:18
트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이진 트리에 대한 개념을 알고 있다면 어렵지 않은 문제였다. 다만, 트리의 입력 정보가 포화 이진 트리인지, 완전 이진 트리인지, 정 이진 트리인지 보장해주지 않는다. (트리에 대한 개념 설명은 이전 자료구조의 트리 포스팅을 참고) 그래서, 해당 노드의 값에 따라 정보를 입력해주어야 한다는게 핵심이었던 것 같다. 위의 입력 문제를 해결하기 위해서 append라는 메소드를 만들었다. node의 vertex 값이 일치하는 node를 찾아 left, ..
-
TreeCS 지식/자료구조 2021. 1. 14. 15:46
Tree Tree 스택이나 Queue와 다르게 비선형 & 계층적 관계 자료 구조 트리는 표현에 집중한다 Node, Edge, Root Node, Terminal Node(Leaf Node, 단말 노드) => 하위에 다른 노드가 없는 최하위 노드, Internal Node(내부 노드, 비단말 노드) => 단말 노드를 제외한 모든 노드(루트 포함) Binary Tree 루트 노드를 중심으로 두 개의 서브 트리를 가지는 자료구조 서브 트리 또한 모두 이진 트리여야함 (공집합 포함) 트리의 depth를 숫자로 매겨서 레벨(Level)이라고 함( 0부터 시작 left child key) 부모의 키가 오른쪽 자식 노드의 키보다 작다. (parent key < right child key) 서브 트리도 모두 이진 탐..