Computer Science2 Set 자료구조 비교 (c++, python) 알고리즘을 풀던 도중 c++에서 set은 데이터가 정렬되어 있으나 python의 set은 그렇지 않다는 사실을 발견했다. 왜 이러한 차이가 있는고 이러한 차이가 만들어내는 특징은 무엇이 있는지 알아보았습니다. Set 자료구조란 무엇인가 우선 Set 자료구조에 대해 간단히 알아보고 가겠습니다. 위키에서는 다음과 같이 정의하고 있습니다. In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computerimplementation of the mathematical concept of a finite set. Unlike most other coll.. 2021. 3. 24. Segment Tree / 세그먼트 트리 세그먼트 트리는 data를 구간별로 나누고 작업해야 하는 과정 중 구간별로 나누어 반복적으로 실행할 작업들의 결과를 미리 계산하여 저장해 둔 트라이입니다. 이후 해당 작업을 수행하는 대신 세그먼트 트리 내에 있는 결과를 통해 보다 빠르게 원하는 결괏값을 받아올 수 있습니다. 세그먼트 트리는 바이너리 트리로 구성되어 있다. data의 시작 index를 0 마지막 index를 9라고 가정하면 루트는 0~9의 구간을 나타내고 왼쪽의 자식 노드는 0~4 오른쪽 자식 노드는 5~9의 구간을 가지게 된다. 즉 부모노드 구간의 ( 시작 index + 마지막 index ) / 2를 기점으로 자식노드를 나누게 된다. leaf 노드는 시작 index와 마지막 index가 같은 node들로 data의 개수만큼 존재하게 된다.. 2020. 3. 31. 이전 1 다음
