자료구조2 Binary Heap (이진 힙) 힙은 아래 성질을 만족하는 Alomost complete binary tree이다. Max heap의 경우 parent node의 값은 child node의 값보다 크거나 같다. Min heap의 경우 parent node의 값은 child node의 값보다 작거나 같다. 아래의 모든 설명은 Max heap을 기준으로 한다. Max heap의 경우 tree 내의 모든 노드에 대해 parent node의 값은 child node의 값보다 작지 않다. 그래서 Max heap에선 root node의 값이 가장 크다. 값을 삽입하고 뺄 때도 이 성질을 유지하면 root에서는 항상 tree 내의 가장 큰 값이 존재하게 된다. Cpp의 priority queue를 사용해 본 적이 있는가? 어떤 값을 priority.. 2023. 1. 31. Fenwick Tree (펜윅 트리, Binary Indexed Tree = BIT) 배열에서 어느 구간의 구간합을 구한다고 하자. 누적합을 저장한 배열을 사용하면 특정 구간의 구간합을 단순히 두 위치의 값을 빼줌으로 상수 시간에 쉽게 구할 수 있다. 그러나 만약 배열의 값이 자주 바뀐다면 문제가 생긴다. 만약 원래 배열의 k번째 값이 변경된다면 누적합을 저장한 배열에서 k번째와 그 이후의 값들은 모두 변경해주어야 한다. 최악의 경우엔 누적 값을 저장한 배열의 n개의 값들을 다 변경해주어야 한다. 데이터의 양이 많으면서 데이터의 값이 자주 수정된다면 누적합은 사용하기 적합하지 않은 방법이다. 이때 펜윅트리를 사용하면, O(logn)에 해결할 수 있다. 이번 글에서는 펜윅트리에 대해 알아보겠다. 참고로 이번 글에서 n번째라고 하면 배열에서 처럼 0부터 셈을 하는 것이 아닌 일상에서 처럼 1.. 2021. 5. 13. 이전 1 다음
