From previous blog..
오전에 트라이하고 40분동안 못끝내서 오후에 해설을 보고 이해를 한 후 푼 문제.
사실 문제의 해설을 보고 처음에 '와! 신선한 개념이다!' 라고 생각했었던 로직이었지만 알고보니 누적합이라는 -정말 코딩테스트 대비를 하는 초기에 배웠던, 그리고 배운 후 써먹질 않아서 기억에 잊혀졌던..- 기초적인 방법을 2차원으로 확장시킨 문제였다..
이번 문제같은 경우 자세한 풀이는 생략하고, 누적합이 어떤 개념인지(+ 2차원 상에서의 누적합이 어떤 개념인지), 그리고 어떤 방식으로 풀이가 이루어지는 것인지, 간단히 그 예시를 통해 설명을 해보려고 한다.
우선 누적합을 설명하기에 앞서 한개의 배열을 생각해보자.
x = [1, 0, 0, -2, 0, 5, 8, 3, 0]누적합이라는 것은 배열이 주어졌을 때 각 원소에서 자기 자신을 포함해서 합산을 시켜가며 나아가는 방법이다. 위의 x를 예시로 들어 설명해보자. 우선 x를 누적합 했을 때 나오는 결과물은
[1, 1, 1, -1, -1, 4, 11, 14, 14]이다. 그리고 이를 만들게 되는 계산방법은 바로 앞의 숫자를 계속해서 합해주며 나가는 것이다.
for i in range(1,len(x)):
x[i] += x[i-1]여기서 주의깊게 보고 넘어가면 좋을 지점은 누적합을 어떻게 이용하면 좋을까? 에 대한 지점이다.
예시로 x1이라는, 길이가 5인 새로운 배열을 생각해보자.
x1 = [0, 0, 0, 0, 0]이때 우리는 누적합을 이용해서 x1의 2번째 원소부터 4번째 원소까지 2를 추가해주는 작업을 할 것이다. 그리고 그 결과는
x1 = [0, 2, 2, 2, 0]가 된다. 그리고 이를 시행하기 직전의 누적합은
[0, 2, 0, 0, -2, 0]이 나온다는 것을 기억하자!...(*)
이제 이차원 행렬상의 누적합을 생각해보자. 여기서는 y라는 이중배열을 사용할 예정이다.
y =
[[1,2,3,4],
[0,0,0,0],
[-4,-3,-2,-1],
[1,0,0,0]]이 때 y의 누적합은
[[1,3,6,10],
[1,3,6,10],
[-3,-4,-3,0],
[2,4,7,1]]이 된다. 그리고 이 행렬은 i,j에 원소가 있을 때 그 원소보다 큰 수의 행 또는 열에 있는 수를 모두 더해주며 합을 계산했을 때 나온다.
그리고 이제 문제로 돌아가서, 처음에 내가 어떤 방법으로 풀이를 썼는지, 그리고 누적합을 사용했을 때 문제의 풀이방법이 어떻게 바뀌게 되는지 살펴보자.
우선 초기의 내 풀이방법은 이벤트가 있을 때 마다 계산을 하는 일반적인 방식을 사용했다.(문제의 자세한 설명은 누적합에서 간단히 소개할 수도 있지만.. 위에 첨부한 문제의 링크를 보고 온 후 설명을 보는 것을 추천한다. (초기 풀이에 걸리는 시간은 O( len(board)*len(board[0])*len(skill) ) )
import numpy as np
def solution(board, skill):
board = np.array(board)
for i in skill:
if i[0] == 1:
board[i[1]:i[3]+1,i[2]:i[4]+1] -= i[5]
if i[0] == 2:
board[i[1]:i[3]+1,i[2]:i[4]+1] += i[5]
cnt = 0
for i in board:
for j in i:
if j > 0:
cnt += 1
return cnt그리고 누적합을 사용했을 때의 풀이방법은 다음과 같다.
import numpy as np
def solution(board, skill):
n = len(board[0]) # row
m = len(board) # col
board = np.array(board)
onboard = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in skill:
if i[0] == 1:
onboard[i[1]][i[2]] -= i[5]
onboard[i[1]][i[4]+1] += i[5]
onboard[i[3]+1][i[2]] += i[5]
onboard[i[3]+1][i[4]+1] -= i[5]
if i[0] == 2:
onboard[i[1]][i[2]] += i[5]
onboard[i[1]][i[4]+1] -= i[5]
onboard[i[3]+1][i[2]] -= i[5]
onboard[i[3]+1][i[4]+1] += i[5]
onboard = np.array(onboard)
for i in range(m):
onboard[i+1] += onboard[i]
for j in range(n):
onboard[i][j+1] += onboard[i][j]
board += onboard[0:m,0:n]
cnt = 0
for i in board:
for j in i:
if j > 0:
cnt += 1
return cnt최종적으로 우리가 계산해야할 것은 skill이 다 돌게 되었을 때, board에서 0보다 큰 값을 가진 지역이 몇개가 있느냐는 것이다.
이 풀이에서는 누적합의 방식을 사용할 것이기 때문에 기본으로 주어지는 board를 냅두고, 초기에 계산을 할 onboard를 하나 만들어 줄 필요가 있다.
onboard = [[0 for _ in range(n+1)] for _ in range(m+1)]이 때 위의 (*)를 상기시키면서 skill의 원소에 따라 onboard에 원소를 추가해주는 작업을 할 것이다.
for i in skill:
if i[0] == 1:
onboard[i[1]][i[2]] -= i[5]
onboard[i[1]][i[4]+1] += i[5]
onboard[i[3]+1][i[2]] += i[5]
onboard[i[3]+1][i[4]+1] -= i[5]
if i[0] == 2:
onboard[i[1]][i[2]] += i[5]
onboard[i[1]][i[4]+1] -= i[5]
onboard[i[3]+1][i[2]] -= i[5]
onboard[i[3]+1][i[4]+1] += i[5]여기서는 이차원 행렬을 기준으로 누적합을 잡는 것이기 때문에 모서리의 원소에 숫자를 맞춰줄 필요가 있다.
예시를 하나 생각해보자. 5x5 행렬(여기서는 이중배열) y1을 생각해보자.(여기서는 코드를 기준으로 설명을 할 예정이다. 즉, 모든 시작은 0이다.)
y1의 (2,2) 원소와 (3,4) 원소 사이에 2를 더해준다고 가정한다. 그러면 y1의 onboard에서는 다음과 같은 숫자가 들어가야 한다.
onboard_of_y1 =
[[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 2, 0, -2, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, -2, 0, 2, 0]]그리고 이를 계산해보면 y1에 합을 해줄 결과는 다음과 같이 나오게 된다.(마지막 행과 마지막 열을 제외시키는 것을 잊지 말자!)
[[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 2, 2, 0, 0],
[0, 0, 2, 2, 0, 0],
[0, 0, 2, 2, 0, 0],
[0, 0, 0, 0, 0, 0]]그리고 이 방법을 조금 더 쉽게 이해해보고 싶다면, 직사각형 꼴의 벤다이어그램을 생각해보았을 때 원하는 집합의 형태를 어떻게 잡으면 될 지 y1의 onboard에 숫자를 하나씩 넣어보면서 살펴보면 좋을 것 같다.
그리고 마지막으로 풀이는 이런 방법을 통해 onboard에 모든 skill을 표시해준 뒤 모든 결과를 한번에 계산 후 board에 이를 적용시켜서 구해주는 문제가 된다.
이미 배웠던 좋은 로직을 일께워 준 것에 감사드립니다!
