누적합

📖 문제 https://www.acmicpc.net/problem/2118   💡  풀이 방식• 누적합, 투 포인터 N가지 지점 中 2가지를 뽑는 경우의 수는 N * (N-1)/2이고, 이러면 약 12억 5천만을 넘으므로 시간 초과가 발생한다.그러므로 투 포인터로 두 지점을 뽑는다. 그리고 나서 정방향 / 역방향으로 진행하며 최대 거리를 구한다.   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243import java.util.*;import java.io.*; public class Main {    public static void main(String[] args) throws IOException..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 누적합 (시간 복잡도 : O(N+M) = O(N)) 필요 자료구조 - 모든 skills에 대한 처리를 저장할 누적합 2차원 배열 💥 1. 반복문으로 스킬 배열을 돌며 새로 생성한 누적합 배열에 degree를 배치한다. 2. 가로 누적합과 세로 누적합을 구한다. 3. 건물 배열과 누적합 배열의 값을 더한 값이 0보다 크다면 붕괴되지 않은 건물이므로 정답 +1한다. 💥 유의사항 - O(N * M * K)했다간 시간 초과가 발생한다. 그래서 누적합으로 해결 - N+1, M+1까지 계산 가..

📖 문제 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 💡 풀이 방식 • (i,j) ~ (x,y) 구간에 대한 누적합을 구한다. 1) 초기 2차원 누적합 행렬은 다음과 같이 채운다. dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j]; 2) 부분 행렬의 값은 다음과 같이 구한다. dp[x][y] - dp[x][j - 1] - dp[i - 1][y] + dp[i - 1][j - 1] 💥 유의사항 dp[N][M..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 누적합 1. int형 일차원 배열을 생성해 시작 위치인 입실 시간에 1을 추가하고, 퇴실 + 청소 시간 위치에 -1을 한다. (배열의 최대 크기는 24 * 60 + 10로 설정) 2. 반복문을 이용해 현재의 값에 이전 값을 더하며, 이 중 최댓값을 구하고 생신한다. (누적합) 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { priva..

🔺 문제

🔺 문제 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 🧩 해결 아이디어 • 브루트포스, 2차원 누적합 1. dp 배열을 채운다. dp 배열의 왼쪽 값 + dp 배열의 위쪽 값 - 2번 받아 중복되는 dp 배열의 왼쪽 위 대각선 값 + map 배열의 현재 위치 값 2. dp 배열을 돌며 최댓값을 구한다. 💥 유의사항 최댓값 비교 할 때, long형으로 받고 비교해야 한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

🔺 문제 14929번: 귀찮아 (SIB) n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main { static int[] arr, sum; static int N; static long ans = 0; public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..

🔺 문제 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🔺 코드 1) 누적 합 풀이 - 시간 복잡도 : O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

🔺 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..