누적합

1. 개요 안녕하세요. 오늘 풀었던 백준 문제 유형은 누적합이었습니다. 문제를 읽고 구현할 수 있는 여러 알고리즘이 스쳐 지나갔습니다. 그중 구현 난이도가 가장 쉬울 것 같은 누적합을 사용하여 풀었습니다. 구체적으로 생각이 났던 알고리즘에는 "투 포인터"나 "슬라이딩 윈도우"를 사용하는 풀이법이 있었고요 좀 더 어렵게 풀어보자면 "구간합 세그먼트 트리"도 생각이 났습니다. "펜윅 트리"는 제가 아직 공부하지 않아서 제외했습니다. 누적합으로 문제를 풀기 위해서는 배열의 처음과 끝이 연결되어 있는 원형 구조를 어떻게 구현할지 고민해봐야 할 것 같습니다. 저는 다른 문제의 정답 코드를 리뷰할 때, 원형 구조를 linear하게 표현하는 코드를 인상 깊게 보았던 것이 도움이 되었습니다.  2. 문제 풀이 크기가 ..

1. 문제풀이2차원 배열의 누적 합을 구성하고 이를 이용해 계산하는 방법을 요구하는 문제, 시간 복잡도가 O(N^2M^2)가 될 수 있음을 고려해야 했으며, 4중 for loop 구조이지만 캐시 친화적인 형태이므로 무리 없이 동작할 것으로 판단했다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; type..

1. 문제풀이길이가 4인 임의의 비트필드 1xxx가 있다고 가정합시다. 이 비트필드에 xxx는 이전에 등장하였던 1xx, 1x, 1의 패턴이 동일하게 나타납니다. 즉 이전 결과 1xx, 1x, 1에서 등장하는 1의 개수를 알고 있다면 1xxx에서의 1의 개수를 알 수 있습니다. 이를 바탕으로 누적합 배열을 저장합니다.  다음엔 임의의 숫자 x에 대해서 1부터 x까지의 비트필드에서 등장하는 1의 개수를 누적합을 이용하여 계산해야합니다. 숫자 x의 비트필드를 1xxxx라고 한다면 우리는 1xxxx - 10000으로 최상위 비트 1이 몇 개까지 등장했는지 알 수 있습니다. 그 이전에 등장하는 1의 개수는 이전에 구한 누적합으로 계산이 가능합니다. 이런 방법으로 최상위 비트에서 순차적으로 내려오면 1부터 x까지..

1. 문제 풀이 이진 탐색과 누적 합의 응용으로 풀이하였습니다. 처음엔 부배열의 값들이 연속적으로 이루어져 있었기에 투 포인터를 사용해야 하는 거 아닐까? 하는 의문이 생겼습니다. 그러던 중 배열의 크기가 1,000이므로 누적합 배열을 구해놓는다면 O(N^2)으로 부 배열의 모든 합을 구할 수 있다고 판단하게 되면서 이진 탐색을 사용하는 것이 적합할 것 같다는 생각을 하게 됩니다. A, B의 누적합 배열로 중복되지 않은 범위의 부 배열 합 값들을 모두 저장했습니다. 이를 정렬한 다음 lower_bound와 upper_bound를 사용해 경우의 수를 계산해주었습니다. [ 시간복잡도 ]$$ O(N^{2}log M^{2})$$ 2. 코드#include using namespace std;typedef long..