세그먼트 트리의 Lazy Propagation 이번 포스팅에서는 세그먼트 트리의 Lazy Propagation에 대해서 알아보겠습니다. Lazy Propagation은 구간 Query에 대한 시간 복잡도를 O(mnlogn)에서 O(nlogn) 수준으로 개선하는 방법입니다. 그 전에 세그먼트 트리 공부가 필요하신 부분은 아래 글 참고 부탁드립니다. 파이썬, 세그먼트 트리 구현 세그먼트 트리는 무엇인가? 세그먼트 트리는 완전이진트리를 기반으로 주워진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조입니다. 제가 이 자료구조를 사용해서 문제를 풀었을 때는 대부 ojt90902.tistory.com 세그먼트 트리의 단점 세그먼트 트리는 기본적으로 특정 구간 내에 쿼리를 처리할 때, logn만에 처리할 수 있는 자료..
Node 선언 class Node(object) : def __init__(self,data): self.data = data self.count = 0 self.child = {} Node 선언 클래스를 만들어준다. Node는 각각 data, count, child를 가지고 있다. data : 현재 노드가 어떤 문자를 가지는지를 보여준다. Node('a')라고 선언할 경우, 자동으로 초기화하는데 이 때 data에는 'a'가 들어가게 된다. count : 현재 노드를 지나간 문자열이 몇개인지 알려주는 변수. 해당 노드를 지나가는 문자열이 하나씩 생길 때 마다, count를 증가시킨다. child : 현재 노드의 자식노드를 나타낸다. 딕셔너리 형태로 선언하고, 딕셔너리의 key는 data명이, value에..
세그먼트 트리는 무엇인가? 세그먼트 트리는 완전이진트리를 기반으로 주워진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조입니다. 제가 이 자료구조를 사용해서 문제를 풀었을 때는 대부분 어떤 범위 내에서 어떤 값을 찾아야 할 때 사용을 했는데, 완전탐색을 할 경우 시간초과가 발생하여, O(N^2)에서 O(logn)수준으로 시간복잡도를 줄여야 할 때 주로 사용하게 되었습니다. 세그먼트 트리는 기본적으로 각 노드가 특정 구간에 대한 정보를 가지고 있는 자료구조입니다. 정보는 '특정 구간'내의 어떤 것이든 될 수 있으며, 최소값, 최대값, 구간합, 혹은 최소값의 위치 정보, 정렬 상태 등이 될 수 있습니다. 아래 그림은 세그먼트 트리를 직접 그려본 그림입니다. 노드 위에 있는 N은 'Node'를 뜻하는 알파벳이며..