구간합

[Java/백준] 구간 합 구하기 #11659

문제 풀이 (1) 문제 분석하기 수의 개수 N과 합을 구해야 하는 횟수 M은 최대 100,000 임 최악의 경우, 1억 회 이상 연산을 해야 하므로 1초 안에 계산을 끝낼 수 없음 → 구간 합 사용! (2) 손으로 풀어보기 // 합 배열 공식 S[i] = S[i-1] + A[i] // 구간 합 공식 S[j] - S[i-1] N개의 수를 입력받으면서 바로 합 배열 생성 i부터 j까지 구간 합 공식으로 정답 출력 배열의 index는 0부터, 합 배열의 index는 1부터 시작한다는 것에 주의하기! (3) 슈도코드 작성하기 N(숫자의 개수), M(질의 개수) 저장하기 for(1부터 N 까지) { 합 배열 생성하기(S[i] = S[i - 1] + A[i] } for(0부터 M 전까지) { 질의 범위 받기(i ~..

[TIL] 알고리즘 구간 합

✍ Today I Learned 구간 합 구간 합이란? 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 구하기 // 배열 A가 있을 때 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 // 합 배열을 만드는 공식 S[i] = S[i-1] + A[i] 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 구간 합 구하기 // 구간 합 구하는 공식 S[j] - S[i-1] // i에서 j까지 구간 합 // A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정 S[5] = A[0] + A[1] + A[2] + A[..