PS
[개념정리] 부분합
부분합이란? 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열 이제부터 부분합 배열을 psum[]이라고 하겠습니다. 또한, psum[-1] = 0; psum[0] = A[0]; psum[k] = ([0, k] 구간의 합) 으로 두겠습니다. 부분합 시간복잡도? O(1) (그냥 psum[b] - psum[a-1] 하면 됩니다.) 문제 풀며 느낀 팁 부분합 문제인거 같은데 뭔가 잘 안풀린다면, 부분합 배열을 정렬해보자. Sum(a,b) = psum[b] - psum[a - 1] 인데, 구간의 합이 특정한 값이 되어야 한다던가, 최소일 때를 찾아야 한다거나 할 때 유용하다. ex) 구간합이 0인 구간을 구해라(정렬한 후에 같은 값이 몇 개 있는지 세면 됨) 구간으로 주문할 수 있..
2021. 7. 8. 18:40