🦾 오늘의 컨디션 및 특이사항(개인 일정 등)
- 수면 시간
- 7시간
- 학습 시간
- 12 : 00 ~ 13 : 30
- 18 : 30 ~ 20 : 00
- 특이사항
📑 세부 학습 내용
📅 스케쥴
- 1시간 30분 코딩테스트 및 풀이 리뷰 + 1시간 30분 개념 학습 및 블로그 정리
- 총 3시간
✏️ 코딩 테스트
- 1 SOLVE 및 깃허브 커밋
- 프로그래머스 -
92344 - 문제 유형 :
차분 배열,누적합,시뮬레이션/구현 - https://github.com/oneplast/ProgrammersCT/commit/3a593170cc97c9704ac43f4a50eefad63c93ee4c
⭕ 문제 풀이
class Solution {
int n;
int m;
int[][] dp;
public int solution(int[][] board, int[][] skill) {
n = board.length;
m = board[0].length;
dp = new int[n + 1][m + 1];
fillDp(skill);
sumDp();
return n * m - getDestroyCnt(board);
}
private void fillDp(int[][] skill) {
for (int[] ints : skill) {
int type = ints[0];
int r1 = ints[1];
int c1 = ints[2];
int r2 = ints[3];
int c2 = ints[4];
int degree = ints[5];
if (type == 1) {
degree = -degree;
}
dp[r1][c1] += degree;
if (c2 + 1 <= m) {
dp[r1][c2 + 1] -= degree;
}
if (r2 + 1 <= n) {
dp[r2 + 1][c1] -= degree;
}
if (r2 + 1 <= n && c2 + 1 <= m) {
dp[r2 + 1][c2 + 1] += degree;
}
}
}
private void sumDp() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i > 0) {
dp[i][j] += dp[i - 1][j];
}
if (j > 0) {
dp[i][j] += dp[i][j - 1];
}
if (i > 0 && j > 0) {
dp[i][j] -= dp[i - 1][j - 1];
}
}
}
}
private int getDestroyCnt(int[][] board) {
int destroyCnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
board[i][j] += dp[i][j];
if (board[i][j] < 1) {
++destroyCnt;
}
}
}
return destroyCnt;
}
}
- 차분 배열 및 누적합을 이용한 풀이
- 3중 반복문을 이용한 풀이는 시간복잡도가 높아, 해당 문제를 성공적으로 통과할 수 없음
- 최종 시간복잡도 :
O(N * M)sumDp()및getDestroyCnt()에서의 이중 반복문 :O(N * M)fillDp()는O(S)->S는skill.length- 최종 시간복잡도 :
O(S + N * M)->O(N * M)
💡 어려웠던 것 || 알게 된 것
📌 차분 배열
- 배열을 효율적으로 업데이트하는 기법
- 구해야하는 배열의 특정 범위 값을 미리 한 번에 업데이트하고, 이를 누적합을 이용하여 나중에 계산하는 방식
- 변화량을 빠르게 기록한 후, 복원 시 누적합으로 전체 변화를 한 번에 반영
1️⃣ 1D 차분 배열
int[] board = {5, 3, 2, 7, 1};
// [1, 4] 구간에 각각 5씩 더하시오board배열의 크기보다 1 큰 배열 생성board배열의 크기n은 5- 크기가 6인
dp배열 생성, 모두 0으로 초기화
- 구해야 하는 범위 중, 시작점에 +5, 끝점 다음 점에 -5
dp = [0, 5, 0, 0, 0, -5]
dp의 각 인덱스 별 누적합 계산누적합 = [0, 5, 5, 5, 5, 0]
0 <= i < n범위까지의board[i] + dp[i]수행board = [5, 8, 7, 12, 6]- 최종적으로 구간 내 계산 완료
2️⃣ 2D 차분 배열
int[][] board = {{5, 5, 5, 5, 5}, {5, 5, 5, 5, 5},
{5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}}
// [0, 0] ~ [3, 4] 구간에 각각 4씩 더하시오
// r1, c1 = 0, 0 (구간 시작점)
// r2, c2 = 3, 4 (구간 종료점)
n = board.length,m = board[0].lengthn = 4,m = 5
- 크기가
[n + 1][m + 1]인dp배열 생성, 모두 0으로 초기화dp = {{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0}}
- dp[r1][c1] 및 dp[r2 + 1][c2 + 1]에 +4
[0, 0] += 4,[4, 5] += 4
- dp[r2 + 1][c1] 및 dp[r1][c2 + 1]에 -4
[4, 0] -= 4,[0, 5] -= 4
- 인덱스 마다 인덱스 -1 까지의 누적합 계산
- 행(가로) 누적합과 열(세로) 누적합을 덧셈
- 중복 계산이 발생하기 때문에
dp[i - 1][j - 1]의 누적합을 한 번 차감dp[i - 1][j]까지의 누적합과dp[i][j - 1]까지의 누적합에는dp[i - 1][j - 1]까지의 누적합이 중복되어 있으므로, 한 번을 제거
- 이러한 과정을 통해 각 행/열의 연산 필요 값 저장
0 <= i < n및0 <= j < m범위까지의board[i][j] + dp[i][j]수행- 최종적으로 구간 내 계산 완료
기록