본문 바로가기

분할 정복

BOJ)11442 홀수번째 피보나치 수의 합 문제: icpc.me/11442 N보다 작은 모든 홀수번째 피보나치 수의 합을 구하는 문제이다. N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이방법으로 모든 피보나치수를 구하는건 너무 많은 시간이 걸린다. 하지만 수를 쭉 나열해보면 Rn이 n보다 작은 모든 홀수번째 피보나치 수의 합이라고 가정한다면 R(2n)=R(2n-1)=F(2n) 이라는 공식이 나온다. 따라서 이에 대한 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include using namespace std;typedef long long ll;.. 더보기
BOJ)11443 짝수번째 피보나치 수의 합 문제: icpc.me/11443 N보다 작은 모든 짝수번째 피보나치 수의 합을 구하는 문제이다. N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이 방법으로 모든 피보나치 수를 구하는건 너무 많은 시간이 걸린다. 하지만 수를 쭉 나열해보면 Rn 이 n보다 작은 모든 짝수번째 피보나치 수의 합이라고 가정한다면 R(2n)=R(2n+1)=F(2n+1)-1 이라는 공식이 나온다. 따라서 이에 대한 답을 구해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std;typedef long long l.. 더보기
BOJ)1629 곱셈 문제:icpc.me/1629 A^B(MOD C)를 구하는 문제이다. A,B,C가 2^31까지 들어오므로 단순 구현으로는 오버플로우나 시간초과를 받게 될 것이다. 하지만 우리는 분할정복을 이용하여 logB 시간에 A^B를 구해줄 수 있다. 1234567891011121314151617181920212223#include #include using namespace std;typedef long long ll;ll a, b, c;ll power(ll x, ll y) { ll ret = 1; while (y > 0) { if (y % 2) { ret *= x; ret %= c; } x *= x; x %= c; y /= 2; } return ret;}int main() { scanf("%lld%lld%lld",.. 더보기
이항계수를 구하는 알고리즘 이항계수 는 으로 정의되며 흔히 조합으로 알려져 있습니다. n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다. 우리는 이항계수가 가지는 이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다. 하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다. 그래서 개선된 방법을 필요로 합니다. 이는 맨 위에 정의 된 를 이용하는 방법입니다. 문제 조건에서 모듈러를 위한 소수가 주어질텐데 을 소수에 대한 의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다. 우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N).. 더보기
BOJ)10167 금광 문제: icpc.me/10167 직사각형 모양의 영역으로 금광을 개발 할 때 얻을 수 있는 최대 이익을 구하는 문제이다. 문제를 푸는데 상당히 고생했는데 KOI 2014 중등부 문제인걸 보고 어이가없어서 웃음만 나왔다... 일단 N이 3000이므로 N^2혹은 N^2logN 알고리즘을 사용해야 하는데 처음 생각한것은 x축기준으로 스위핑 하여 y축을 세그먼트 트리 구간합에 업데이트 시키는 작업을 순서대로 하는데이 때 이 작업은 전단계의 점들을 반드시 포함하게 되므로 모든점에 대해서 이 작업을 반복하는 것이다. 이 때 처음에는 최대 구간합을 구하기 위해서 이미 업데이트 된 모든 점이랑 비교하여 구간합의 최댓값을 구했는데 이렇게 할 경우 한점에서 업데이트한 후 구간합의 최댓값을 구하는데 O(NlogN) 여기에 .. 더보기
BOJ)6549 히스토그램에서 가장 큰 직사각형 문제: icpc.me/6549 히스토그램에서 가장 큰 직사각형을 구하는 문제이다. 세그먼트 트리를 이용한 분할 정복을 이용하여 풀 수 있는데 i,j까지의 구간의 직사각형 넓이는 i,j까지의 높이가 최솟값인 부분에 의하여 결정된다. 따라서 우리는 높이가 최솟값인 부분을 기준으로 양쪽을 분할 정복해 나갈 것이다. 이를 계산하기 위하여 높이가 최솟값인 지점을 세그먼트 트리에 저장을 해줘야 한다. 전체에서 넓이를 구하여 높이가 최솟값인 지점을 기준으로 양쪽의 넓이를 다시 구해주면서 최종적으로 높이의 최댓값을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#.. 더보기
BOJ)12846 무서운 아르바이트 문제: icpc.me/12846 알바를 한 기간동안 임금이 가장 적은날을 기준으로 급여를 받을 때 최대 이익을 출력하는 문제이다. 유명한 문제인 히스토그램에서 가장 큰 직사각형과 같은 문제로 해석해도 된다. 세그먼트 트리를 이용하여 최솟값의 위치를 저장한 후 가장 작은 위치를 기준으로 왼쪽 오른쪽을 보며 답을 비교해 나간다. 히스토그램에서 가장 큰 직사각형 문제는 스택으로도 풀 수 있으니 이곳을 참고하도록 하자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include typedef long long ll;using namespac.. 더보기