누적합 단계의 백준 문제들을 풀기 시작했다.
별로 어렵지 않게 풀었는데 시간초과가 발생해서 좀 찾아보니 누적합과 부분합을 구하는 알고리즘이 따로 있는 걸 알게 되었다. 누적합과 부분합을 구하는 알고리즘이 존재하는 지는 이번에 처음 알았다..!
📌 누적합
먼저 누적합에 대해서 알아보고자 한다.
말그대로 누적합은 배열 0번째 부터 N번째까지의 합을 의미한다.
이를 구현하는 건 어렵지 않다.
n개의 수가 있다고 가정하고 n번째 숫자까지의 누적합을 구하는 방법이다.
n = int(input())
arr = list(map(int, input().split()))
prefix_sum = [0]*n # 누적합을 담을 배열
prefix_sum[0] = num[0] # 첫번째 누적합은 더해줄 숫자가 없으므로 배열의 첫 숫자와 동일
# 예를 들어 3번째 수까지의 누적합을 구하라 하면
# 2번째 수까지의 누적합에 3번째 수를 더해주는 방법
for i in range(1, n):
prefix_sum[i] = prefix_sum[i-1]+arr[i]
answer = prefix_sum[n-1]📌 부분합
그렇다면 위에서 배운 누적합을 구하는 방법을 활용해서 부분합을 구하는 방법을 알아볼 것이다.
부분합은 길이가 N인 배열이 있을 때 i번째 수부터 j번째 수까지의 합을 의미한다.
여기서 i, j는 0보다 크거나 같고 N보다 작다.
즉 i번째 수부터 j번째 수까지의 합은 j까지의 누적합에서 i-1번째 수까지의 누적값을 빼주면 된다!
n = int(input())
arr = list(map(int, input().split()))
i,j = map(int,input().split())
.
.
.
# 누적값 계산 부분은 위와 동일하므로 생략
# 부분합 계산
partSum = prefixSum[j] - prefixSum[i-1]💡 같이 풀어보면 좋을 문제
누적합과 부분합을 공부하며 제일 먼저 풀었던 문제이다!
👩🏻💻[BOJ] 11659 구간 합 구하기 4
처음에는 단순 for문을 사용해서 구현했는데 바로 시간초과가 발생했다.
그 이유는 i와 j의 범위가 100,000까지로 매우 커질 수 있기 때문이었다.
위에서 배웠던 내용을 잘 숙지한다면 더 간단하고 아주 쉽게 풀 수 있다!
-끝-
👩🏻💻👊🏻⭐️