구간 합

합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 알고리즘이다. 구간 합 알고리즘을 사용하기 위해선 합 배열을 만들어야 한다. 리스트 A가 있을 때 합 배열의 정의는 다음과 같다.

 

S[i] = A[0] + A[1] + ... + A[i] (A[0]부터 A[i]까지의 합)

 

합 배열은 기존 리스트를 전처리한 배열이라고 보면 된다. 합 배열을 통해 배열의 구간의 합을 구할 때 시간 복잡도가 O(N)에서 O(1)로 줄어든다.

 

 

🔑 합 배열 제작 공식

S[i] = S[i-1] + A[i] (전의 합 배열에서 새로운 원소를 더한다.)

 

🔑 구간 합 공식

A[i] + ... + A[j] = S[j] - S[i-1]

 

합 배열만 미리 구해두면 구간 합은 한번에 구할 수 있다. 구간 합은 코딩테스트에서 적재적소에 활용하면 시간복잡도를 줄일 수 있다.

 

 

구간 합 구하기 1

구간 합 구하기4로 바뀜

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ i ≤ j ≤ N

예제 입력 1 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 

12
9
1

 

1️⃣ 분석

 

합 배열을 이용한 구간합을 사용하지 않는다면, 100,000^2로 제한시간 1초를 넘어갈 것이다. 구간 합을 이용하자.

 

2️⃣ 손으로 풀어보기

 

구간 합 공식을 상기하자.

  • S[i] = S[i-1] + A[i] (파이썬 리스트는 처음에 크기를 정하지 않기 때문에 인덱스를 바로 사용할 수 없다.)
  • i, j 구간합 = S[j] - S[i-1]

 

3️⃣ 슈도 코드

 

슈도 코드에서 for문까지 적어주자. 합 배열을 만들 때 리스트 메소드 중 append를 활용하면, 크기를 정하지 않은 상태에서 원소를 추가할 수 있다. 이거의 시간복잡도는 O(1)이다. insert는 다른 거긴한데 얘는 O(N)을 알자.

 

4️⃣ 실제 코드 작성

이 코드는 동작이 안된다. 정리한 코드를 보고 다시 생각해보자.

N, M = map(int, input().split())
A = list(map(int, input().split()))
S = []
sum = 0

for i in range(N):
    if i == 0:
        S[i] = A[i]
    else:
        S[i] = S[i-1] + A[i]

for i in range(M):
    i, j = map(int, input().split())
    if i == 1:
        sum = S[j-1]
    else:
        sum = S[j-1] - S[i-2]
    
    print(sum)

리스트 자료구조의 특징 중 하나는 선언시 크기를 고정하지 않는다는 것이다. S 배열은 원소를 넣기 전 크기가 정해지지 않아 인덱스로 참조할 수 없다. 그래서 IndexError 오류가 나왔다.

이를 해결하고 싶으면 append 메소드를 이용해 S 배열에 원소를 하나씩 넣어줘야 한다.

 

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0]
temp = 0

for i in range(N):
    temp += A[i]
    S.append(temp)

for _ in range(M):
    i, j = map(int, input().split())
    sum = S[j] - S[i-1]
    print(sum)

S 배열에 temp (원소의 합)을 넣어줘 합 배열을 만든다. 이후 S 배열이 완성되었으므로 인덱스를 이용해 구간 합을 구할 수 있다.

그리고 S 배열을 초기화할 때 [0]을 넣어줘 초기화했는데, 이는 인덱스가 0이 아닌 1부터 시작하기 때문에 맞춰준 것이다. 이것도 활용하자.

 

🔑 배운 점

  • 리스트는 선언 시 크기가 정해지지 않는다. 물론 정해줄 순 있긴 하다. 인덱스를 이용해 참조할 땐 생각하자.
  • 인덱스를 맞추기 위해 [0] 원소를 넣는 방법도 있다.

 

구간 합 구하기 2 (11660)

문제

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

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

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

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 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 

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

예제 출력 1 

27
6
64

 

 

1️⃣ 분석

 

2차원 구간의 합을 구하는 문제이다. 합 배열을 이용하지 않는다면 문제의 조건인 제한 시간 1초를 만족하지 못한다.

다만 문제에서 요구하는 구간 합을 잘못 알았는데, 일자로 이어지는 구간이 아니라 좌표 2개가 만드는 직사각형의 구간의 합이다.

 

2️⃣ 손으로 풀어보기

 

완전히 잘못 풀었다. 밑의 다른 사진을 보고 왜 틀린지 알아보자.

2차원 구간 합을 구하는 방법

두 좌표가 만드는 사각형 내 값들의 합을 구하는 것이다. 합 배열을 구하는 방법, 구간 합을 구하는 방법 모두 달라진다.

책에서 제시한 방법은 특별한 공식을 유도하는 것인데, 합 배열 구하기 단락을 보자.

책에서는 문제에서 제시한 표보다 행과 열 모두 1칸씩 더 큰 (N+1) 배열을 만든다. 인덱스가 넘어가더라도 대응하기 위함이다.

 

💡합 배열 구하는 공식

  • S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]

S[i][j]은 A[1][1]과 A[i][j]가 만드는 사각형 내의 모든 값의 합이다. S[i][j-1]은 별이고 S[i][j-1]과 S[i-1][j]은 노트에서 각각 삼각형과 사각형이다. S[i-1][j-1]은 동그라미다. 새로운 사각형 구역 합을 구하기 위해 기존의 사각형 구역 합인 삼각형과 사각형을 더한다.

문제는 동그라미 구역(A[1][1]부터 A[i-1][j-1]이 만드는 구역, S는 관계없음)이 겹치기 때문에 중복된 동그라미를 빼준다.

마지막으로 구하고자 하는 구역의 마지막 조각인 A[i][j]를 더하면 원하는 합 배열이 완성된다.

 

 

💡구간 합 구하는 공식

  • sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

식만 봐서는 무슨 말인지 모른다. 노트의 구간 합 구하기 파트를 보자. 합 배열이 아닌 원래 배열 A에서 12번 좌표와 6번 좌표가 만드는 구역의 값을 구하고 싶다.

합 배열로 돌아와서 합 배열 12번에는 1번과 12번이 만드는 사각형 구역 합이 들어가 있다. 우리는 원래 배열 A의 1, 5, 9의 합, 1, 2, 3, 4의 합을 빼줘야 6번과 12번이 만드는 사각형 구역 값을 구할 수 있다.

다시 합 배열로 돌아오면 1, 5, 9합은 삼각형 즉 합 배열 9번이, 1, 2, 3, 4합은 사각형 즉 합 배열 4번이 값을 가지고 있다. 옆에 있는 기호 수식과 마찬가지로 12번이 별이라면 별에서 두 부분을 빼고 중복해서 뺀 동그라미를 더해주면 구간 합을 구할 수 있다.

이 수식이 맞는지 여러 구역을 직접 정해서 구해봤는데, N+1 배열을 만들고 안에 0을 넣었기 때문에 인덱스가 넘어가도 원하는 구간 합을 구할 수 있다. 

 

 

3️⃣ 슈도 코드

  1. 각종 변수 및 리스트 초기화
  2. A 배열 구하기
  3. S 배열 구하기 => for 문 범위는 (1, N+1) 0 인덱스는 사용하지 않는다. 
  4. 구간 합 구하기

 

4️⃣ 실제 코드 작성

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [[0] * (N+1)]
S = [[0] * (N+1) for _ in range(N+1)]

for _ in range(N):
    temp = [0] + list(map(int, input().split()))
    A.append(temp)

for i in range(1, N+1):
    for j in range(1, N+1):
        S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]
        
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    sum = S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]
    print(sum)

 

주목할 것은 A 배열과 S 배열을 초기화하고 값을 넣는 방법이다. A 배열은 우선 2차원 배열이지만 1차원 배열을 원소로 갖는 배열이기 때문에 append를 통해 원소를 넣어줘 2차원 배열을 만든다. 앞에 [0]을 처리한 것은 0 인덱스를 사용하지 않아서이다.

2차원 리스트에서 합 배열과 구간 합을 구하는 공식을 통해 원하는 값을 구한다.

 

🔑  배운 점

  • 2차원 리스트의 합 배열, 구간 합 구하기

 

나머지 합 구하기 (10986)

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제 입력 1 

5 3
1 2 3 1 2

예제 출력 1 

7

 

 

1️⃣ 분석

 

M으로 나눠 떨어지는 구간 합의 갯수를 구하는 문제이다. 구간 합을 위해 합 배열을 만들 생각을 했다.

우선 M으로 나눠 떨어지는 구간을 구하는 방법을 생각했다. 합 배열의 원소의 나머지를 구해, 나머지 같은 두 원소끼리 구간 합을 구하면 어차피 차를 하니까 나머지가 0이 돼 M으로 나눠 떨어지겠다는 생각을 했다.

나머지 배열을 만드는 것은 합 배열을 구한 다음 각 원소에 대해 M으로 나눈 나머지로 배열을 만들면 되니 어렵지 않았다.

문제는 같은 나머지를 가지는 원소의 수를 구하는 것과 구간의 수를 구하는 것에서 애를 먹었다.

 

2️⃣ 손으로 풀어보기

 

  • 같은 나머지를 가지는 원소의 갯수 => 배열의 인덱스를 활용한 수 세기
  • 같은 나머지를 가지는 구간 합 갯수 => 무작위의 점들 중 순서 상관 없이 점 뽑는거니 조합

배열의 인덱스를 활용해 같은 나머지를 가지는 합 배열 원소 수를 구할 수 있고, 조합을 통해 구간의 수를 구할 수 있다. 이 두개는 배워 가자.

 

3️⃣ 슈도 코드

 

중간에 슈도 코드를 구하다가 굳이 합 배열을 만들 필요가 있을까 생각을 했다. 바로 나머지를 구해 나머지 배열을 만들면 더 짧은 코드로 구할 수 있을 것 같았다.

그런데 그렇게 코드를 작성하면 나중에 채점 받을 때 코드를 이해못해 감점 당할 것 같아서 내가 짠 코드란 정석 코드 둘 다 쳐보도록 했다.

 

4️⃣ 실제 코드 작성

 

이 사진에는 오류가 조금 있다. 직접 치다가 로직을 바꾼 것도 있어서 다 가져와 풀어보자.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = [0] * M
temp = 0
sum = 0

for i in A:
    temp = temp + i
    C[(temp % M)] += 1

for n in C:
    temp = n * (n-1) // 2
    sum += temp

sum += C[0]
print(sum)

 중간에 합 배열을 없앤 코드다. 이 코드를 치다가 두 부분을 놓쳐 오답을 받았는데 살펴보면,

# 배열 초기화
C = [0 * M] 	// [0]
C = [0] * M 	// [0, 0, 0]

# 나눗셈
'/'		// float
'//' 	// int
'%' 	// 나머지

배열 초기화와 나머지에 대해 잊지 말자.

 

정석 코드는 다음과 같다. A 배열과 합 배열 모두 구하고 인덱스로 카운트하는 C 배열 모두 만든 것이다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * N
S[0] = A[0]
C = [0] * M
temp = 0
sum = 0

# 합 배열
for i in range(1, N):
    S[i] = S[i-1] + A[i]

# 인덱스 카운트
for s in S:
    temp = s % M
    C[temp] += 1

# 구간 수 구하기
for c in C:
    temp = c * (c-1) // 2
    sum += temp

# 나머지 0 추가 더하기
sum += C[0]
print(sum)

 

🔑  배운 점

  • 나머지 합 배열 만들기, 구간 합 구하기(나머지가 같은 합 배열 원소)
  • 배열 인덱스를 활용한 갯수 세기, 조합을 이용한 수 세기
  • 배열 초기화 꼭 하기

'Algorithm' 카테고리의 다른 글

[Do it 알고리즘 코딩테스트] 3-4. 슬라이딩 윈도우  (0) 2025.08.13
[Do it 알고리즘 코딩 테스트] 3-3. 투포인터  (0) 2025.08.09
[Do it 알고리즘 코딩 테스트] 3-1. 배열과 리스트  (0) 2025.08.06
[Do it 알고리즘 코딩 테스트] 2. 디버깅  (0) 2025.08.05
[Do it 알고리즘 코딩 테스트] 1. 시간 복잡도  (0) 2025.08.05

티스토리툴바