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

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

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

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

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

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

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

문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...