홈

How I went into the rabbit hole. Recently I had the chance to try using PCA for a data analysis project I was working on at Riderdash. Specifically, I was trying to convert a time-series data into a user-feature matrix of sorts so that I could analyze it with dimensionality reduction. I quickly realized that the way I had my data stored, it wa...

서론 구간합이란 임의의 배열 $a_1, a_2, \dots, a_N$에서 쿼리 $(x, y)$가 주어지면 $S = a_x + a_{x+1} + \dots + a_y = \sum_{i=x}^{y}{a_i}$인 $S$의 값을 구하는 것이다. 구간합 문제는 일상 속에서도 많이 발견할 수 있을 뿐만 아니라 다양한 분야에서 사용된다. 간단해 보이는 이 문제는 한 쿼리가 주어질 때 마다 $O(y - x + 1)$의 복잡도를 가지고 있기 때문에 $Q$개의 쿼리가 주어질 때, 최악의 경우 $O(NQ)$만큼의 비용이 든다. 이 문제를 빠르게 해결할 수는 없을까? 누적 합 배열 - Prefix Sum Array 구간합을 구...