알고리즘/삼성 SW검정 Pro
[한방정리]삼성 SW검정 Pro 유형정리 #1
인덱스 트리 구간합을 구하는 트리 하면 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중 SW검정 Pro에 자주 출제되었던 인덱스 트리에 대해 알아보겠습니다. 인덱스 트리란 포화 이진트리 형태의 자료구조로 리프 노드에 내가 쓸 값들을 저장해두고, 부모들에는 해당 노드의 합들로 된 노드들을 구현해둔 트리입니다. 출제 유형은 아래와 같습니다. 유형 문제 비고 구간의 최소값 (RMQ) 구간의 최소값 [백준] 최솟값과 최댓값 기본적인 트리 질의 응답 1 ~ N 까지 k칸 이내 건너 뛰기 [기출] 징검다리 구간의 최소값 변형 유형 동순위 처리 [기출] 초밥 동순위 모아서 UPDATE MAX값 - MIN값 [기출] 인접한수의 차이 MAX TREE, MIN TREE 2개 사용 구간합 (RSQ) 구간합 [백..
2022. 7. 26. 19:58