25682번: 체스판 다시 칠하기 2

25682번: 체스판 다시 칠하기 2사용 언어: C++문제 요약N*M 크기의 보드. 각 칸은 'B', 'W'로 칠해짐. 이 보드에서 임의의 K*K 크기 부분을 잘라서 체스판처럼 만들고자 한다. 체스판이란, 흑백이 번갈아 있는 형태이며 왼쪽 위 칸이 흰색인 경우와 검은색인 경우 두 가지가 존재한다. 목표는, K*K 크기의 구간을 선택한 뒤, 체스판으로 만들기 위해 다시 칠해야 하는 정사각형의 최소 개수를 구하는 것이다.풀이1. 두 체스판 패턴과 비교- 입력 보드와 두 체스판 패턴(W 시작, B 시작)을 비교하여 틀린 칸 수를 0과 1로 기록.- 이를 통해 diff_w[i][j], diff_b[i][j] 배열을 만듦 2. 2차원 누적합(prefix sum) 계산- 각 diff 배열에 대해 2차원 누적합을 만..

10986번: 나머지 합

10986번: 나머지 합사용 언어: C++문제 요약수 N개 A1, A2, ..., AN이 주어진다. 이때 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.풀이처음에는 아래와 같이 모든 (i, j) 쌍에 대해 부분합을 구하고,그 값이 M으로 나누어떨어지는지 검사하려 했지만 시간 초과가 났다.for (int i = 1; i 그래서 시간을 어떻게 줄일 수 있을까 고민해봤는데, 위의 O(N^2)이 아닌 O(N)으로 줄일 수 있었다.방법은 누적합 + 나머지 활용이다. 누적합을 다 하고, 나머지가 같은 prefix 값들끼리 nC2 로 조합하는 것이다.예를 들어 나머지가 1인 prefix 수가 4개면, 이 4개 중 2개 씩 고르면 prefix[4] - prefix[2]를 하..

16139번: 인간-컴퓨터 상호작용

2559번: 수열사용 언어: C++문제 요약문자열 S와 질의 Q개가 주어진다. 각 질의는 알파벳 α와 정수 l, r로 구성되어 있으며,문자열 S[l]부터 S[r]까지 구간 내에서 α가 몇 번 등장했는지 구해야 한다.문자열 길이 ≤ 200,000질의 개수 ≤ 200,000⇒ 단순 순회는 시간 초과 발생.풀이구간 빈도 문제에서는 누적합을 사용하면 효율적으로 문제를 풀 수 있다.알파벳은 총 26개이므로 각 알파벳마다 문자열의 접두 구간에서 누적 등장 횟수를 저장.prefix[c][i] = 문자열 S의 0번째부터 i-1번째까지의 알파벳 c가 등장한 횟수그리고 전처리 방식for (int i = 0; i 정답 코드#include #include #include using namespace std;int main()..

2559번: 수열

2559번: 수열사용 언어: C++문제 요약어떤 날마다 측정한 기온이 정수 수열로 주어진다.이 중 연속된 K일 동안의 기온의 합 중에서 가장 큰 값을 구하라.📌 입력첫 줄: N KN: 전체 날짜 수 (2 ≤ N ≤ 100,000)K: 연속 날짜 수 (1 ≤ K ≤ N)둘째 줄: N개의 정수 (각 날짜의 기온, -100 ~ 100)📌 출력연속된 K일 동안의 기온 합 중 최댓값풀이이 문제를 풀 때 두 가지가 대표적으로 떠오르는데,1. 첫 번째는 그냥 누적합을 구하고 모든 길이의 구간에 대해서 누적합으로 계산해서 최대값을 비교하는 방법2. 두 번째는 슬라이딩 윈도우다. 얘는 그냥 개별 인덱스를 사용하는건데 첫번째 구간 인덱스를 더해서 구하고 첫 번째 인덱스는 빼고 다음 인덱스 값을 더해 값을 비교하는 방식..

11659번 : 구간 합 구하기 4

11659번: 구간 합 구하기 4사용 언어: C++문제 요약수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.풀이전형적인 누적합 (prefix sum)문제다. 매번 값을 구하면 너무 느리니까 미리 관련된 값을 다 구하고 필요할 때 꺼내쓰는 방식이다. 위 방식은 구간과 구간 사이에 합을 구하는 것이므로 모든 자리까지의 누적합을 구하고 해당 자리가 필요할때 구간이 a, b이면 (a#i..