11401번: 이항 계수 3

11401번: 이항 계수 3사용 언어: C++문제 요약자연수 N과 정수 K가 주어질 때, 이항 계수 NCK를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.N은 최대 4,000,000까지 주어질 수 있어, 단순 계산으로는 해결이 어렵고1,000,000,007은 소수(prime number)라는 점이 이 문제의 핵심풀이일단 모듈려 연산은 나눗셈에 대해 분배법칙이 성립하지 않고, 계산 자체도 N이 400만까지 가서 단순 계산은 불가능.그래서 해결 방법이 모듈러 곱셈 역원을 쓰는 건데, 이게 어떤 수 B로 나누는 것은, B의 역원(B^-1)을 곱하는 것과 같다는 거고, 이를 이루기 위해 쓰는 것이 페르마의 소정리. 페르마의 소정리페르마의 소정리는, P가 소수이면, a^(P−1) ≡ 1(modP) ..

1717번: 집합의 표현

1717번: 집합의 표현사용 언어: C++문제 요약초기에 0, 1, 2, ..., n의 원소 각각이 자기 자신만 담은 n+1개의 서로 집합으 ㄹ이룬다. 두 연산을 m번 처리한다.1. 합집합 연산 : o a b -> a 가 속한 집합과 b가 속한 집합을 합친다.2. 동일 집합 질의: 1 a b -> a와 b가 ㅈ같은 집합에 속하면 YES, 아니면 No를 출력. 제한은 n 풀이합집합을 하고 해당 두 수가 같은 집합에 있는지 찾는 최적의 방식은 유니온 파인드다.유니온 파인드의 핵심 연산은 두 가지다.1. find(x)- 원소 x가 속한 집합의 대표(root)를 찾는다int find_parent(vector& parent, int x){ if(parent[x] == x) return x; re..

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

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 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.출력첫째 줄에 남아있는 모든 전깃줄이 서로 ..