말랑한 하루

누적 합 문제는 1차, 2차원 상태의 배열과 연관된 문제가 주를 이룬다. 누적 합, 말 그대로 현재까지의 모든 값을 누적 합산한 결과를 새로운 배열에 저장하고, 내가 원하는 범위의 누적 합을 빠르게 계산해낼 수 있다. 누적 합을 계산해 갈 때 내 이전의 누적 값을 불러오는 점화식이 활용되므로, 누적 합 배열의 첫 인덱스는 0으로 초기화 해주는 것이 중요하다. ※ 단, 연속된 구간의 합을 구하는 문제는 투포인터를 활용해 더 간단하게 해결할 수 있으니 주의하자. 1차원 상태의 배열에 대한 누적 합을 구하는 방법은 간단하다. 누적 합 자체의 정의에 맞는 점화식을 세워, 내가 원하는 구간의 합을 구할 수 있다 prefixSum[0] = 0; for(int i = 1; 1

정교한 알고리즘을 사용하지 않아도 해결할 수 있는 유형의 문제로, 손으로 직접 문제를 해결하기 위한 아이디어를 찾아가며 풀어나갈 수 있다 단순히 지시를 따르면 되는 구현, 그리디 또는 수학으로 분류되는 경우이다