CodingTest) 누적합

JJONGHA2·2023년 4월 28일
0

CodingTest

목록 보기
4/5
post-thumbnail

CodingTest 연습문제를 풀다보면 수열이 주어지고, 이 수열의 연속된 부분 수열의 합을 구해서 조건에 만족시키는 값을 출력하는 문제가 자주 등장합니다.

처음에는 for문으로 하나하나 합을 구해서 출력을 해도 '이게 되네' 라며 풀리지만, 레벨이 올라갈수록 '시간 초과' 라는 빨간색 문구를 발견할 수 있습니다.

그래서 slicing 과 sum( ) 메서드를 사용해서 해봐도 이역시 '시간 초과' 라는 빨간색 문구로 저를 반겨줍니다.

이를 해결하기 위해 '누적합' 이라는 것을 사용해봅니다.

빠르고 쉽게 간단한 예시로 알아보겠습니다.

[1, 2, 3, 4, 5]

이런 수열이 주어졌다고 생각해봅시다. 주어진 수열의 요소를 하나씩 누적시키면서 더하면 됩니다.

0 + 1 = 1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15

[0, 1, 3, 6, 10, 15]

바로 이런식으로 말이죠. 그렇다면 이걸로 뭘 할 수 있냐, 이건 그냥 다 더한거지 이걸로 인덱스를 어떻게 알 수 있냐 라고 물어볼겁니다.

누적합의 특징을 잘 살펴 본다면 알 수 있습니다.

기존수열
[1, 2, 3, 4, 5]
누적합
[0, 1, 3, 6, 10, 15]

여기서 '누적합[4] = 10' 에서 '누적합[1] = 1' 을 뺀다면 9가 나옵니다.

끝 index 4 - 1 = 3 => 이놈이 기존 수열의 끝 index가 되고
시작 index 1 => 이놈이 기존 수열의 시작 index가 됩니다.

기존 수열의 1번 index 부터 3번 index 까지 모두 더해보면,
2 + 3 + 4 = 9 와 같이 놀랍게도 아까 누적합에서 빼서 구한 값과 동일한 값이 나오게 됩니다.

이런식으로 누적합을 이용해서 기존 수열의 연속된 부분 수열에 대한 인덱스를 구할 수 있습니다.

그래서 결론은

N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N) 이 걸리지만, 누적합을 이용하면 모든 부분합을 O(1)로 바로 구할 수 있다

누적합을 사용하여 시간 복잡도를 줄이자!!

가 되겠습니다.

profile
깡통훈련시키기

0개의 댓글