2차원누적합

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..

🔺 문제

🔺 문제 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 ..