구간 내 고유 요소 개수 구하기 - 펜윅 트리와 오프라인 처리
이 문제는 주어진 배열의 특정 구간에 존재하는 서로 다른 숫자의 개수를 구하는 것을 목표로 합니다. 이를 해결하기 위해 펜윅 트리(Fenwick Tree)와 오프라인 쿼리 처리 기법을 활용합니다.
펜윅 트리를 사용할 때 핵심은 각 위치에서 해당 요소가 마지막으로 등장한 위치를 추적하고, 새로운 위치에서 등장할 경우 이전 위치의 값을 제거하고 현재 위치를 갱신하는 것 ...
7월 17일 22:50에 게시됨
스위핑 라인(Sweep Line) 알고리즘 이해하기
스위핑 라인은 데이터 구조를 활용한 중요한 기법으로, 주로 구간 내 부분 구간의 정보를 쿼리하는 문제를 해결할 때 사용됩니다. 이 기법은 오프라인 처리 기반으로 동작합니다.
기본 아이디어는 다음과 같습니다. 모든 쿼리를 오프라인으로 저장한 후 특정 기준으로 정렬합니다. 그런 다음 배열의 시작부터 끝까지(1부터 n까지) 순회하면서 정보를 점진적으로 업데이트 ...
7월 6일 20:02에 게시됨