본문 바로가기

누적합3

[백준 2015] 수들의 합 4 www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 누적합과 구간합을 알아야 하는 문제이다. 가끔 보이는 유형인데 볼 때마다 못 푼다...ㅠㅠㅠ eazymean.tistory.com/43 [알고리즘] Prefix Sum 구간 합/누적 합 알고리즘 prefix sum이란 구간 합을 의미한다. 예를 들어, int arr[5] = {10,20,30,40,50}; prefix sum은 prefix[i].. 2021. 1. 1.
[백준 2167] 2차원 배열의 합 www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 누적합을 사용하여 시간을 줄이는 문제이다. (i,j)부터 (x,y)까지 다 더해도 상관없긴 하나 tle가 날꺼 같아서 col기준 누적합을 사용했다. i는 시작 row, x는 마지막 row col기준 누적합을 사용하므로 sum[?][y] - sum[?][j-1]을 해주면 각 row에 대한 합이 나온다. #include using namespace std; int m, n; int su.. 2020. 12. 11.
[leetcode 560] Subarray Sum Equals K Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Constraints: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. 풀이: 처음 접근한 방법은 투포인터...하지만 투포인터가 작동하려면 배열 안의 수가 전부 양수라는 조건이 있어야 .. 2020. 10. 1.

티스토리툴바