📘누적합
누적합 알고리즘은 배열에서 특정 구간의 합을 빠르게 계산하기 위해 사용되는 알고리즘이다. 이 알고리즘을 사용하면 원본 배열의 값을 매번 더하지 않고도 특정 구간의 합을 효율적으로 구할 수 있다.
먼저, 원본 배열이 있다고 가정해보자. 예를 들어, 배열이 [2, 4, 5, 1, 3]라고 하자.
누적합 배열은 원본 배열의 앞에서부터 각 원소까지 합을 저장하는 배열이다. 이를 계산하는 방법은 다음과 같다.
- lst_sum[0] = lst[0]로 시작한다. (lst_sum은 누적합 배열이다.)
- lst_sum[i] = lst_sum[i-1] + lst[i]로 계속해서 각 원소를 더해 나간다.
위의 예시 배열을 기준으로 누적합 배열을 계산해보면 다음과 같다.
- lst_sum[0] = 2
- lst_sum[1] = lst_sum[0] + 4 = 2 + 4 = 6
- lst_sum[2] = lst_sum[1] + 5 = 6 + 5 = 11
- lst_sum[3] = lst_sum[2] + 1 = 11 + 1 = 12
- lst_sum[4] = lst_sum[3] + 3 = 12 + 3 = 15
따라서 누적합 배열 lst_sum은 [2, 6, 11, 12, 15]가 된다.
✅코드 구현
위 예시를 파이썬으로 구현한 코드는 다음과 같다.
lst = [2,4,5,1,3]
lst_sum = [0]*(len(lst))
lst_sum[0] = lst[0]
for i in range(1, len(lst)):
lst_sum[i] = lst_sum[i-1] + lst[i]
print(lst_sum) # 최종 누적합📘구간합
구간합 알고리즘은 배열에서 특정 구간의 합을 빠르고 효율적으로 계산하는 방법이다. 이 알고리즘은 특히 데이터가 크거나 구간 합을 자주 계산해야 할 때 유용하다.
위 누적합 배열을 사용하여 특정 구간의 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 1번 인덱스부터 3번 인덱스까지의 합을 계산하고 싶다고 해보자. 이를 구하기 위해서 다음과 같은 공식을 사용할 수 있다.
- sum[i, j] = lst_sum[j] - lst_sum[i-1]
여기서 i와 j는 각각 구간의 시작과 끝 인덱스이다. 만약 i가 0이라면 lst_sum[i-1] 대신 0을 사용하면 된다.
예시에서 1번 인덱스부터 3번 인덱스까지의 합을 계산해보면
- sum[1, 3] = lst_sum[3] - lst_sum[0]
- sum[1, 3] = 12 - 2 = 10
따라서 배열 [2, 4, 5, 1, 3]의 1번 인덱스부터 3번 인덱스까지의 합은 10이 된다.
✅코드 구현
위 예시를 파이썬으로 구현한 코드는 다음과 같다.
# 1번째 인덱스부터 3번째 인덱스까지의 합 구하기
lst = [2, 4, 5, 1, 3]
lst_sum = [0]*(len(lst)+1)
x,y = 1,3
result = lst_sum[y] - lst_sum[x-1]
print(result)✅구간합 응용
연속된 m개의 숫자들의 합이 가장 큰 구간의 값(합) 구하기
lst = [1,8,7,4,3,5,6]
n = len(lst)
m = 2
maxvalue,sum = 0,0
for i in range(m): # 처음 m개의 합 구하기
sum += lst[i]
maxvalue = sum
for i in range(n-m):
sum += lst[i+m] # 처음 m개의 합 sum에 i+m번째 인덱스 값을 더하기
sum -= lst[i] # sum에서 i번째 인덱스의 값을 빼주기
if sum > maxvalue:
maxvalue = sum
print(maxvalue)위 코드는 2개의 숫자들의 합이 가장 큰 구간의 합을 구하는 코드이다. 처음 2개의 합을 구하고 그 값을 maxvalue에 할당한다. 처음 2개는 합을 구했으므로 2개를 제외한 만큼 for문의 범위를 지정한다. 처음 2개 합을 구한 것에 i가 0이면 2(0+2)번 인덱스의 값을 더한다. 여기까지 sum에 더해진 상태가 1 + 8 + 7 이므로 앞에 1을 빼줘야 한다.
