돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/13548 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. 문제 풀이 일단 문제를 읽어보자. 구간 내에서 가장 많이 나타나는 수 -> 각각의 수들이 몇번씩 나왔는지 관리하려고 하면 된다. 또한 이 질문이 쿼리로 주어진다. 이러한 형식의 문제를 많이 풀어봤으면 바로 Mo's algorithm을 써야 한다는 생각을 할 수 있다. Mo's algorithm 으로 구간을 더하거나 빼주면서 각 숫자별로 몇 개씩 있는지 관리한다고 생..

문제 링크 : https://www.acmicpc.net/problem/13547 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. 문제 풀이 수의 갯수를 출력하기 위해서는 수들의 집합을 관리 해야한다. 쿼리로써 구간을 많이 주는데 그 쿼리마다 수들의 집합을 관리해야한다 -> 바로 Mo's algorithm을 떠올릴 수 있다. 풀이도 꽤나 간단하게 보인다. Mo's algorithm을 이용하여 구간을 정렬하고 구간내에서의 각 숫자의 갯수를 세주면 된다. 구간을 추가할 때는 추가되는 구간의 숫자의 갯수에 1..

문제 링크 : https://www.acmicpc.net/problem/13554 문제 태그 (관련 지식) 더보기 Mo's algorithm, Segment tree 문제 소개 길이가 N인 두 수열 A1, A2, ..., AN과 B1, B2, ..., BN가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: i ≤ p, q ≤ j이면서 Ap × Bq ≤ k 인 (p, q) 쌍의 개수를 출력한다. 문제 풀이 일단 오프라인 쿼리고 시간제한이 6초이다. 사실 어떻게 접근을 해야할지 모르겠다. 이 문제를 볼 때 쯤이면 다른 수열과 쿼리 문제를 꽤나 풀어봤을 것이고, 그러면 수쿼를 풀 수 있는 도구중 Mo's Algorithm이 생각이 날 수 밖에 없다. 하지만 문제가 있다. Mo's a..

sqrt, 루트계의 스페셜리스트 알고리즘인 Mo's algorithm을 소개하려고 한다. 어떤 문제를 해결할 때 기본적으로 루트풀이는 친숙하지 않아서 떠올리기 힘들다. 하지만 그 와중에 Mo's algorithm은 굉장히 신박한 아이디어로 만든 시간복잡도이기 때문에 이 알고리즘은 정말 '알고 있어야' 사용이 가능하고 문제를 풀 수 있을 것이다. Mo's algorithm 이란? Mo's algorithm은 업데이트가 없이 오프라인으로 구간 쿼리가 많이 주어질 때, 그 구간쿼리들을 효율적으로 처리하는 알고리즘이다. 기본적으로 오프라인 쿼리여야 되고, 처리하는 쿼리들의 순서를 잘 조정함으로서 더 효율적으로 처리를 할 수 있게 됩니다. Mo's algorithm의 작동 방식 1. 어떤 쿼리 (구간) 에 대한 ..