khj878   1년 전

최악의 경우N이 100000개 경우에 M개(최악 100000개) 의 구간합을

최대범위(1~100000)번 을 구해서 TL이 나는거 같은데 (최악의 경우 O(n^2) = 백억..? )

이 문제 어떻게 해결해야 될까요?ㅠㅠ


koosaga   1년 전

Si = Sigma(Aj) (j<=i)라고 정의합시다.


1. S 배열을 어떻게 하면 O(n)에 만들까?

2. S 배열을 통해 어떻게 질문당 O(1)에 답을 낼까?


이 문제들을 해결하면 풀수 있습니다.


khj878   1년 전

오오오!!!!

입력을 받은 후에 모든 경우(시작구간 ~ 종료구간)에 대한 합을 구해 배열에 넣고

시작구간과 종료구간의 범위가 주어질때 그 값이 저장된

배열을 어떻게 찾아가야 되는지 문제를 해결하면 된다는거죠?

제가 잘 이해 한건가요?

kyma123   1년 전

{A1, A2, ... , An}이 있을 때, Si = A1 + A2 + ... + Ai라고 하면,

Ai + Ai + 1 + ... + Aj - 1 + Aj는 Sj - Si - 1로 표현할 수 있다는 의미입니다.

khj878   1년 전

아..이해했어요.

그러면 O(n)에 합을 구할수 있고 O(1)에 합을 찾을 수있겟네요.

감사합니다!!

khj878   1년 전

은근히 쉽게 풀렸네요ㅋㅋㅋ

분에 좋은 알고리즘 하나 배웠습니다!

댓글주신 분들 감사합니다.

seungdols   11달 전

글쓴분께서는 음수는 어떻게 처리하셨나요?

khj878   11달 전

음수일 경우와 양수일 경우를 따로 구분하지 않으셔도 됩니다.

1~n까지의 합을 sum[n]에 저장한다고 가정해 봅시다.

특정 구간의 합을 계산 하고 싶을시 sum배열을 이용하여

종료지점까지의 구간합에서 시작지점까지의 구간합을 빼주면 됩니다.

예를 들어보면 입력으로  2 -5 4 2 -10 총 5개의 원소가 들어왔을때

합배열은 2 -3 1 3 -7이 나오게 됩니다.

구간 3~5의 합을 구하고 싶으면 합배열 5번째 원소에서(3~5까지의 합) 

합배열의 2번째원소(1~2까지의 합)을 빼주면 됩니다. 

sum[5]-sum[2] = -7 - (-3) = -4로나오게 되며 검산을 해보아도 결과는 같습니다.

댓글을 작성하려면 로그인해야 합니다.