배열: 1차원과 2차원

순회·누적합·차분, 그리고 격자를 다루는 기본기.

개념

배열은 인덱스로 원소에 바로 접근할 수 있어 읽기와 쓰기가 O(1)이에요. 대신 중간에 끼워 넣거나 빼면 뒤쪽 원소를 전부 밀어야 해서 O(n)이에요. 이 비대칭이 나중에 큐를 배열로 만들면 안 되는 이유(10주차)로 이어져요.

맨 뒤에 넣고 빼기는 빨라요 — JS push/pop, Python append/pop
맨 앞에 넣고 빼기는 느려요 — JS unshift/shift, Python insert(0, x)/pop(0)
길이를 미리 알면 Array(n).fill(0) / [0] * n 으로 한 번에 만드는 편이 나아요
잘라내기는 복사예요 — slice / nums[a:b] 는 O(잘라낸 길이)

2차원 배열

격자·행렬·지도는 전부 2차원 배열이에요. 앞으로 나올 격자 BFS(16주차), 2차원 DP(20주차), 시뮬레이션(4주차)이 모두 여기서 출발하니까, 만들고 훑는 법을 지금 확실히 해둬요.관례는 grid[행][열], 즉 grid[y][x] 예요. 문제 설명이 (x, y) 좌표로 쓰여 있으면 코드와 순서가 뒤집히니까, 어느 쪽을 첫 번째 인덱스로 쓸지 시작할 때 정하고 끝까지 지켜요. 중간에 섞이면 예제는 통과하고 제출은 틀리는 상태가 돼요.

누적합

누적합은 출발점부터의 '러닝 표시'가 적힌 자라고 생각하면 쉬워요. 마라톤 코스에 1km마다 '여기까지 누적 오르막 몇 m' 팻말이 꽂혀 있다고 해봐요. 3km 팻말과 7km 팻말을 보면, 그 사이 구간의 오르막은 두 값을 빼기만 하면 나와요. 구간을 처음부터 다시 세지 않아도 되죠. 누적합이 딱 그 팻말이에요.구간 합을 여러 번 물어보는 문제에서, 매번 그 구간을 더하면 질문 하나당 O(n)이에요. 앞에서부터 더한 값을 미리 만들어 두면 어떤 구간이든 뺄셈 한 번, 즉 O(1)에 답할 수 있어요. 질문이 10만 개면 O(n·q)가 O(n+q)로 줄어들어요.prefix 배열의 길이를 n+1로 잡고 prefix[0] = 0 으로 두는 게 요령이에요. 그러면 l이 0일 때를 따로 처리하지 않아도 돼요 — 구간 [l, r]의 합이 언제나 prefix[r+1] - prefix[l] 이에요.작은 배열로 직접 채워 볼게요. nums의 각 칸을 왼쪽부터 더해 가며 prefix를 만들고, 구간 [1, 3]의 합을 뺄셈 한 번으로 구해요.

nums=[3,1,4,1,5] — prefix를 채우고 구간 [1,3] 합 구하기
인덱스 i     0   1   2   3   4
nums         3   1   4   1   5
prefix[0] = 0
prefix[1] = prefix[0] + nums[0] = 0 + 3 = 3
prefix[2] = prefix[1] + nums[1] = 3 + 1 = 4
prefix[3] = prefix[2] + nums[2] = 4 + 4 = 8
prefix[4] = prefix[3] + nums[3] = 8 + 1 = 9
prefix[5] = prefix[4] + nums[4] = 9 + 5 = 14
prefix        0   3   4   8   9   14
구간 [1,3] 합 = nums[1]+nums[2]+nums[3] = 1+4+1 = 6
         빠르게 = prefix[4] - prefix[1] = 9 - 3 = 6

직접 더한 1+4+1도 6, 팻말 뺄셈 9-3도 6이에요. 구간이 아무리 길어도 뺄셈은 딱 한 번이라 O(1)이에요. prefix[4]-prefix[1]에서 4가 r+1, 1이 l인 것만 잘 챙기면 돼요.

차분 배열

누적합의 반대 방향이에요. 구간에 값을 여러 번 더해야 할 때 써요. 구간 [l, r]에 x를 더하려면 차분 배열의 l에 +x, r+1에 -x만 기록해요. 모든 갱신을 마친 뒤 누적합을 한 번 취하면 최종 배열이 나와요.

상황	도구	효과
구간 합을 여러 번 조회, 값은 안 바뀜	누적합	조회 `O(1)`
구간에 값을 여러 번 더함, 조회는 마지막에	차분 배열	갱신 `O(1)`
갱신과 조회가 뒤섞임	세그먼트 트리 (이 과정 범위 밖)	둘 다 `O(log n)`

패턴 코드

2차원 배열 만들고 훑기행 개수와 열 개수를 변수로 먼저 꺼내두면 경계 조건을 쓸 때 헷갈리지 않아요.

javascript
Copy code
const rows = grid.length;
const cols = grid[0].length;
const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
for (let y = 0; y < rows; y++) {
  for (let x = 0; x < cols; x++) {
    if (grid[y][x] === 1) seen[y][x] = true;
  }
}

누적합으로 구간 합을 O(1)에 답하기prefix[i]는 앞에서부터 i개의 합이에요. 구간 [l, r]의 합은 prefix[r+1] - prefix[l].

javascript
Copy code
const prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
  prefix[i + 1] = prefix[i] + nums[i];
}
const rangeSum = (l, r) => prefix[r + 1] - prefix[l];

차분 배열로 구간 갱신갱신은 O(1), 마지막에 누적합을 한 번 취해 실제 배열을 복원해요.

javascript
Copy code
const diff = new Array(n + 1).fill(0);
for (const [l, r, x] of updates) {
  diff[l] += x;
  diff[r + 1] -= x;
}
const result = new Array(n).fill(0);
let running = 0;
for (let i = 0; i < n; i++) {
  running += diff[i];
  result[i] = running;
}

이번 주 문제

이번 주 진행0 / 4

주차 진행률

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.

배열 맨 앞에 원소를 넣는 연산이 O(n)인 이유를 설명할 수 있는가?
[[0] * m] * n 이 왜 위험한가?
누적합과 차분 배열은 각각 어떤 상황에서 쓰는가?

← 1주차 · 시작하기: 문법과 복잡도 3주차 · 문자열 →