트리

image.png 문제 풀이 > 전위 표기의 경우 루트 노드가 반드시 맨 앞에 오고 중위 표기에서 그 루트 노드를 기준으로 양 옆을 왼쪽 subtree 오른쪽 subtree로 나눠서 크기가 1이 될 때까지 재귀적으로 호출하는 간단한 문제이다. 먼저 끝난 함수일 수록 후위 표기의 경우 먼저 등장하므로 후위 표기로 표현하는 것은 간단하다.

image.png 문제 파악 > 원형으로된 요새의 벽을 가장 많이 통과 하는 경우를 구하는 문제이다. 요새의 벽 끼리 겹치는 경우는 없기 때문에 요새가 겹치는 지를 파악하는 아이디어는 쉽게 생각났으나 트리 자료 구조를 표현하는 방식에서 시간이 너무 오래 걸려 포기했다. 가장 많이 겹치는 구간을 구하는 방법은 트리 구조로 된 모습에서 가장 긴 리프에서 리...

이진 검색 트리란 image.png > 이진 트리란 노드의 자식을 최대 두 개까지만 가질 수 있는 트리를 말한다. 이진 검색 트리는 이진 트리의 왼 쪽 자식을 부모 노드보다 작은 값, 오른 쪽 자식을 부모 노드 보다 큰 값으로 두어 만들어진 트리를 말한다. > 이진 검색 트리는 효율적인 연산들을 제공한다. 이진 검색 트리는 어떤 값을 찾을 때 연결 리...

image.png 문제 접근 > 값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이 들어오면 그 값보다 큰 값을 가진 인덱스들에 대해 라면의 값을 확인하려고 했다. set안...

트립이란 > 이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간단한 구조로 균형성을 보장하는 이진 검색 트리가 트립이다. > C++의 표준 라이브러리에...

image.png 문제 파악 > 삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이너를 트립으로 두면 문제를 NlogN의 시간 복잡도로 해결할 수 있다. 숫자를 하나씩 원래...

구간 트리란 image.png > 어떤 배열이 주어졌을 때 그 배열의 특정 구간의 최소값을 알고싶다고 하자. 만약 배열 그 자체로 접근하고자 하면 구간에 속한 원소들을 일일이 확인해야 하기 때문에 n의 시간복잡도를 필요로 한다. 이를 효율적으로 수행하기 위한 구조가 구간 트리이다. 구간 트리는 특정 구간의 최소값을 컨테이너에 담고 있는데 담고 있는 구조...

image.png 문제 파악 > 트리의 최소 공통 조상을 구해서 트리의 노드에서 노드까지 가는 거리를 구하는 문제이다. 직관적인 방식을 떠올리면 시간 복잡도가 너무 커지게 되고, 트립을 쓰게 되면 구현이 어렵고 구간 트리를 활용한 문제 취지를 벗어나는 것 같아서 구간 트리를 사용하는 방법을 떠올려 보려고 했지만 떠오르지 않았다. 문제 풀이 구간 트리...

펜윅트리 > 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다. image.png 펜윅트리의 구현 > 펜윅트리를 실제로 구현하기 위해서는 이진수를 활...

문제 풀이 > 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 > 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅 트리를 만들고, 배열의 첫 원소부터 하나씩 갱신하면서 그 원소보다 큰 원소의 개수를 구...