반응형 트리2 [백준/C++] 트리와 쿼리 (No. 15681) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 루트노드가 주어지면 그 노드를 기준으로 트리를 그리면 되는 문제다. 단지 그냥 트리를 그리는 것과 다른 점이 있다면, 자식 노드의 수가 몇 개 인지 쿼리를 통해 출력한다는 점이다. 여기서 매번 쿼리가 들어올 때 마다 자식 노드의 수를 계산한다면 매우 많은 반복이 생기게 된다. 그러므로 애초에 트리를 그릴 때 자식노드가 몇 개 인지 return을 해준다면 한번의 트리를 그림으로써 모든 노드의 자식의 수를 알 수 있게 된다. 이제 아래 그림을 통해 어떻게 진행되는지 알아보자 위 그림과 같은 트리가 있을 경우 트리.. 2024. 6. 3. [백준/C++] 트리의 순회 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리의 규칙을 잘 찾으면 해결할 수 있는 문제다. 인오더는 중위 순회로 (왼쪽) -> (루트) -> (오른쪽)프리오더는 전위 순회로 (루트) -> (왼쪽) -> (오른쪽)포스트오더는 후위 순회로 (왼쪽) -> (오른쪽) -> (루트)순서로 탐색을 한다. 여기서 아래 그림을 예로 들어 생각해 보자그러면 우리는 포스트오더가 항상 맨 마지막에 루트 노드가 오기 때문에 포스트오더의 마지막 노드는 프리오더에서 맨 처음에 나오는 루트 노드라는 사실을 알 수 있다. 즉, 아래 그림과 같이 처음에 탐색을 한다. 이를 이용하.. 2024. 5. 20. 이전 1 다음 반응형
