알고리즘/누적합5

• BJ S1 11660 구간 합 구하기 5 - Java [문제링크]https://www.acmicpc.net/problem/11660 [문제]N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.[입력]첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000).. 알고리즘/누적합 2024. 10. 7.

• BJ S3 11659 구간 합 구하기 4 - Java [문제링크]https://www.acmicpc.net/problem/11659 [문제]수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.[입력]첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.[출력]총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.[예제 입력 1]5 35 4 3 2 11 32 45 5[예제 출력 1]1291 [설명]이 문제는 제한을 자세히 보아야 한다.제한에서 N과 M이 100,000까지 되므로 O(n^2)이 불가능하게 보인다.따라서 다른 방법을 찾아야 했고.. 알고리즘/누적합 2024. 10. 2.

• 

  BJ_G5_3020_개똥벌레 - Java [문제링크] https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net [문제] 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서.. 알고리즘/누적합 2022. 6. 6.

• 

  BJ_S3_2559_수열 - Java [문제링크] https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net [문제] 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 .. 알고리즘/누적합 2022. 6. 6.

• 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물 [문제링크] https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr [설명] 이 문제는 완전탐색으로 풀었는데 효율성에서 통과하지 못하였습니다. 찾아보니 다른분들께서 누적합으로 풀은 것을 볼 수 있습니다. 누적 합으로 푸는 방법 1) sum이라는 배열을 만든다.(b.. 알고리즘/누적합 2022. 6. 5.