순간을 기록으로

문제 수 N개가 주어졌을 때 , i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하세요. 입력 첫째 줄에 수의 개수 N과 구해야 하는 횟수 N이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지의 합을 출력한다. 분석 데이터 갯수는 10만 개이고, 구간 합을 구해야 하는 횟수도 최대 10만 번이다. 즉 최악의 경우 시간 복잡도는 O(n^2). 연산이 10만^2번, 100억이 되어 100초가 걸린다. 제한시간이 0.5초이므로 단순히 이중 for문으로 문제를 풀 수 없다. 이 문제를 풀기 위해서는 구간합 알고리즘을 이용해야 ..

분석 * 이번 문제는 수 나열에서 부분 합을 여러번 구하는 문제다. * 배열의 구간 합을 구해야 될때에는 합 배열을 이용하면 시간복잡도를 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초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..