트리
-
백준 2250 트리의 높이와 너비Algorithm/BOJ 2021. 6. 4. 14:26
출처: https://www.acmicpc.net/problem/2250 분류: 트리, 중위순회 접근방식 너비가 가장 큰 높이를 구해야하는 문제였습니다. 문제의 그림이 힌트를 주고 있는데요, 가장 왼쪽 노드부터 x가 하나씩 증가하고 있습니다. 중위 순회를 하면 "왼쪽 -> 루트 -> 오른쪽" 순서로 방문하기 때문에 이 순서가 곧 x가 1인 노드부터 차례대로 방문하는 순서입니다. 이 부분까지 이해가 됐다면 구현만 해주면 되는데요! 저는 그냥 중위순회에서 다 처리해버렸습니다. 전역적으로 사용하는 x값을 가지고 다니면서 노드에 넣었으면 1 증가시키는 방식으로 x를 처리했구요 해당 레벨의 최대, 최소 x값을 넣는 배열을 전역적으로 만들어 놓고 최대 최소를 업데이트 시켜줬습니다. func markWhileInOr..
-
백준 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++로는 이런 식으..
-
백준 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 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..