중첩 루프를 O(n²)에서 O(n)로 바꾸는 누적 상태 유지 기법

Context

배열의 각 인덱스까지의 누적 합을 구할 때, 단순히 모든 이전 요소를 다시 더하는 중첩 루프 구조는 동일한 계산을 반복한다. result[2]를 구할 때 이미 result[1]을 계산했음에도 다시 처음부터 합을 구한다.

Technical Solution

• 배열 전체를 순회하며 단일 합계 변수를 유지한다.
• 각 단계에서 현재 요소를 합계에 더한 뒤 결과 배열에 저장한다.
• result[i] = result[i-1] + nums[i] 공식으로 이전 결과를 재활용한다.
• 입력 배열을 직접 수정하는 제자리(in-place) 변형도 가능하다.
• 루프 불변량으로 "step i에서 sum은 nums[0]부터 nums[i-1]까지의 합"을 증명한다.