본문 바로가기

전체 글

 (774)
제곱근 분할법 [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..
Placement new [1. 개요]placement new 라는 문법(혹은 기능) 은 일반적인 동적 할당 보다 조금 더 세밀하게 메모리의 수명을 관리할 수 있게 해준다. 일반적으로 객체를 대상으로 하는 new 는 메모리 할당 및 생성자 호출을delete 는 소멸자 호출 및 메모리 해제를 같이 진행 하게 해준다. 그러나, 아래와 같은 요구사항이 있을 수 있다.메모리를 할당만 하고, 생성자 호출은 뒤로 미루고 싶다.소멸자를 호출하여, 객체 내부의 메모리를 정리하지만, 객체 자체의 메모리는 당장 해제하지 않고 싶다.특히, 아래와 같은 상황도 있을 수 있다.공유 메모리를 대상으로 특정 객체를 공유하고 싶다.즉, 메모리는 이미 할당이 되어있지만, 객체의 생성자를 호출하고 싶다. 주의할 점은 소멸자가 자동으로 호출되지 않는다. (소멸자..

티스토리툴바