# 트리
[BOJ 2250] 트리의 높이와 너비
BOJ 2250 트리의 높이와 너비 문제풀이 트리를 구현해서 노드를 삽입할 때 마다 각 노드의 열 위치를 업데이트하는 방식을 생각하였는데 구현이 너무 어려웠다. 그런데 열 번호를 중심으로 노드를 보니 열 번호의 순서와 중위 순회시에 순회하는 순서가 같다는 사실을 알게되었다. 중위 순회를 통해서 각 레밸의 가장 왼쪽과 가장 오른쪽의 열 번호를 구해서 그 차...
2019.09.18 Tree, Binary Search Tree
Tree image.png 1. 노드(node) 가 하나 이상의 자식을 가지면 tree 라고 한다. > 1. 한 개의 루트 노드만이 존재 > 2. 모든 자식 노드는 한 개의 부모 노드만을 가짐 > 3. 계층 모델 > 4. 부모 - 자식 관계 > 5. 비순환 그래프 && 방향 그래프 (top - bottom) > 6. 그래프의 한 종류 2. 트리의 구성 ...
펜윅트리 문제1 삽입정렬 시간 재기
문제 풀이 > 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 > 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅 트리를 만들고, 배열의 첫 원소부터 하나씩 갱신하면서 그 원소보다 큰 원소의 개수를 구...
펜윅트리
펜윅트리 > 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다. image.png 펜윅트리의 구현 > 펜윅트리를 실제로 구현하기 위해서는 이진수를 활...
트리 - 구간트리 문제1 족보 탐험
image.png 문제 파악 > 트리의 최소 공통 조상을 구해서 트리의 노드에서 노드까지 가는 거리를 구하는 문제이다. 직관적인 방식을 떠올리면 시간 복잡도가 너무 커지게 되고, 트립을 쓰게 되면 구현이 어렵고 구간 트리를 활용한 문제 취지를 벗어나는 것 같아서 구간 트리를 사용하는 방법을 떠올려 보려고 했지만 떠오르지 않았다. 문제 풀이 구간 트리...
트리 - 구간 트리
구간 트리란 image.png > 어떤 배열이 주어졌을 때 그 배열의 특정 구간의 최소값을 알고싶다고 하자. 만약 배열 그 자체로 접근하고자 하면 구간에 속한 원소들을 일일이 확인해야 하기 때문에 n의 시간복잡도를 필요로 한다. 이를 효율적으로 수행하기 위한 구조가 구간 트리이다. 구간 트리는 특정 구간의 최소값을 컨테이너에 담고 있는데 담고 있는 구조...
트리 - 트립 문제1 삽입 정렬 뒤집기
image.png 문제 파악 > 삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이너를 트립으로 두면 문제를 NlogN의 시간 복잡도로 해결할 수 있다. 숫자를 하나씩 원래...
트리 - 트립
트립이란 > 이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간단한 구조로 균형성을 보장하는 이진 검색 트리가 트립이다. > C++의 표준 라이브러리에...
트리 - 이진 검색 트리 문제1 - NERD2
image.png 문제 접근 > 값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이 들어오면 그 값보다 큰 값을 가진 인덱스들에 대해 라면의 값을 확인하려고 했다. set안...
트리 - 이진 검색 트리
이진 검색 트리란 image.png > 이진 트리란 노드의 자식을 최대 두 개까지만 가질 수 있는 트리를 말한다. 이진 검색 트리는 이진 트리의 왼 쪽 자식을 부모 노드보다 작은 값, 오른 쪽 자식을 부모 노드 보다 큰 값으로 두어 만들어진 트리를 말한다. > 이진 검색 트리는 효율적인 연산들을 제공한다. 이진 검색 트리는 어떤 값을 찾을 때 연결 리...
트리 문제2 - 요새
image.png 문제 파악 > 원형으로된 요새의 벽을 가장 많이 통과 하는 경우를 구하는 문제이다. 요새의 벽 끼리 겹치는 경우는 없기 때문에 요새가 겹치는 지를 파악하는 아이디어는 쉽게 생각났으나 트리 자료 구조를 표현하는 방식에서 시간이 너무 오래 걸려 포기했다. 가장 많이 겹치는 구간을 구하는 방법은 트리 구조로 된 모습에서 가장 긴 리프에서 리...
트리 - 문제1 트리 순회 순서 변경
image.png 문제 풀이 > 전위 표기의 경우 루트 노드가 반드시 맨 앞에 오고 중위 표기에서 그 루트 노드를 기준으로 양 옆을 왼쪽 subtree 오른쪽 subtree로 나눠서 크기가 1이 될 때까지 재귀적으로 호출하는 간단한 문제이다. 먼저 끝난 함수일 수록 후위 표기의 경우 먼저 등장하므로 후위 표기로 표현하는 것은 간단하다.
그래프 DFS - 문제1 감시 카메라
문제 파악 image.png > 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...
백준 1068 트리
문제 첫재 줄에 n이 주어집니다. 정점의 개수가 n개인 트리이며, 트리의 정점은 0번부터 n-1까지 입니다. 둘째 줄에 각 정점의 부모 정점의 정보가 주어집니다. (-1이면 루트 노드 입니다.) 셋째 줄에 지울 노드 한개가 주어집니다. n(1 <= n <= 50) 정점의 수 시간 제한 2초 문제 링크 접근 과정 1. 탐색 사실 어려운 문제는 아닙니다. ...