[프로그래머스 / Python] 파괴되지 않은 건물 - 누적합 (1차원, 2차원)

누적합 (Prefix sum)

• 누적합은 주어진 배열의 각 원소에 대해 그 원소를 포함하여 이전 모든 원소의 합을 계산한 값을 저장하는 알고리즘
• 특정구간의 원소의 연산을 여러번 하는 일반적인 경우,  지정된 인덱스부터 하나씩 더했을 때, 총 O(n^2) 가 소요됨.
• 누적합의 경우, 누적합 배열이 준비된 후 연산하면 배열의 크기에 비례하므로 시간복잡도가 총 O(n)
• 배열이 크거나 연산을 많이 실행할 경우에 자주 쓰임

 

 

1. 1차원 배열 누적합

ex) 자연수의 누적합

index	0	1	2	3	4
arr	1	2	3	4	5
prefix_sum	1	3	6	10	15

 

arr[i] = prefix_sum[i] - prefix_sum[i-1]

 

• [BOJ] 태상이의 훈련소생활[19951번] - https://www.acmicpc.net/problem/19951
• ex) 배열의 0~4번 index의 value를 -3 해줘야 하는 경우
• [-3, -3, -3, -3, -3 , 0, 0, 0, 0, 0] 을 하게 되면 총 5번의 연산이 필요
• 하지만, 누적합을 적용한 경우 (시작구간) 과 (끝 구간 + 1) 의 index에만 값을 넣으면 2번의 연산으로 표현할 수 있음

prefix_set = [-3, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0]

for i in range(1, n+1):
	prefix_set[i] += prefix_set[i-1]


print(prefix_set) 
# [-3, -3, -3, -3, -3, 0, 0, 0, 0, 0, 0]

• N보다 1 큰 배열을 만들어서 i 번째에 -3을 넣고
• ( i + 4) + 1 번째 index에 -1을 곱한 값을 넣으면 누적합 표현을 완성할 수 있음
• 이후 i = 1에서 i = n 까지 prefix_set[i] += prefix_set[i-1] 을 시행

 

2. 2차원 배열 누적합

• 2차원 배열의 누적합은 1차원 배열의 누적합 개념을 확장한 것
• 각 원소가 포함된 직사각형 영역의 합을 미리 계산하여 저장
• 역누적합 과정을 거쳐서 제작 (1번, 2번 과정의 순서는 무관)

1. 열방향 역누적합 (세로방향)

0	0	0	0	0
0	1	1	1	0
0	1	1	1	0
0	1	1	1	0
0	0	0	0	0

0	0	0	0	0
0	1	1	1	0
0	0	0	0	0
0	0	0	0	0
0	-1	-1	-1	0

 

 

 

 

          역누적합 → 

 

 

            ← 누적합

 

 

 

 

 

2. 행방향 역누적합 (가로방향)

0	0	0	0	0
0	1	1	1	0
0	0	0	0	0
0	0	0	0	0
0	-1	-1	-1	0

0	0	0	0	0
0	1	0	0	-1
0	0	0	0	0
0	0	0	0	0
0	-1	0	0	1

 

 

 

          역누적합 → 

 

 

            ← 누적합

 

 

 

 

• 이후 누적합 과정을 가로 → 세로 과정으로 수행하면 최종 상태의 이차원 배열을 얻을 수 있음

ex)  [프로그래머스] 파괴되지 않은 건물 - https://school.programmers.co.kr/learn/courses/30/lessons/92344

 

def solution(board, skill):
    R = len(board)
    C = len(board[0])
    
    # 1. 2차원 누적합 배열 생성
    prefix_sum = [[0]*(C+1) for _ in range(R+1)]
    
    # 2.  역누적합 지점 연산
    for skill_set in skill:
        ty,r1,c1,r2,c2,dmg = skill_set
        dmg =  dmg if ty == 2 else -1*dmg
        
        prefix_sum[r1][c1] += dmg
        prefix_sum[r1][c2+1]  -= dmg
        prefix_sum[r2+1][c1] -= dmg
        prefix_sum[r2+1][c2+1] += dmg
    
    # 3. 열방향 누적합
    for j in range(R+1):
        for i in range(1,C+1):
            prefix_sum[j][i] += prefix_sum[j][i-1]
    
    # 4. 행방향 누적합
    for i in range(C+1):
        for j in range(1,R+1):
            prefix_sum[j][i] += prefix_sum[j-1][i]

    
    answer = 0
    # 5. 최종 연산
    for i in range(R):
        for j in range(C):
            board[i][j] += prefix_sum[i][j]
            if board[i][j] > 0:
                answer += 1
    return answer