Tree
-
백준 2263 트리의 순회Algorithm/BOJ 2021. 3. 26. 16:19
출처: www.acmicpc.net/problem/2263 분류: 트리 접근방식 트리 순회 방법의 특성을 잘 이용해 해결했어야 하는 문제였습니다. 기억해야 할 특징은 다음과 같습니다. 1. post-order는 왼쪽 - 오른쪽 - 루트 순으로 탐색하므로 배열의 마지막은 루트노드가 됩니다. 2. in-order 는 root를 기준으로 왼쪽은 left, 오른쪽은 right 서브트리로 분리됩니다. post-order를 통해 root 노드를 찾았다면, in-order의 시작부터 root 까지가 왼쪽, 오른쪽으로 분리되고, 이를 통해 왼쪽, 오른쪽에 몇 개의 노드가 존재하는지 알 수 있습니다. 다시 in-order는 왼쪽 - 오른쪽 - 루트가 순서대로 배치되어 있기 때문에 개수를 통해 in-order에서 어디까지..
-
백준 5639 이진 검색 트리Algorithm/BOJ 2021. 3. 26. 14:19
출처: www.acmicpc.net/problem/5639 분류: 트리 접근방식 pre-order 결과가 들어오면 이 트리의 post-order 검색의 결과를 출력하는 문제였습니다. pre-order의 결과를 놓고 보면 첫 번째가 root, root+1 부터 처음으로 root보다 큰 값이 나오는 위치까지가 Left 그 다음이 Right 트리가 됩니다. 우리가 원하는 결과인 post-order는 왼쪽부터 탐색하기 때문에 루트를 타겟으로 이분탐색으로 UpperBounds를 찾아서 왼쪽 -> 오른쪽 -> 루트 를 반복적으로 돌려주면 원하는 결과를 얻을 수 있습니다. 처음엔 입력 받을 때마다 루트부터 위치를 찾아 트리를 만들어 나가는 방식으로 접근했었는데 이렇게 하니까 시간초과가 났습니다. c++로는 이런 식으..
-
백준 1068 트리Algorithm/BOJ 2021. 3. 25. 16:49
출처: www.acmicpc.net/problem/1068 분류: 트리 접근방식 전형적인 트리 문제였습니다. 주어진 대로 부모자식을 쭉 연결한 다음 dfs나 bfs 방식으로 탐색하다가 삭제해야 할 노드를 만나면 건너뛰는 방식으로 하면 해당 요구조건에 맞게 빠르게 해결할 수도 있으나 (많은 분들이 그렇게 푸신 것 같습니다.) 저는 실제 트리에 가깝게 해결해보고 싶어서 실제로 해당 노드와 그 자식 노드들을 제거해주는 방식으로 해결해봤습니다. 처음에는 Node, Tree 클래스를 각각 만들어서 처리해서 풀었다가 별도의 Tree 클래스 없이 루트노드만 가지고 해결하도록 개선해봤는데요, n만큼 임시 배열에 노드를 만들어두고 -1을 만나면 treeNode의 변수로 저장해두고 연결과 제거를 모두 끝내고 나면 임시 배..
-
백준 1967 트리의 지름Algorithm/BOJ 2021. 1. 21. 15:14
출처: https://www.acmicpc.net/problem/1967 분류: 트리 접근방식 문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다. root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면 leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다. root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :) 해결방법 dfs를 돌려서 루트에서 가장 먼 노드를 찾고, 그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다. 그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다. 트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢 im..
-
TreeComputer Science/DataStructure 2021. 1. 14. 18:00
- 객체간의 계층적인 관계를 나타낸다 - 빠르고 효율적으로 탐색할 수 있다 - 데이터의 정렬된 형태를 보여준다 - 사이클이 없는 그래프 - 텍스트의 prefix 매칭을 빠르게 할 수 있다. ex) - 회사나 정부의 조직 구조 - 나라, 지방, 시•군별 등 계층적인 데이터 - 인덱스 오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다. Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..