알고리즘 / 누적 합 - Tech.it

Tech.it

Sign in Subscribe

알고리즘 / 누적 합

누적 합 알고리즘으로 풀이한 문제들입니다.

[PS] BOJ 25711 / 인경산

[PS] BOJ 25711 / 인경산

문제 링크: https://www.acmicpc.net/problem/25711 누적 합을 어떻게 활용할 지 잘 생각해야 합니다. 풀이 누적 합 계산하기 문제에서는 $Q$개의 질문이 주어지고, 각 질문마다 $i$번 산장에서 출발해 $j$번 산장에 도달하기 위해 소모되는 체력을 계산해야 합니다. 매 질문마다 거리를 직접 계산하는 방식으로는 질문을 처리하는 과정의 시간

[PS] BOJ 30508 / 고인물이싫어

[PS] BOJ 30508 / 고인물이싫어

문제 링크: https://www.acmicpc.net/problem/30508 그래프 탐색과 누적합을 모두 활용하는 문제입니다. 풀이를 떠올리면 구현은 어렵지 않습니다. 풀이 단계별로 생각하기 1. 하수구에서부터 BFS 진행해서 전체 타일에 물이 빠진 칸 파악하기 2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기 3. H x M 크기로 모두 물이

[PS] BOJ 10986 / 나머지 합

[PS] BOJ 10986 / 나머지 합

문제 링크: https://www.acmicpc.net/problem/10986 누적 합을 활용하는데, 최적화를 위한 테크닉이 필요합니다. 풀이 문제 변환하기 먼저, 구간 $[1, i]$ $(1 \leq i \leq N)$에 대해, 구간 합을 $P_i$라고 정의합니다. $P_i = \sum_{i=1}^N A[i]$ 또, 구간 $[1, i]$에 대해 구간

[PS] BOJ 1644 / 소수의 연속합

[PS] BOJ 1644 / 소수의 연속합

문제 링크: https://www.acmicpc.net/problem/1644 Thumbnail: Photo by Ryunosuke Kikuno (Unsplash) 풀이 에라토스테네스의 체를 사용해 $N$까지의 소수를 미리 구하고, 소수들의 배열을 가지고 투 포인터 탐색을 활용해 연속 합을 구하면 됩니다. 에라토스테네스의 체 에라토스테네스의 체는 잘 알려진 소수 판별법으로, 1부터 $N$까지의 범위 안에서 소수를 일괄적으로 구할

[PS] BOJ 2253 / 점프

[PS] BOJ 2253 / 점프

문제 링크: https://www.acmicpc.net/problem/2253 Thumbnail: Photo by Jackson Blackhurst (Unsplash) 처음 봤을 때는 DP로 풀 수 있는 계단 문제를 생각했는데, 오를 수 있는 속도를 변화시킬 수 있어 조금 더 풀이가 까다로웠습니다. 풀이 Bottom-Up 방식의 DP로 접근했습니다. DP 배열 구상 DP배열은 다음과 같이 정의했습니다. 💡 DP[돌 번호]

[PS] BOJ 1806 / 부분합

[PS] BOJ 1806 / 부분합

문제 링크: https://www.acmicpc.net/problem/1806 Thumbnail: Photo by Thibault Penin (Unsplash) 전체 수열의 부분 수열 중, 전체 원소의 합이 $S$보다 크거나 같으면서 길이가 최소가 되는 수열을 찾아, 그 길이를 구하는 문제입니다. 풀이 0.5초라는 짧은 시간 제한 때문에, 모든 부분 수열을 탐색할 수 없습니다. 따라서, 투

[PS] BOJ 11660 / 구간 합 구하기 5

[PS] BOJ 11660 / 구간 합 구하기 5

문제 링크: https://www.acmicpc.net/problem/11660 Thumbnail: Photo by Melissa (Unsplash) 2차원 배열의 누적 합 문제입니다! 비슷한 문제를 풀었던 기억이 있네요. 풀이 누적 합을 계산하는 풀이는 지정좌석제 (33993)와 같습니다. 다만, 지정좌석제 풀이에서는 범위의 중앙 좌표를 기준으로 계산했다면 이번 문제는 편의 상 끝 쪽 좌표를 사용했습니다. 누적 합

[PS] BOJ 33993 / 지정좌석제

[PS] BOJ 33993 / 지정좌석제

문제 링크: https://www.acmicpc.net/problem/33993 Thumbnail: Photo by Hiroyoshi Urushima (Unsplash) 예제 입력을 잘 보도록 합시다.. 풀이 누적 합 \(R \times C\) 크기의 좌석에 임의의 위치에 \(N\)명의 친구가 앉아 있습니다. 각 좌석을 중심으로 주변 \(W \times W\) (단, \(W\)는 홀수) 안에 있는 친구의 수를 그

[PS] BOJ 16139 / 인간-컴퓨터 상호작용

[PS] BOJ 16139 / 인간-컴퓨터 상호작용

문제 링크: https://www.acmicpc.net/problem/16139 Thumbnail: Photo by Thanuj Mathew / Unsplash '누적 합'에 대한 이해만 있다면 그리 어렵지 않게 풀이를 떠올릴 수 있습니다. 풀이 최대 200,000자의 문자열 \(S\) 에서, 최대 200,000 번의 구간 쿼리를 수행해야 한다. 각각의 쿼리에서는 \([L, R]\) (L, R