programmer life guidance 101

www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 16869 9717 7667 59.489% 문제 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음..

www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 367 115 88 31.655% 문제 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다. 동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각..

> 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 문의 최악..