BOJ 11660) 누적합 구하기

2023-09-23 20:45:00

알고리즘 수업에서 백준 온라인 저지 문제를 내주셔서 해결해보았다.

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

문제 해결 과정

  1. 초기 아이디어

    처음 문제를 접하고 다음과 같은 과정으로 해결했다.

    1. N(표의 크기, N x N), M(합을 구해야 하는 횟수) 입력 받기
    2. N x N 의 표 입력 받기
    3. 네 개의 정수 x1, y1, x2, y2 로 이루어진 M개 행 입력 받기
    4. M 개 행 계산하기

    특히, 4번의 경우 코드를 아래와 같이 작성했다. 제대로 동작했지만 온라인 저지에서 제한 시간이 초과되는 문제를 발견했다.

    # M 개 행 계산하기
for k in range(M):
    cumsum = 0
    coordinate = coordinates[k]
    # x1부터 x2까지
    for i in range(coordinate[0], coordinate[2] + 1):
        for j in range(coordinate[1], coordinate[3] + 1):
            cumsum += a[i-1][j-1]
    print(cumsum)
    1
    2
    3
    4
    5
    6
    7
    8
    9

  2. 누적 합 사전 계산 방법

    시간 초과 문제를 모색하던 중 M번 누적합을 계산해서 실행시간이 오래 걸린 것이라고 생각해 누적합 행렬을 사전에 만들어 두고 이를 이용하는 방식으로 바꾸자 했다. (1,1) 부터 (x, y) 까지의 누적합을 미리 계산해두고 이를 이용하는 것이다. 기존 방법보다 다소 복잡하지만 더 빠른 속도를 보여준다.

    누적합 사전 계산 방법은 아 그림과 같은 방식으로 동작한다. (x1, y1) 부터 (x2, y2) 영역의 부분 누적합을 구하기 위해 (1,1) 부터 (x2, y2) 영역의 누적합을 구한 다음 해당 영역의 왼쪽부분과 위쪽 부분을 제거하는 것이다. 이때, (x1-1, y1-1) 까지의 누적합이 두번 제거되므로 반대로 더해줘야 한다.

    # M개 행에 대해 매번 누적합을 계산하는 것이 아닌, (0,0) 에서 (i,j)까지의 누적합을 계산한 것을 모아두고 조합한다.
cumsum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        cumsum[i][j] = a[i - 1][j - 1] + cumsum[i - 1][j] + cumsum[i][j - 1] - cumsum[i - 1][j - 1]
for k in range(M):
    [x1, y1, x2, y2] = coordinates[k]
    sum = cumsum[x2][y2] - (cumsum[x1 - 1][y2] + cumsum[x2][y1 - 1] - cumsum[x1 - 1][y1 - 1])
    print(sum)
    1
    2
    3
    4
    5
    6
    7
    8
    9

  3. 입력 내장 함수 성능 문제

    한 두줄 입력 받는다면 크게 상관 없지만, 여러 줄을 입력 받는 문제 상황에서 파이썬 내장 input 함수를 이용한다면 시간 초과 문제에 직면할 가능성이 높다. 왜냐하면 input 함수는 입력 받기 전 프롬포트 메시지를 파라미터로 받는데, 프롬포트를 인수로 전달하지 않더라도 오버헤드가 생성된다. 또, 개행문자가 포함된 입력 문자열에서 rstrip 함수를 적용시켜 입력받은 값의 개행 문자를 삭제시킨 뒤 리턴한다.

    따라서 여러 줄의 입력을 반복문으로 받으려면 sys 라이브러리의 sys.stdin.readline 메서드를 이용해야 한다. sys.stdin.readline을 이용하면 오버헤드 없이 빠른 입력이 가능하다. readline 메서드는 개행문자를 제거하지 않지만 데이터를 정수형으로 변환하는 상황이라 상관 없다. 아래 링크의 Github Repository 에서 input과 sys.stdin.readline을 포함한 많은 파이썬 함수들의 성능을 비교한다. 알고리즘 문제를 해결할 때 도움이 될 것 같다.

    https://github.com/xkumiyu/python-speed-comp (opens new window)

    Untitled