𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

1. 누적 합(prefix sum)1.1 개념특정 배열에서 어떠한 구간까지의 합을 구하는 방식. 어떠한 1차원 배열 [ 1, 5, 2, 10, 1, 8 ] 에서 가장 합이 큰 길이가 3인 부분 배열을 고를 때, [ 1, 5, 2 ], [ 5, 2, 10 ], ... , [ 10, 1, 8 ] 을 하나하나씩 반복문을 돌려나가면서 비교해 나가는 것이 아니라 미리 누적합을 계산해둔 배열 [ 1, 6, 8, 18, 19, 27 ] 를 활용하여 계산을 하기 때문에, 계산량에서 큰 이득이 있다. 1.2 1차원 배열알고리즘 작동 방식은 다음과 같다. 1. 길이가 N(또는 N + 1)의 누적합 배열을 선언하고, 각 누적합 배열의 i번째 인덱스에는 원본 배열의 1번째부터 i번째 원소의 합을 저장한다.2. a번째 원소부터..