(1)자료구조 ② 구간합

1. 구간 합 구하기1

 

 

 

• 문제

Q. 수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램을 작성하시오.
[입력]	[출력]
1번째 줄에 숫자의 개수 N (1≤N ≤100,000) 합을 구해야 하는 횟수 (1≤M ≤100,000)	총 M개의 줄에 입력으로 주어진 i번째 수에서 j번째 수까지의 합을 출력한다.
2번째 줄에 N개 수가 주어진다. (각 수는 1,000보다 작거나 같은 자연수다.)
3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와 j가 주어진다.

 

 

• 풀이방법

1. N개의 수를 입력받은 동시에 합배열 생성     * 합배열 >>>> S[i] = S[i-1] + A[i] 2. i~j 가 주어지면 구간합을 구하는 공식으로 정답 출력     * 구간합 >>> S[j] - S[i-1]

 

 

• 코드 순서

1. suNo(숫자 개수), quizNo(질의 개수) 2. numbers 변수에 숫자 데이터 저장 3. prefix_sum 합배열 변수 선언 4. temp 변수 선언 5. for 저장한 숫자 데이터 차례대로 탐색:     temp에 현재 숫자 데이터 더해 주기     합 배열에 temp값 저장 6. for 질의 개수만큼 반복:     질의 범위 받기 (s ~ e )     구간 합 출력하기 (prefix_sum[e] - prefix_sum[s-1])

 

 

• 정답

suNo,quizNo = map(int, input().split())               numbers = list(map(int, input().split()))               prifix_sum = [0]               temp = 0               for i in numbers:                   temp = temp + i                   prifix_sum.append(temp)                for i in range(quizNo):                   s, e = map(int, input().split())                   print(prifix_sum[e]-prifix_sum[s-1])
[입력]	[출력]
5 3 5 4 3 2 1 1 3 2 4 5 5	12 9 1

 

• 다른 답

n, m = map(int, input().split())       array = list(map(int, input().split()))       newarray = []       sum = 0       for i in array:                      # 합배열 구하기           sum += i           newarray.append(sum)       for i in range(m):           x, y = map(int, input().split())           if x == 1:               print(newarray[y - 1])                          # x가 1이면 기본 배열에서 배열의 0번째 인덱스부터 더해주는 것.             즉, 합배열에서는 제외하고 마지막부분만 보면 된다.           else:             print(newarray[y - 1] - newarray[x - 2])

 

 

2. 구간합 구하기2

 

 

 

• 문제

 

Q. N x N개의 수가 N x N 크기의 표에 채워져 있다. 표 안의 수 중 (X₁,Y₁)에서 (X₂,Y₂)까지의 합을 구하려 한다.          X는 행, Y는 열을 의미한다. 예를 들어 N = 4이고, 표가 다음과 같이 채워져 있을 때를 살펴보자.          (2,2)에서 (3,4)까지의 합을 구하면 3+4+5+4+5+6=27 이고, (4,4)에서 (4,4)까지의 합을 구하면 7이다.          표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때 이를 처리하는 프로그램을 작성하시오.
[입력]	[출력]
1번째 줄에 표의 크기 N (1 ≤ N ≤ 1024) 합을 구해야 하는 횟수 M ( 1 ≤  M ≤ 100,000)	총 M 줄에 걸쳐 (X₁, Y₁) 에서 (X₂, Y ₂)의 합을 구해 출력
2번째 줄부터 N개의 줄에는 표에 채워야 하는 수가 1행부터 차례대로 주어집니다.
다음 M 개의 줄에는 4개의 정수 X₁, Y₁, X₂, Y ₂ 가 주어집니다.
@ 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수 ( X₁ ≤   X₂ , Y₁ ≤ Y ₂)

 

• 풀이방법

1. 2차원 구간 합 배역의 1행, 1열부터 구합니다. 구간 합 배열 1행, 1열은 다음과 같이 구합니다. - 행 구하기: D [ 1 ] [ j ] = D [ 1 ] [ j - 1 ] + A [ 1 ] [ j ] - 열 구하기: D [ i ] [ 1 ] = D [ i - 1 ] [ 1 ] + A [ i ] [ 1 ] 2. 합배열 채우기 D [ i ] [ j ] = D [ i ] [ j - 1 ] + D [ i -1 ] [ j ] - D [ i - 1 ] [ j - 1 ] + A [ i ] [ j ] 3. X₁, Y₁, X₂, Y ₂ 에 대한 답 구하기 D [ X₂ ] [ Y ₂ ] -  D [ X₁ - 1 ] [ Y ₂] - D [ X₂ ] [ Y ₁ - 1 ] + D [  X₁ - 1 ] [ Y ₁ - 1 ]

 

 

• 코드 순서

1. n (리스트 크기), m (질의 수), A (원본 리스트), D (합 배열) 정의 2. for n 만큼 반복:     원본 리스트 데이터 저장 3. for i를 1부터 n까지 반복:        for j를 1부터 n까지 반복:            합배열 저장             D [ i ] [ j ] = D [ i ] [ j - 1 ] + D [ i -1 ] [ j ] - D [ i - 1 ] [ j - 1 ] + A [ i ] [ j ] 4. for m만큼 반복:        질의에 대한 결과 계산 및 출력        결과 = D [ X₂ ] [ Y ₂ ] -  D [ X₁ - 1 ] [ Y ₂] - D [ X₂ ] [ Y ₁ - 1 ] + D [  X₁ - 1 ] [ Y ₁ - 1 ]

 

• 정답

n, m = map(int, input().split())        A = [[0] * (n+1)]        D = [[0] * (n+1) for _ in range(n+1)]        for i in range(n):            A_row = [0] + [int(x) for x in input().split()]            A.append(A_row)        for i in range(1,n+1):            for j in range(1,n+1):                #구간 합 구하기                D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j]        for _ in range(m):            x1, y1, x2, y2 = map(int, input().split())              result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1 -1]            print(result)
[입력]	[출력]
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 4 1 4	27 6 64
2 4 1 2 3 4 1 1 1 1 1 2 1 2 2 1 2 1 2 2 2 2	1 2 3 4

 

 

 

3. 나머지 합 구하기

 

• 문제

Q. N개의 수 A₁, A₂,...An 이 주어졌을 때 연속된 부분의 합이           M으로 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.           즉, Ai, A₂,...Aj(i≤j)의 합이 M으로 나누어떨어지는 (i,j) 쌍의 개수를 구하시오.
[입력]	[출력]
1번째 줄에 N과 M  ( 1 ≤ N  ≤ 10⁶ ) ( 2 ≤ M  ≤ 10³ )	1번째 줄에 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 출력
2번째 줄에 N개의 수 A₁, A₂,...An 이 주어진다.  (0 ≤ Ai  ≤ 10⁹)

 

•  풀이방법

1. 리스트 A와 합 배열 S 를 생성한다. 2. 합배열 S 의 모든 값을 M으로 나눈 나머지 연산을 수행해 값을 업데이트하기 3. 나머지가 같은 개수끼리 경우의 수 따져 결과값에 추가하기           ₃C₂ => 3           ₂C₂ => 1 4. 모든 경우의 수 세기            3 + 3  + 1 = 7

 

 

• 코드 순서

1. n (수열의 개수), m(나누어 떨어져야하는 수), A (원본수열) , S(합 배열), C(인덱스 카운트 리스트), answer 선언하기 2. for i -> 1 ~ n-1:         S[i] = S[i-1] + A[i] 3. for i -> 0 ~ n-1:          remainder = S[i] % M          if ( remainder == 0 ) 정답 +1          C[remainder]의 값을 1 증가 4. for i -> 0 ~ m-1:          C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기 5. 결과값 출력

 

• 정답

n, m = map(int, input().split())       A = list(map(int, input().split()))       S = [0]*n       C = [0]*m       S[0] = A[0]       answer = 0       for i in range(1, n):            S[i] = S[i-1] + A[i]         for i in range(n):           remainder = int(S[i] % m)            if remainder == 0:                answer += 1           C[remainder] += 1          for i in range(m):           if C[i] > 1:             answer += (C[i] * (C[i] - 1) / 2)       print(int(answer))
[입력]	[출력]
5 3 1 2 3 1 2	7

 

• 다른 답

n,m = map(int, input().split())          a = list(map(int, input().split()))          count= [0]*m          count[0] = 1          result =0          sum_mod_m =0          for num in a:              sum_mod_m = (sum_mod_m +num) % m              result += count[sum_mod_m]              count[sum_mod_m]+=1          print(result)