이게 뭐야? 트리 종류 중에 하나이며, 연속된 구간(특정 범위)의 합(최솟값, 최댓값, 곱 등)을 구하는데 많이 쓰인다. 아래에서 선형구현과 비교하며 왜 쓰는지, 어떻게 사용하는지 gif를 준비해 놨으니 자세히 알아보자. 세그먼트 트리 문제 보기 문제 - 1 페이지 www.acmicpc.net 일단 결과부터 보자 입력된 수는 10의 7제곱이다. 10개의 데이터 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]를 두고 구간 합을 구해본다. 예시 입력 : 1 10 예시 출력 : 55 선형 구현 O(N) 초기화 과정 O(N) ARRAY = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] for i in range(1,len(ARRAY)): ARRAY[i] += ARRAY[i-1] 1 3 6..

해당 게시글은 다크모드에 최적화 되어 있지 않습니다. 표준 템플릿 라이브러리 STL (Standard Tamplate Library) 중 컨테이너 항목에 속하는 vector, 항상 효율적인 것은 아닙니다. C++ 자료구조 컨테이너 세 가지를 살펴보시고 적절한 곳에 사용하시기 바랍니다. ※ 해당 포스트에서는 각 컨테이너에 대해 자세히는 다루지 않습니다. 목차 Vector #include [ 특징 & 장점 ] 흔히 사용하는 vector는 일반 배열처럼 연속적인 메모리 공간에 저장합니다. 그렇기에 iterator 뿐 아니라 index로도 접근이 가능합니다. 또한, 동적으로 확장/축소가 가능한 Dynamic Arrary로 구현되어 있습니다. 연속적인 메모리 공간에 저장되기에 deque, list에 비해서 개별 ..