프로그래밍 면접 문제 2 : Matrix Region Sum

 

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 질문 1 : Array Pair Sum

 

이 문제는 매우 우아한 질문이라고 할 수 있습니다. 처음 접근은 쉽지만 효율적인 해답을 찾기위해서는 매우 노력해야하기 때문입니다: 정수형 행렬과 행렬 내 사각형 영역을 나타내는 좌표가 주어지면, 이 사각형 영역 안의 수를 모두 더한 값을 구하는 문제입니다. 프로그램은 동일한 행렬의 다른 사각형 영역에 대해서 여러번 실행됩니다.

매우 쉬워보입니다. 간단하게 루프를 중첩해서 숫자를 더하면 됩니다. 행렬과 사각형 영역의 왼쪽 상단, 오른쪽 하단 좌표가 주어졌을 때 숫자를 모두 더하는 알고리즘은 다음과 같습니다:

def matrixRegionSum1(matrix, A, D):
    if len(matrix)==0:
        return
    totalSum=0
    for i in range(A[0], D[0]+1):
        for j in range(A[1], D[1]+1):
            totalSum+=matrix[i][j]
    return totalSum

이 풀이법의 복잡도는 O(MN)입니다. 여기서 M은 행렬에서 행의 갯수이고, N은 열의 갯수입니다. 이 풀이법은 매우 직관적인 해결책으로 문제를 처음 만났을 때 머리에 바로 떠오를 수 있습니다. 하지만, 이 방법은 데이터를 캐싱(caching)해서 사용하지 않고, 프로그램에서 지속적으로 호출되는 코드는 동일한 복잡도를 갖기때문에, 최적화와는 거리가 멀다고 할 수 있습니다. 이 루틴은 여러번 실행되기 때문에, 함수를 호출할 때마다 너무 많은 양의 공간을 차지하지 않고 일정한 시간 O(1)만 소요되는 방법이 이상적입니다.

복잡도를 O(1)으로 줄이기 위해서 미리 계산한 다음 캐시(cache)에 저장을 해두는 것이 좋습니다. 미리 계산하는 과정의 복잡도는 처음 시작할 때 한번만 실행되기 때문에 그리 중요하지 않고, 함수 호출이 지속될 때 속도를 높이는데 캐싱된 데이터가 사용됩니다. 어떤 걸 미리 계산할 수 있는지 살펴보겠습니다. O(1) 복잡도를 가진 풀이를 위해서, 가능한 모든 사각형 영역에 대해서 그 합을 미리 구해놓고, 나중의 사용을 하기 위한 용도로 해시테이블에 저장해둡니다. 그런 다음, 사각형 영역에 대한 합이 필요할 때, 미리 구해놓은 값을 반환하면 일정한 시간에 답을 구할 수 있습니다. 하지만, 이 접근 방법의 공간 복잡도는 O(M^2N^2)이기 때문에 너무 많이 소모됩니다. 사각형 영역의 왼쪽 상단과 오른쪽 하단을 이루는 서로 다른 경우의 수가 MxN이기 때문입니다.

모든 사각형 영역에 대한 합을 미리 계산해서 캐시에 저장하는 방법은 일정한 시간의 복잡도를 갖는 알고리즘이지만, 공간을 너무 많이 차지합니다. 공간 복잡도를 허용할 수 있을만한 수준으로 줄일 수 있는지 생각해보겠습니다. 공간 측면에서 가장 비효율적인 부분은 가능한 모든 사각형 영역에 대한 합을 저장하는 부분입니다. 그 대신, 전체를 저장하지 않고 부분 집합에 대한 결과를 저장하면 일정한 공간 복잡도를 가진 풀이를 얻을 수 있습니다. 이제 가능한 모든 사각형 영역에 대한 합을 계산해보겠습니다. 위의 사진에서 ‘O’가 왼쪽 상단(행렬의 왼쪽 상단)을 가리키며 오른쪽 하단은 행렬에서 모든 지점이 될 수 있습니다. 사각형 영역의 오른쪽 하단 좌표만 자유롭기 때문에, 이를 위해서 미리 계산되는 영역의 왼쪽 상단 좌표를 수정하고 캐시에 저장하는 합의 수를 O(MN)으로 줄입니다. 이제 문제는 왼쪽 상단 지점이 ‘O’인 사각형 영역에 대한 합을 미리 계산한 결과를 이용해서 가능한 모든 사각형 영역에 대한 합을 구할 수 있는지 여부입니다. 분명히 할 수 있고, 동작 방식은 아래 그림과 같습니다:

임의의 사각형 영역 ABCD가 주어지면, 미리 계산해둔 왼쪽 상단 좌표가 ‘O’인 사각형 영역의 합 4개를 이용해서 답을 구할 수 있습니다.

멋지죠? 아래 코드는 왼쪽 상단 좌표가 ‘O’인 모든 사각형 영역에 대한 합을 미리 구하는 코드입니다. 합을 효율적으로 구하기 위해서 다이나믹 프로그래밍을 사용했습니다. 복잡도는 O(MN)이고, MN 개의 서로 다른 사각형 영역에 대한 합을 구하고 있기 때문에 효율적인 코드라고 할 수 있습니다. 따라서 각 영역의 합은 다이나믹 프로그래밍에 의해서 미리 구한 사각형 영역의 합을 이용해서, O(1)시간으로 구할 수 있습니다.

def precomputeSums(matrix):
    topRow, bottomRow=(0, len(matrix)-1)
    leftCol, rightCol=(0, len(matrix[0])-1)
    sums=[[0]*(rightCol-leftCol+1) for i in range(bottomRow-topRow+1)]
    sums[topRow][leftCol]=matrix[topRow][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        sums[topRow][col]=sums[topRow][col-1]+matrix[topRow][col]
    for row in range(topRow+1, bottomRow+1):
        sums[row][leftCol]=sums[row-1][leftCol]+matrix[row][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        columnSum=matrix[topRow][col]
        for row in range(topRow+1, bottomRow+1):
            sums[row][col]=sums[row][col-1]+matrix[row][col]+columnSum
            columnSum+=matrix[row][col]
 
    return sums

미리 계산한 결과를 얻으면, 위의 공식을 이용해서 가능한 모든 사각형 영역에 대한 합을 구할 O(1)의 복잡도로 구할 수 있습니다.

def matrixRegionSum2(matrix, A, D, sums):
    if len(matrix)==0:
        return
 
    if A[0]==0 or A[1]==0:
        OA=0
    else:
        OA=sums[A[0]-1][A[1]-1]
 
    if A[1]==0:
        OC=0
    else:
        OC=sums[D[0]][A[1]-1]
 
    if A[0]==0:
        OB=0
    else:
        OB=sums[A[0]-1][D[1]]
 
    OD=sums[D[0]][D[1]]
 
    return OD-OB-OC+OA

사전 계산, 다이나믹 프로그래밍, 고민이 더해져서 쉬웠던 문제를 매우 효율적으로 해결할 수 있기 때문에 개인적으로 이 문제를 참 좋아합니다.

다음글 – 프로그래밍 면접 질문 3 : Largest Continuous Sum

 

내용 끝까지 읽어주셔서 감사합니다.
배너 클릭은 저에게 많은 힘이 됩니다.
감사합니다 🙂