본문 바로가기
728x90

prefixsum

[백준] 1292번 : 쉽게 푸는 문제 - C/C++ 문제 자체는 특정 규칙을 따르는 수열을 생성한 뒤, 주어진 구간 합을 구하는 문제이다.1,2,2,3,3,3,4,4,4,4,5,5,...i라는 수가 i번 반복된다는 규칙을 가진다. A,B 입력받고, 그에 해당하는 구간합 구하기구간합 [a,b]는 sum += ary[i] 로 쉽게 구할 수 있다.for(int i = a; i  문제에서 제약조건을  정수 A, B(1 ≤ A ≤ B ≤ 1,000) 이렇게 걸어두었기 때문에const로 NMAX를 선언하자.const int NMAX = 1001;1000으로 안 하고 왜 1001로 하나요?--> 상관은 없다. (반복문 돌릴때 등호 쓰기 싫어서) k는 현재 배열의 인덱스이다.1로 초기화했었다.for(int i = 0; i 1000){ break; .. 더보기
[백준] 11660번 : 구간 합 구하기 5 - C/C++ 지난번에 풀었던 문제와 비슷하다.누적합(prefix sum)을 이용하자. 입력 받은 2차원 배열을 저장할 공간과 누적합을 저장할 dp 테이블을 미리 선언해주자.int sum[1025][1025], dp[1025][1025]; N과 M을 입력 받았다면 dp를 처리하자.for(int i=1; i> sum[i][j]; dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + sum[i][j]; }} 왜 dp를 저렇게 처리하나요?https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하.. 더보기
[백준] 11659번 : 구간 합 구하기 4 - C/C++ 문제 풀이 순서는 아래와 같다.1. 데이터의 개수 N과 질의 개수 M 입력2. 구간 합을 구할 대상 배열 입력3. 구간 i,j 입력4. 출력 이전 글에 구간 합에 대한 내용을 정리했으니참고하길 바란다.https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한binaryroot.tistory.com 글을 확인했다면, 풀이를 시작해보자.  N과 M 입력int n,m;cin >> n >> m; 배열은 100000를 넘을 수 없으니const로 미리 선언해주기const int NMAX = 100020;int a.. 더보기
[백준] 2167번 : 2차원 배열의 합 - C/C++ 문제 해결 과정은 아래와 같다.1. 배열 입력2. 합을 구할 K 입력 받고 정수 네 개 입력 받기3. 합 구하기  벡터를 이용하여 동적으로 2차원 배열을 생성할 것이다.vector> ary(n + 1, vector(m + 1, 0)); ary[n+1][m+1] → (1-based index)로 사용하기 위해 입력받은 n,m을 각각 1씩 증가시킨다누적합 계산을 쉽게 하기 위해서 모든 값을 0으로 초기화 시킨다. -2차원 누적합(prefix sum)???수들의 나열에서 특정 구간의 합을 의미하는 prefix sum은보통은 1차원 배열에서 i부터 k 인덱스 사이의 값을 구하는 데에 이용된다. 부분합은 아래와 같이 코드를 작성할 수 있다.for (int i = 1; i > num; ary[i][j] =.. 더보기
728x90

티스토리툴바