Mo's 알고리즘 이란?구간 질의하는 Query 문제에서 업데이트되지 않는 특수한 상황에서 사용할 수 있는 알고리즘으로 기존의 구간 쿼리는 O(NM)인 반면 Mo's 를 사용하면 O(M sqrt N) 으로 줄일 수 있습니다.  아이디어데이터가 추가적으로 업데이트되지 않는다면, 모든 쿼리에 대해서 항상 전체를 탐색해줄 필요는 없습니다. 이 전에 계산한 구간의 값을 참고하여 답을 구할 수 있습니다.   일단 데이터 길이를 N으로 했을 때 sqrt(N) 의 길이로 그룹을 나눕니다. 위 그림은 N = 10 일때의 그림이며 4개의 구간으로 나눌 수 있습니다. ( 왜 sqrt(N) 으로 나누는지는 아래에 설명하겠습니다 )  만약 위처럼 3가지 쿼리가 주어졌다고 할 때 어떻게 작동하는지 간략하게 그림으로 보고 자세히..

드디어 플래티넘2에 도착했습니다... 눈치가 빠르신 분은 알아챘을 수도 있습니다. 플3 포스팅을 안한 것과 뒤의 저 프로필이 의미하는 바가 무엇인지.. 플3 찍고 나중으로 포스팅을 미뤘다가 어느세 50%정도 채워져서 그냥 포스팅하지 않았습니다. 그리고 뒤의 프로필을 수열과 쿼리를 여러 문제를 풀면 주는건데... 넴, 세그 트리가 대량으로 과제로 나와서 본의 아니게 날먹했습니다.  티어가 실력을 전부 나타내진 않는다 어느정도 티어를 쌓으면서 위의 말이 공감되기 시작했습니다. 예전에는 티어 올리는 재미로, 티어를 목적으로 공부한 반면 지금은 알고리즘을 공부하기 위해 공부하고, 티어는 그 추가적인 결과물이라고 생각합니다.  예전에는 실버나 골드 하위 문제는 그냥 넘기는 버릇이 있었는데, 이제는 일단 풀어야겠습..