초기 체스판 상태와 기본 패턴 차이

먼저, 4x4 체스판을 예로 들어 설명하겠습니다. 체스판의 각 셀이 'B'(Black) 또는 'W'(White)로 표시되어 있다고 가정합니다. 기본 패턴은 교차하는 'B'와 'W'입니다.

처음 체스판 상태 (Board)
B W B W
W B W B
B W B W
W B W B

기본 패턴 (Pattern)
B W B W
W B W B
B W B W
W B W B

기본 패턴과의 차이 계산

이제 체스판과 기본 패턴과의 차이를 계산합니다. 같으면 0, 다르면 1로 표시합니다.

차이 (Difference)
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

누적 합 계산

누적 합을 계산하여 각 셀에 저장합니다. 누적 합은 왼쪽 상단부터 시작하여 현재 위치까지의 합을 나타냅니다.

누적 합 (Cumulative Sum)
0 0 0 0
1 2 3 4
1 2 3 4
2 4 6 8

누적 합을 사용한 구간 합 계산

누적 합을 사용하여 특정 영역의 합을 계산할 수 있습니다. 예를 들어, 아래 2x2 영역의 합을 계산해 보겠습니다.

선택된 영역
1 1
0 0

이 영역의 합은 누적 합 배열에서 아래 오른쪽 셀의 값에서 위쪽 및 왼쪽 셀의 값을 빼고, 두 번 뺀 왼쪽 상단 셀의 값을 다시 더하여 계산할 수 있습니다. 이 경우, **(2 - 1 - 1 + 0) = 0**입니다.

시각화

아래는 4x4 체스판의 일부분에 대한 누적 합 계산 방법을 시각화한 것입니다.

[0, 0, 0, 0]       [0, 0, 0, 0]
[1, 2, 3, 4]  ->   [1, 2, 3, 4]  ->  [1, 1]
[1, 2, 3, 4]       [1, 2, 3, 4]      [0, 0]
[2, 4, 6, 8]       [2, 4, 6, 8]

이 방법을 사용하면, 큰 배열에서도 특정 구간의 합을 효율적으로 계산할 수 있습니다.