본문 바로가기

전체 글

 (772)
mo`s. [13548] [1. 문제 설명]https://www.acmicpc.net/problem/13548[2. 풀이 접근]동일한 숫자의 발생 횟수를 저장할 배열이 필요함. (occurs)index: 수열의 원소value: 현재 구간에서 해당 원소의 발생 횟수발생 횟수에 대해서 해당 횟수만큼 존재하는 숫자의 개수. - 3이라는 원소가 4번 발생하고, 5라는 원소가 4번 발생한 경우- 4번 발생한 원소의 개수는 2개가 된다.index: 횟수value: 횟수만큼 존재하는 숫자의 개수.즉, 쿼리에 대해서 각 포인터가 (Left, Right) 넓혀지는 방향으로 움직이는 경우.구하고자 하는 최대 값이 갱신 되는지 확인 하도록 한다.반대로, 각 포인터가 좁혀지는 방향으로 움직이는 경우.현재 포인터가 가리키는 원소 a 의 발생 횟수가 1..
제곱근 분할법 [1. 개요]배열에 대한 제곱근 분할법이란배열을 길이의 제곱근 단위로 나누어 구간에 대한 쿼리를 처리하는 것이다.즉, 오프라인 쿼리 처리에서 매우 유용하지만, 수정이 불가능한다는 단점이 있다.[2. 상세]배열의 특정 구간에 대해 최대값, 최소값 등을 계산해야 한다고 할 때,세그먼트 트리 등을 이용해 처리할 수 도 있지만, 배열을 특정한 크기로 묶어서(이하 블록) 아래와 같이 처리 할 수 있다.쿼리 구간 [L, R] 이 블록 들에 interleave 한 경우 쿼리 구간 [L, R] 이 전체 블록을 포함 하는 경우전체 배열의 길이를 N , 블록의 크기를 K 라 할 때, 1번 경우는 아래와 같다.L 이 왼쪽 블록에 포함되고R 이 오른쪽 블록에 포함 됨.이 경우, 쿼리의 시간복잡도는 2K2번 경우는 전체 구간이..
제곱근 분할법. [13546] [1. 문제 설명]https://www.acmicpc.net/problem/13546[2. 풀이 접근]완전 탐색으로 풀이L -> R 방향으로 배열을 순회하면서배열의 값을 index 로 하여 배열의 값의 최초 출현 위치를 기록하고,2회 이상 출현 시, 최초 저장 된 위치를 이용하여 구하고자 하는 길이를 계산 하고,필요 시, 전체 결과를 갱신하도록 한다.완전 탐색 풀이는 배열의 길이와 쿼리의 개수로 보아 그 시간 복잡도는 O(NK) 이고,N 과 K 모두 최대 100,000 이므로, 시간 조건을 만족하지 못함. 여기서, 배열 내 값이 변하지 않고 현재 쿼리의 결과가 나중 쿼리 결과에 영향을 주지 않으므로 오프라인 알고리즘 적용을 고려해 볼 수 있다. 오프라인 알고리즘으로 풀이제곱근 단위로 배열을 분할 및 mo..

티스토리툴바