[JAVA] 구간 합 (1차원, 2차원 배열)

합 배열

• 합 배열은 원본 배열을 전처리한 배열
• 합 배열 S 공식 (S=합배열, A=원본배열)
  • S[i] = A[0] + A[1] + A[2] + ... + A[i-1] 

• A[i] ~ A[j] 까지의 합(구간합)을 합 배열 없이 구하는 경우, 시간 복잡도는 O(N)
• 코딩테스트에서 시간 복잡도는 생명🏄‍♀️

 

구간 합

• 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 알고리즘
• 구간 합 공식 (S=합배열)
  • S[j] + S[i-1]  // i ~ j 까지 구간의 합

 

1차원 배열의 구간 합

• 1. 배열의 구간 합을 구하는 작업을 선행한다.
• 2. 구간 합 공식을 대입하여 결과를 도출한다.
• 백준 11659번 예제로 공부해보자.
  • https://jeongsoyeon.tistory.com/157

 

2차원 배열의 구간 합

• 나는 2차원 배열의 경우를 분석하는데에 시간이 조금 걸렸다 🤹‍♀️ 
• 2차원 배열 합을 구하는 작업은 2단계를 걸친다.
  • 1. 원본 배열의 행 구간합을 구한다. 
  • 2. 행 구간합의 열 구간합을 구한다. (행과 열 어떤 것을 우선으로 계산해도 무방)
  • 위 두 단계를 하나의 공식으로 정리할 수 있다.
• 2차원 배열 합 공식 (D=구간합, A=원본배열)
  • D[i][j] = D[i][j-1] + D[i-1] - D[i-1][j-1] + A[i][j] 
  • 이 원리는, 집합 이론의 포함-배제 원리와 유사하다.
    1. D[i-1][j]는 (1,1)부터 (i-1,j)까지의 직사각형 영역 합
    2. D[i][j-1]는 (1,1)부터 (i,j-1)까지의 직사각형 영역 합
    3. 이 두 값을 더하면 (1,1)부터 (i,j)까지의 영역에서 (i-1,j-1) 영역이 중복되어 계산된다.
    4. 따라서 S[i-1][j-1]를 한 번 빼준다.
    5. 마지막으로 A[i][j]를 더해 현재 위치의 값을 포함시킨다.
• 2차원 배열의 구간 합 공식 
  • result = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
  • 마찬가지로 집합 이론의 포함-배제 원리와 유사하다. 
    1. S[x2][y2]는 (1,1)부터 (x2,y2)까지의 전체 직사각형 영역 합.
    2. 우리는 이 중에서 (x1,y1)부터 (x2,y2)까지의 영역만 원한다.
    3. 따라서 불필요한 영역을 제거해야 합니다:
       • S[x1-1][y2]: (1,1)부터 (x1-1,y2)까지의 영역 (위쪽 영역)
       • S[x2][y1-1]: (1,1)부터 (x2,y1-1)까지의 영역 (왼쪽 영역)
    4. 하지만 (1,1)부터 (x1-1,y1-1)까지의 영역이 두 번 빼졌으므로, S[x1-1][y1-1]를 다시 더해준다.

• 2차원 배열의 구간 합 구하는 예제를 공부해보자.
  • https://jeongsoyeon.tistory.com/158