제곱근 분할법 (2) 썸네일형 리스트형 [Python] 32387번 충전하기 https://www.acmicpc.net/problem/32387 24/10/06 KCPC 당시, 파이썬으로 검수했던 문제다. 다양한 풀이가 있어서 나름 연습해보기 적절한 문제라고 생각한다. 문제 접근 방식: 문제의 요구 사항은 다음과 같다. 크기가 $N$인 Bool 배열 $A$가 주어지고, 두 종류의 쿼리가 주어진다. 쿼리의 개수는 최대 $10^6$개이며, 배열의 최대 크기는 $10^6$이다. 또한, 배열의 초기 상태는 모두 False로 초기화되어있는 상황이다. 1번 쿼리는 인덱스 $i$가 주어진다. $i$보다 크거나 같은 인덱스 $k$중에서, $A[k]$ = False로 되어있는 가장 작은 인덱스를 True로 바꾸는 것이다. 만약 이것이 불가능하다면 $-1$을 출력한다. 2번 쿼리는 인덱스 $.. [Python] 2357번 최솟값과 최댓값 (추후 보강 예정) https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 24/03/15 대다수의 사람들이 해결한 방식인 세그먼트 트리로 해결하지 않고, 제곱근 분할법으로 해결한 문제이다. 세그먼트 트리로 해결한다면 이후 세그먼트 트리 풀이를 작성할 예정이다. 첫 번째 문제 접근 방식: 제곱근 분할법으로 해결했다. 제곱근 분할법은, 길이 $N$짜리 배열이 있다면 그 배열을 $\sqrt{N}$크기로 적당히 분할하여 시간 복잡도를 줄여.. 이전 1 다음