부분 합
-
[Algorithm] - 부분합Algorithm/Algorithm 2022. 9. 24. 00:39
부분 합 부분 합이란? 흔히 부분합 알고리즘은 시작점 S 부터 끝점 E까지의 모든 합을 구하는 문제입니다. 하지만, 주어진 시간내에 주어지는 모든 범위의 부분합을 구하기 위해선, 일일이 다 더해주는 것은 비효율적인 일입니다. 임의의 배열을 만들어, 일일히 더하는 것이 아닌 모든 동작을 한번에 하도록 처리하여 주는 것이 주요 목표입니다. O(N) -> O(1) 아이디어 index 2~4까지의 값을 구하려고 합니다. 이 때 부분합은 arr[2]+arr[3]+arr[4]라고 할 수도 있지만, sum[5]-sum[2]와도 같습니다. 만약 부분적으로 특정 값을 빼고 넣어준다고 하여 봅시다. [4,4,4,4,4] 라는 배열에서 1부터 마지막 index까지 6을 추가 2부터 3까지 index만 5를 추가한다고 해봅시..