트리 검색 결과

해당 글 4건
여러 트릭에 응용되는 트리에서의 dfs ordering을 알아봅시다.

ps를 하시다 보면, 이런 말은 한 번쯤 들어보셨을 겁니다. 트리를 일렬로 펴기, 트리를 구간으로 바꿔서 풀기. 자동차 공장 트릭. 이들의 기반이 되는 것은 dfs ordering입니다. 그리고 이를 응용해서, HLD, LCA와 같은 것에도 쓸 수 있습니다. 이 글에서는 HLD, LCA는 다루지 않을 겁니다. 대신에, 트리를 구간으로 바꾸기 위해서 사용하는 전처리에 대해서 알아보도록 하겠습니다. 먼저, 예시로 쓰이는 트리는 아래와 같습니다. 여기서, 이런 쿼리들이 들어온다고 생각해 보겠습니다. 3을 root로 하는 서브 트리에 속한 노드들에 +3을 더한다. 혹은 xor 3을 한다. 이런 것들이 들어올 수 있어요. 트리를 구간으로 어떻게 펴는 것이 가능할까요? 해당 쿼리에서 중요한 것은 부모와 거기에 딸려..
자료알고/알고리즘 2021. 3. 7. 20:31
균형 이진 트리 : 제약 조건이 맞지 않으면 추가적인 연산을 한다.

ps를 하시면, 많이 보는 자료구조 중 하나는, Java에서 TreeSet, TreeMap, C++의 STL에서는 Map, Set 등이 있습니다. 균형 트리로 구현이 되어 있다는 이야기는 많이 합니다. 이게 무엇일까? 에 대해서만 간단하게 생각해 보도록 하겠습니다. 필기 시험에 나올 때 상당히 매력적인 보기를 주는 경우도 있으니, 간단하게 개념을 짚고 넘어가시는 것도 좋겠습니다. 이진 트리를 생각해 봅시다. 이것은 기준 노드를 기준으로 그것보다 작으면 왼쪽에, 크면 우측에 옵니다. 그러면 1을 찾기 위해서는 몇 번의 탐색이 필요할까요? 3보다 작으므로 왼쪽으로 갑니다. 2보다도 작으므로 왼쪽으로 갑니다. 그랬더니 1이 있습니다. 3번 탐색하면 됩니다. 그러면 이 트리에서 -5를 찾기 위해서는 어떻게 해야..
자료알고/자료구조 2020. 1. 11. 03:28
java hashset은 key의 해쉬 코드가 모두 같을 때 최악 복잡도가 어떻게 될까요?

저번에, 왜 equals를 구현하면 왜 hashCode를 같이 구현해야 하는지에 대해서 설명을 했습니다. hash 계열의 자료구조 때문에 그렇다고 했었습니다. 그렇지 않으면 어떻게 동작하는지는 여기를 참고하시면 좋겠습니다. 이 내용에 대해서 숙지하셨다고 가정하고 진행하도록 하겠습니다. 면접 질문에서 간혹 가다가 등장하는지는 잘 모르겠습니다만, 어떠한 객체의 hashCode 값이 같은 것들을 모두 hashSet에 넣을 때, 어떤 일이 벌어지는지는 꽤 중요한 문제 중 하나일 겁니다. 사실, 우리는 그렇게 바보같이 구현할 일이 없습니다. 그렇지만, 저는 이에 대해서 포스팅 하도록 하겠습니다. 먼저 Java 8에서부터, hashMap은 버킷에 8개 이상 달려있을 때, Balanced Tree로 변환이 된다는 것..
레퍼런스/분석 2019. 12. 18. 22:35
우선순위 큐 : 부모가 자식들보다 rank가 높다.

우선순위 큐는, 삽입과 삭제가 일어날 때, 가장 우선순위가 높은 것을 빠르게 찾을 수 있는 구조입니다. 일단, 이것의 특징 먼저 간단하게 잡고 넘어가 봅시다. 먼저, 부모들은 자식들보다 rank가 높습니다. 예를 들어서, A의 자식이 B, C라고 해 봅시다. 그러면, A >= B이고 A >= C입니다. 그러면 A의 모든 child들 (자식의 자식이라던지)은 무조건 A보다 rank가 같거나 낮을까요? 위 그림을 봅시다. B(1)의 직계 child는 B(2), B(2)의 child는 B(3), ... 이런 식으로 가고 있어요. 그러면 A >= B(1) >= ... >= B(n)이 성립합니다. 연쇄입니다. 따라서, A >= B(n)입니다. 부모에서 자식으로만 연결된 간선이 있고, x가 A로부터 도달 가능할 때..
자료알고/자료구조 2019. 12. 16. 21:56