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]를 하..

12865번: 평범한 배낭

12865번: 평범한 배낭사용 언어: C++문제 요약한 달 후 군대에 가는 준서는 여행을 떠나기 전 최대한 즐거운 추억을 만들기 위해, 배낭에 넣을 수 있는 물건의 가치 합의 최댓값을 고민하고 있다.준서는 N개의 물건을 가지고 있고, 각 물건은 무게 W와 가치 V를 갖는다.배낭에 넣을 수 있는 최대 무게는 K일 때, 배낭에 담을 수 있는 물건들의 가치의 최댓값을 구하라.단, 각 물건은 한 번씩만 사용할 수 있다.풀이이 문제는 전형적인 0-1 배낭 문제로, 동적 계획법(DP)을 이용해 푸는 문제다.dp[j]: 최대 무게가 j일 때의 최대 가치각 물건을 한 번씩만 사용할 수 있으므로, 무게 j부터 역순으로 갱신해야 한다.#include #include using namespace std;int main(){..

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..

2565번: 전깃줄

2565번: 전깃줄사용 언어: C++문제 요약두 개의 전봇대 A, B 사이에 여러 개의 전깃줄이 연결되어 있음.전깃줄은 A의 위치 번호와 B의 위치 번호 쌍으로 주어짐.어떤 두 전깃줄이 교차한다면 위험하므로, 전깃줄 일부를 제거하여 서로 교차하지 않도록 만들고자 함.남길 수 있는 최대 전깃줄 개수를 찾고,제거해야 할 전깃줄의 최소 개수를 출력하라.입력첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.출력첫째 줄에 남아있는 모든 전깃줄이 서로 ..

11053번: 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열사용 언어: C++ 문제 요약수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이dp[i]는 해당 위치에서 가장 긴 증가하는 부분 수열의 길이.dp[i]의 값은 이전 위치 j들 (0그래서 점화식은dp[i] = max(dp[j] +..