1. 구간 합
: 합 배열을 이용해 시간 복잡도를 더 줄이기 위한 알고리즘
(1) 구현 과정
- 먼저 합 배열을 구한다 -> 미리 구해둘 경우, 일정 범위의 합을 구하는 시간 복잡도가 감소 [O(1)]
- 합배열 공식 : sum[i] = sum[i-1] + arr[i]
- 구간합 공식 : sum[j]-sum[i-1] //i에서 j까지의 구간 합
# arr[2] ~ arr[5] 구간 합을 합 배열로 구하는 과정
sum[5] = arr[0] + arr[1] + arr[2]+ arr[3]+ arr[4]+ arr[5]
sum[1] = arr[0] + arr[1]
sum[5] - sum[1] = arr[2] + arr[3] + arr[4] + arr[5]
//sum[5]-sum[1]은 arr[2] ~ arr[5]까지의 구간 합
문제 3. 구간 합 구하기
수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램을 작성하시오.
입력
1번째 줄에 수의 개수 N(1 <= N <= 100,000), 합을 구해야 하는 횟수 M(1 <= M <= 100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야하는 구간 i와 j가주어진다.
출력
총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.
예제 입력
5 3 //데이터의 개수, 질의 개수
5 4 3 2 1 //구간 합을 구할 대상 배열
1 3
2 4
5 5예제 출력
12
9
11단계. 문제 분석하기
-> 수 개수와 합을 구해야 하는 횟수가 최대 100,000 -> 구간마다 합을 계산할 경우 시간 초과
-> 구간합을 사용
2단계. 손으로 풀어보기
- N개의 수를 입력받아 합 배열 생성
합 배열 공식
: sum[i] = sum[i-1] + arr[i] - 구간 i~j가 주어지면 구간 합을 구해 출력
구간 합 공식
: sum[j] - sum[i-1]
3단계. 슈도코드 작성하기
suNo(숫자 개수), quizNo(질의 개수) 저장하기
for(숫자 개수만큼 반복하기) {
합 배열 생성하기(S[i] = S[i - 1] + A[i])
}
for(질의 개수만큼 반복하기) {
질의 범위 받기다 〜 j)
구간 합 출력하기(S[j] - S[i - 1])
}
package datastructure.ch03;
import java.util.Scanner;
public class ds_q03 {
static Scanner kb = new Scanner(System.in);
public void solution(int n, int m, int[] arr) {
int[] sum = new int[n + 1];
sum[0] = arr[0];
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + arr[i];
int[] answer = new int[m];
for (int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
answer[i] = sum[b] - sum[a - 1];
}
for (int x : answer)
System.out.println(x);
}
public static void main(String[] args) {
ds_q03 T = new ds_q03();
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = kb.nextInt();
T.solution(n, m, arr);
}
}
+) 세련된 코드
문제 4. 구간 합 구하기2
NxN개의 수가 NxN 크기의 표에 채워져 있다. 표 안의 수 중 (Xi, Yi)에서 (X2, Y2)까지의 합을 구하려 한다. X는 행，Y는 열을 의미한다. 예를 들어 N = 4이고，표가 다음과 같이 채워져 있을 때를 살펴보자. (2, 2)에서 (3, 4)
까지의 합을 구하면 3 + 4 + 5 + 4 + 5 + 6 = 27이고，(4,4)에서 (4,4)까지의 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을때 이를 처리하는 프로그램을 작성하시오.
입력
1 번째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다(1 <= N <= 1024,1 <= M <= 100,000). 2번째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1 행부터 차례대로 주어진다. 다음 M개의 줄에는 4개
의 정수 Xi, Yi, X2, Y2가 주어지며，(Xi, YJ에서 (X2, Y2)의 합을 구해 출력해야 한다. 표에 채워져 있는
수는 1,000보다 작거나 같은 자연수다(Xi <= X2, Yi <= Y2).
출력
총 M줄에 걸쳐 (Xi, Yi)에서 (X2, Y2)까지 합을 구해 출력한다.
예제 입력 1
4 3 // 2차원 배열의 크기，구간 합 질의의 개수
1 2 3 4 // 원본 배열 1번째 줄
2 3 4 5 // 원본 배열 2번째 줄
3 4 5 6 // 원본 배열 3번째 줄
4 5 6 7 // 원본 배열 4번째 줄
2 2 3 4 // 구간합(X1，Y1)，(X2, Y2) 1번째 질의
3 4 3 4 // 구간합(X1，Y1)，(X2, Y2) 2번째 질의
1 1 4 4 // 구간합(X1，Y1)，(X2, Y2) 3번째 질의
예제 출력 1
27
6
64
예제 입력 2
2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
예제 출력 2
27
6
641단계. 문제 분석하기
: 질의 개수가 100,000이므로, 구간 합 배열을 이용해야 시간 제한에 걸리지 않는다.
# 2차원 구간 합 배열 D[X][Y] 정의
D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합
2단계. 손으로 풀어 보기
- 2차원 구간 합 배열의 1행, 1열부터 구한다
1행 합 : dim[i][1] = dim[i-1][1] + arr[i][1]
1열 합 : dim[1][j] = dim[1][j-1] + arr[1][j] - dim[i][j]인 구간 합 공식
dim[i][j] = dim[i][j-1] + dim[i-1][j] - dim[i-1][j-1] + arr[i][j] - 예를 들어 (2,2에서 3,4)까지의 구간합
dim[3][4] - dim[1][4] -dim[3][1] + dim[1][1] - (X1, Y1)부터 (X2, Y2)까지의 구간 합
dim[x2][y2] - dim[x1-1][y2] - dim[x2][y1-1] + dim[x1-1][y1-1]
3단계. 슈도코드 작성하기
N（배열 크기） 바질의 수） 저장하기
for（N만큼 반복하기） {
for（N만큼 반복하기） {
원본 배열 저장하기
}
}
for（N만큼 반복하기） {
for（N만큼 반복하기） {
합 배열 저장하기
D[i][j] = D[i][j-1] + D[i-l][j] - D[i-l][j-l] + A[i][j];
}
}
for（M만큼 반복하기） {
질의 계산 및 출력하기
결과 = D[x2][y2] - D[xl-l][y2] - D[x2][yl-1] + D[xl-l][yl-l];
}
package datastructure.ch03;
import java.util.Scanner;
public class ds_q04 {
public int solution(int[][] dim, int x1, int y1, int x2, int y2) {
return dim[x2][y2] - dim[x1 - 1][y2] - dim[x2][y1 - 1] + dim[x1 - 1][y1 - 1];
}
public static void main(String[] args) {
ds_q04 T = new ds_q04();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[][] arr = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
arr[i][j] = kb.nextInt();
}
}
int[][] dim = new int[arr.length][arr.length];
for (int i = 1; i <= arr.length - 1; i++) {
for (int j = 1; j <= arr.length - 1; j++) {
dim[i][j] = dim[i][j - 1] + dim[i - 1][j] - dim[i - 1][j - 1] + arr[i][j];
}
}
for (int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
int d = kb.nextInt();
System.out.println(T.solution(dim, a, b, c, d));
}
}
}
문제 05. 나머지 합 구하기
N개의 수 Ai, A2，...，AnO| 주어졌을 때 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉，Ai + ... + Aj(i < j)의 합이 M으로 나누어떨어지는 (i, j) 쌍의 개수를 구하시오.
입력
1 번째 줄에 N과 M(1 <= N <= 106, 2 <= M <= 103), 2번째 줄에 N개의 수 Ai, A2，...，An이 주어진다(0< =Ai <= 109).
출력
1 번째 줄에 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수를 출력한다.
예제 입력 1
5 3 7
예제 출력 1
71단계. 문제 분석하기
: N의 최댓값이 106이므로, 106개의 수에 대한 모든 구간 합을 구해야 한다
-> 구간 합 배열 이용
2단계. 손으로 풀어보기
- arr 배열의 합 배열 생성
- 합 배열의 모든 값을 m으로 나머지 연산 수행
- 합 배열에서 원소 값이 0인 개수를 answer에 더한다 [떨어지는 수]
- 합 배열의 원소 값이 같은 인덱스 개수 [나머지 값이 같은 합 배열의 개수]
-> 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구해 정답에 더한다.
-> 조합
+) 세련된 풀이
package datastructure.ch03;
import java.util.Scanner;
public class ds_q05 {
public int solution(int[] arr, int m) {
int answer = 0;
int[] count = new int[m];
int[] sum = new int[arr.length];
for (int i = 1; i < arr.length; i++) {
sum[i] = sum[i - 1] + arr[i];
if (sum[i] % m == 0) {
sum[i] = 0;
answer++;
count[sum[i]]++;
} else {
sum[i] = sum[i] % m;
count[sum[i]]++;
}
// 경우의 수
}
// 경우의 수 [조합] -> 나머지 값이 같은 합 배열의 개수를 센다.
// 즉, 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구해 나누어 어지는 개수에 더한다.
for (int i = 0; i < m; i++) {
if (count[i] > 1)
answer = answer + (count[i] * (count[i] - 1) / 2);
}
return answer;
}
public static void main(String[] args) {
ds_q05 T = new ds_q05();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++)
arr[i] = kb.nextInt();
System.out.println(T.solution(arr, m));
}
}
#순열과 조합 공식
'Java > Java 알고리즘' 카테고리의 다른 글
| [알고리즘] 2-4. 슬라이딩 윈도우 # [+deque 데크 자료구조] (0) | 2022.06.30 |
|---|---|
| [알고리즘] 02-3. 투 포인터 (0) | 2022.06.30 |
| [알고리즘] 2-1. 배열과 리스트 (0) | 2022.06.28 |
| [알고리즘] 2. 자료구조 (0) | 2022.06.28 |
| [알고리즘] 1-6. 기수 정렬 [구간 합 이용] (+ 우선순위 큐 이용) (0) | 2022.06.28 |