programmer life guidance 101

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 10013 5217 4243 52.780% 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 ..

> Prefix Sum 누적 합, 구간 합 누적합 또는 구간 합을 빠르게 구하는 알고리즘입니다. 여기서 주의해야할 것은 부분 합 은 0 ~ k까지의 합을 의미하는 것이고 구간 합은 a ~ b까지의 합을 의미 합니다. 이러한 알고리즘은 어디에 쓰일까요? 아래와 같은 문제를 예시로 봅시다. int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 존재한다. 이 때 a에서 b의 구간 합을 요구하는 쿼리 "2천만개"가 들어온다. 이러한 문제에 대해 어떻게 해결 할 것인가? 가장 쉬운 방식은 브루트 포스를 이용해 일일이 더하는 것입니다.하지만 쿼리 2천만개를 1초만에 해결해달라고 요구 했을 때, 이 코드의 시간복잡도를 보면 쿼리 2천만개 * (a에서 b의 합 구하는 for 문의 최악..