개요

이번 2022 카카오 블라인드 채용 문제에서 문제 6. 파괴되지 않은 건물를 공부하면서 흥미로운 알고리즘을 알게되었다.

해당문제는 간단히 반복문을 사용하면 풀리는 문제이긴하나 그렇게 풀게되면 속도가 오래걸리는(2차원 배열을 입력(K)만큼 반복 O(M*N*K)) 문제가 발생하게 된다.
그래서 더욱 효율적인 방법으로 2차원 배열의 값을 더하고 빼야하는데 해당 문제에서는 속도 문제를 해결하기 위해서 누적합을 적용한다.

해당 글은 문제 풀이를 먼저 보고 풀이를 한 문제여서, 위의 문제풀이 링크를 따라가서 보시면 더 이해가 잘되실껍니다.

누적합

누적합은 말 그대로 누적된 합이다. 아래에는 간단한 1D array 예시이다.

# 기존의 array
arr = [0, 1, 5, 2, -3, 4]
# 누적합 array
ps_arr = [0, 1, 6, 7, 4, 8]

만약 위의 상황에서 arr[2]부터 arr[4] 사이의 합을 구하고 싶으면 기존 방법으로는 반복문을 사용하겠지만, 누적합을 사용하게 되면 간단하게 ps_arr[4] - arr[2-1]을 하면 된다.
반복문대신 인덱스로 계산을 하게 되면 속도는 O(n)에서 O(1)로 줄어들게 된다.

# arr: 누접합 배열
def sum_range(arr, start_index, end_index):
	return arr[end_index] - arr[start_index - 1] if start_index != 0 else 0

물론 2D array에도 적용이 가능하다.

위의 2차원 배열이 있다. 누접합 배열 구성은 2단계로 나눠진다. 1. 우선 왼쪽에서 오른쪽으로 누적합을 계산한다. 2. 위에서 아래로 누적합을 계산한다.

2차원 배열 누적합에서 한 원소의 값(arr[i][j])은 arr[0][0]에서 arr[i][j]의 합이다.
이제 여기서 원하는 범위의 값을 구하기 위해서는 아래의 공식대로 진행된다.

시작 점: x1, y1
끝 점: x2, y2


해당 범위의 값
s = arr[x2,y2] - arr[x2, y1-1] - arr[x1-1, y2] + arr[x1-1, y1-1]

위의 식을 그림으로 설명하면 아래와 같다.

만약 노란색 범위의 값을 구하고 싶으면 노란색 범위 합 - 초록색 범위 합 - 주황색 범위 합 + 파란색 범위 함 으로 하면 된다. 나중에 파란색 범위의 합을 더하는 이유는 노란색 범위는 구하기 위해서는 주황색 범위와 초록색 범위를 빼야하는데 파란색 부분이 중복되어 계산되기 때문에 한번더 파란색 범위를 더해준다.

문제

해당 파괴되지 않는 건물 문제는 2차원 배열을 다루는 문제이며, 입력의 수 만큼 2차원 범위 만큼 값을 업데이트를 해야한다.
해당 문제에서 2차원 범위의 값들을 효율적으로 업데이트 하는 방법에 대해서 원하는거 같았다.

효율적으로 업데이트하기위해서는 넓은 범위의 값들을 실시간이 아닌 모아서 한번에 업데이트 하는 방법이 있다. 하지만 2차원 범위의 값들을 모아두기에는 별다른 방법 없이는 반복문을 사용하게 된다.

그래서 효율적으로 2차원 배열의 값들을 모아두기 위해서 누적합을 적용한다.

우선, 1차원부터 생각을 해보면 원하는 범위에 같은 값을 적용하기 위해서는 시작과 끝은 합이 0이 되는 수여야하며, 가운데는 0이여야됩니다. 왜냐하면 왼쪽부터 합을 누적하기때문에 값의 변화를 막기위해 0이 있어야하며, 끝을 내기 위해서 원하는 범위 +1 위치에 반대의 수가 필요하다.
예를 들어 1차원 배열 중 0 - 3의 범위를 n으로 채우기 위해서는 0과 4에는 n, -n을 채워 넣는다. 그러고 누적합을 구하면 0 - 3의 범위는 n으로 채워지는것을 볼 수 있다.

n 0 0 0 -n -> n n n n 0

이제 2차원 개념으로 확장을 하게되면, 위의 왼쪽에서 오른쪽으로 더한값을 위에서 아래로 더해야한다.
마찬가지로 사잇값은 0으로 정해져 있어야하며, 끝 범위를 위해서 마지막 +1 에는 반대되는 수가 필요하다.

 n 0 0 0 -n           n  n  n  n  0        n n n n 0
 0 0 0 0 0            0  0  0  0  0        n n n n 0
 0 0 0 0 0     ->     0  0  0  0  0   ->   n n n n 0
 0 0 0 0 0            0  0  0  0  0        n n n n 0
-n 0 0 0 n           -n -n -n -n  0        0 0 0 0 0

위에서 아래로 더하게되면 원하는 범위에 원하는 값들을 채워 넣을 수 있습니다.
식으로 쓰게 되면, 아래와 같다.

원하는 범위: x1, y1, x2, y2
원하는 값: n

arr[x1  , y1  ] =  n # 왼쪽 위
arr[x2+1, y1  ] = -n # 오른쪽 위
arr[x1  , y2+1] = -n # 왼쪽 아래
arr[x2+1, y2+1] =  n # 오른쪽 아래

실행코드

def solution(board, skill):
    answer = 0
    
    # 크기 설정
    x, y = len(board[0]) + 1, len(board) + 1
    # 미리 빈 배열 만들어두기
    prefix_sum_array = [[0]*x for i in range(y)]

	# 입력별 값 표시해두기
    for _type, y1, x1, y2, x2, degree in skill:
        degree *= -1 if _type == 1 else 1
        
        prefix_sum_array[y1][x1] += degree
        prefix_sum_array[y1][x2+1] += -1 * degree
        prefix_sum_array[y2+1][x1] += -1 * degree
        prefix_sum_array[y2+1][x2+1] += degree
        
    # 누접합 계산하기
    # 왼쪽에서 오른쪽
    for i in range(x):
        for j in range(1, y):
            prefix_sum_array[j][i] += prefix_sum_array[j-1][i]
            
    # 위에서 아래
    for i in range(y):
        for j in range(1, x):
            prefix_sum_array[i][j] += prefix_sum_array[i][j-1]
    
    # 값 업데이트 및 조건 검사
    for i in range(y-1):
        for j in range(x-1):
            answer += 1 if board[i][j] + prefix_sum_array[i][j] > 0 else 0
    
    return answer