순간을 기록으로

분석 * 이번 문제는 수 나열에서 부분 합을 여러번 구하는 문제다. * 배열의 구간 합을 구해야 될때에는 합 배열을 이용하면 시간복잡도를 O(n)에서 On(1)로 줄일 수 있다. * 합 배열 공식:S[i] = S[i-1] + arr[i] * [i,j] 구간 합 공식: S[j] - S[i-1] * 배열의 사이즈를 1 추가하여 인덱스가 1이 첫 번째 원소로 설정해야 합배열 첫 번째 원소도 규칙있게 구할 수 있다. * * 이번 문제에서 만약 합 배열을 이용하지 않고 이중 for문을 사용하면 수의 갯수*횟수이 연산횟수가 된다. * 100,000*100,000 = 10,000,000,000 이다. 즉 100억번 연산을 하게되고 시간은 100초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..