자료구조에서 세그먼트 트리(Segment Tree)의 주된 용도로 올바른 것은?

Q: 자료구조에서 세그먼트 트리(Segment Tree)의 주된 용도로 올바른 것은?

배열의 특정 구간에 대한 합, 최솟값 등의 쿼리와 값 갱신을 O(log n)에 수행한다 세그먼트 트리는 배열을 이진 트리 형태로 분할하여, 구간 합(Range Sum), 구간 최솟값(Range Minimum) 등의 쿼리를 효율적으로 처리합니다. 단순 반복으로 O(n)이 걸리는 구간 쿼리를 O(log n)으로 줄이며, 값 갱신도 O(log n)에 수행할 수 있습니다.

쉬움 freeCodeCamp

보기 및 정답

A 배열의 특정 구간에 대한 합, 최솟값 등의 쿼리와 값 갱신을 O(log n)에 수행한다

B 문자열 데이터에서 특정 패턴을 탐색하고 일치하는 위치를 반환하는 용도이다

C 가중치 그래프에서 출발 노드로부터 목적지까지의 최단 경로를 탐색하는 그래프 경로 탐색 용도이다

D 삽입된 데이터가 항상 정렬된 순서를 유지하도록 자동으로 재배치하는 용도이다

해설

세그먼트 트리는 배열을 이진 트리 형태로 분할하여, 구간 합(Range Sum), 구간 최솟값(Range Minimum) 등의 쿼리를 효율적으로 처리합니다. 단순 반복으로 O(n)이 걸리는 구간 쿼리를 O(log n)으로 줄이며, 값 갱신도 O(log n)에 수행할 수 있습니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

자료구조에서 세그먼트 트리(Segment Tree)의 주된 용도로 올바른 것은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

시장과 사람의 답을 봤다면,다음 결과물의 구조를 고릅니다.

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.