데브허브 | DEVHUB | Increment Submatrices by One - Leetcode 2536

N x N 행렬(초기 0)에 대해 주어진 여러 쿼리(부분 행렬 범위)에 따라 해당 부분 행렬의 모든 요소를 1씩 증가시킨 후 최종 행렬을 반환하는 문제입니다. 🎯
각 쿼리마다 부분 행렬을 직접 순회하며 증가시키면 Q * N^2의 시간 복잡도로 비효율적입니다. 🐢
최적화 목표는 Q + N^2 시간 복잡도를 달성하는 것으로, 이는 쿼리 처리 후 전체 행렬을 한 번만 순회하는 방식임을 시사합니다. 🚀
핵심 아이디어는 1차원 차이 배열(Difference Array) 기법을 2차원으로 확장하는 것입니다. 📈
1차원 차이 배열은 특정 범위 [start, end]를 증가시키려면 start에 +1, end+1에 -1을 표시한 후 누적합(prefix sum)을 계산하여 실제 값을 얻습니다. 🗺️
2차원 차이 행렬에서는 부분 행렬 (r1, c1)부터 (r2, c2)까지의 증가를 네 지점에 마킹하여 처리합니다:
- diff[r1][c1] += 1 (부분 행렬의 시작점) ➕
- diff[r1][c2 + 1] -= 1 (부분 행렬의 오른쪽 경계 바로 바깥) ➖
- diff[r2 + 1][c1] -= 1 (부분 행렬의 아래쪽 경계 바로 바깥) ⬇️
- diff[r2 + 1][c2 + 1] += 1 (오른쪽 아래 대각선 바깥, 이중 감소 상쇄) ↖️
최종 행렬의 각 셀 값은 result[r][c] = diff[r][c] + result[r-1][c] + result[r][c-1] - result[r-1][c-1] 공식을 사용하여 2차원 누적합 방식으로 계산됩니다. 이는 위, 왼쪽 값들을 더하고 중복 계산된 왼쪽 위 대각선 값을 빼는 방식입니다. 📊
차이 행렬은 N+1 크기로 생성하여 r2+1, c2+1 인덱스 접근 시 범위를 벗어나지 않도록 합니다. 📏
알고리즘 흐름은 다음과 같습니다:
1. N+1 크기의 0으로 채워진 차이 행렬을 초기화합니다.

N x N 행렬(초기 0)에 대해 주어진 여러 쿼리(부분 행렬 범위)에 따라 해당 부분 행렬의 모든 요소를 1씩 증가시킨 후 최종 행렬을 반환하는 문제입니다. 🎯
각 쿼리마다 부분 행렬을 직접 순회하며 증가시키면 Q * N^2의 시간 복잡도로 비효율적입니다. 🐢
최적화 목표는 Q + N^2 시간 복잡도를 달성하는 것으로, 이는 쿼리 처리 후 전체 행렬을 한 번만 순회하는 방식임을 시사합니다. 🚀
핵심 아이디어는 1차원 차이 배열(Difference Array) 기법을 2차원으로 확장하는 것입니다. 📈
1차원 차이 배열은 특정 범위 [start, end]를 증가시키려면 start에 +1, end+1에 -1을 표시한 후 누적합(prefix sum)을 계산하여 실제 값을 얻습니다. 🗺️
2차원 차이 행렬에서는 부분 행렬 (r1, c1)부터 (r2, c2)까지의 증가를 네 지점에 마킹하여 처리합니다:
- diff[r1][c1] += 1 (부분 행렬의 시작점) ➕
- diff[r1][c2 + 1] -= 1 (부분 행렬의 오른쪽 경계 바로 바깥) ➖
- diff[r2 + 1][c1] -= 1 (부분 행렬의 아래쪽 경계 바로 바깥) ⬇️
- diff[r2 + 1][c2 + 1] += 1 (오른쪽 아래 대각선 바깥, 이중 감소 상쇄) ↖️
최종 행렬의 각 셀 값은 result[r][c] = diff[r][c] + result[r-1][c] + result[r][c-1] - result[r-1][c-1] 공식을 사용하여 2차원 누적합 방식으로 계산됩니다. 이는 위, 왼쪽 값들을 더하고 중복 계산된 왼쪽 위 대각선 값을 빼는 방식입니다. 📊
차이 행렬은 N+1 크기로 생성하여 r2+1, c2+1 인덱스 접근 시 범위를 벗어나지 않도록 합니다. 📏
알고리즘 흐름은 다음과 같습니다:
1. N+1 크기의 0으로 채워진 차이 행렬을 초기화합니다.

로딩 중...

Increment Submatrices by One - Leetcode 2536 - Python

Run Text-to-Speech Locally (Chatterbox)

신입이 AI 서비스를 만들어왔다 ㄷㄷ #shorts

Optional Chaining in JavaScript

Build a 2D ACTION RPG in GameMaker (FREE)

ChatGPT가 사람들을 공격적으로 만든다?

[유니티][기간한정] Seamless - ShaderGraph Extension 에셋($20) 무료 다운로드