알고리즘 문제를 계속해서 연습해야겠다고 생각한 시점에서 백준 알고리즘 2차원 배열문제를 풀어보기로 했다.
문제는 간단하게 말하면 2차원 배열이 주어졌을 때, 특정 i, j 위치에서 x, y위치 까지의 value들의 합을 구하는 문제이다.
나는 특정 알고리즘을 생각하지 않고 단순하게 접근해서 array에 value를 다 넣어놓고 1,1에서 2, 3 까지 value를 구하라고 하면 1,1에서 2,3까지 반복문을 돌면서 value를 다 더했었다. 하지만 그렇게 하는게 아니라 DP 알고리즘을 사용해야 한다고 한다. 우선 자세한 문제는 백준 홈페이지에서 확인하시면 된다. https://www.acmicpc.net/problem/2167
그리고 먼저 말했던 단순하게 접근한 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public enum InputType {
ROWCNT {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0] <= 300;
}
},
COLCNT {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0]<= 300;
}
},
VALUE {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0] <= 10000;
}
},
CALRANGE {
@Override
public boolean isCheckRange(int... value) {
return value[0] <= value[1];
}
};
public boolean isCheckRange(int... value) {
return false;
}
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int arrayRowCnt = scanner.nextInt();
if (!InputType.ROWCNT.isCheckRange(arrayRowCnt)) {
System.out.println("Row must 1 ~ 100 range.");
scanner.close();
return;
}
int arrayColCnt = scanner.nextInt();
if (!InputType.COLCNT.isCheckRange(arrayRowCnt)) {
System.out.println("Col must 1 ~ 100 range.");
scanner.close();
return;
}
int array[][] = new int[arrayRowCnt][arrayColCnt];
// value 받기
for (int i = 0; i < arrayRowCnt; i++) {
for (int j = 0; j < arrayColCnt; j++) {
int value = scanner.nextInt();
if (!InputType.VALUE.isCheckRange(value)) {
System.out.println("Value must 1 ~ 10000");
scanner.close();
return;
}
array[i][j] = value;
}
}
int count = scanner.nextInt();
int result[] = new int[count];
for (int index = 0; index < count; index++) {
int i = scanner.nextInt() - 1;
int j = scanner.nextInt() - 1;
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
if (!InputType.CALRANGE.isCheckRange(i, x) ||
!InputType.CALRANGE.isCheckRange(j, y)) {
System.out.println("Range Error.");
scanner.close();
return;
}
result[index] = sumData(array, i, j, x, y);
}
scanner.close();
printData(result);
}
/**
* 데이터 출력
*
* @param result
*/
private static void printData(int[] result) {
Arrays.stream(result).forEach(System.out::println);
}
/**
* 데이터 더하기
*
* @param i
* @param j
* @param x
* @param y
*/
private static int sumData(int[][] array, int i, int j, int x, int y) {
int result = 0;
for (int indexX = i; indexX <= x ; indexX++) {
for (int indexY = j; indexY <= y; indexY++) {
result += array[indexX][indexY];
}
}
return result;
}
};
|
cs |
결과는 정상적으로 출력되나 범위가 나올때마다 반복문이 계속 나와야하고 범위가 엄청커지면 실행속도가 엄청 커져버린다.,,,
그래서 DP 알고리즘을 사용해서 시도해 보았다.
DP 알고리즘을 사용한 풀이는 다음과 같다.
먼저 사용자로 부터 입력받은 배열의 크기인 N, M만큼 반복문을돌면서 해당영역의 DP (누적값을 더해놓은 배열)를 구해놓는다. 구하는 공식은 다음과 같다.
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + value;
여기서 i, j는 현재 index이다. 현재 인덱스의 누적값을 구하기 위해서는 바로전의 좌표에 있는 값과 현재 나의 값을 더해주면 된다. 그림으로 보면 다음과 같다.
그림에서 보면 (2, 2)의 값을 구하기 위해서 바로 전인 (1, 2) 까지의 값과 (2, 1) 까지의 값을 구하고 서로 중복되는 (1, 1)의 값을 빼주고 현재 (2, 2)의 값을 더해주면 된다.
그럼 dp 배열에는 각 좌표에 누적 값을 가지고 있다.
그래서 그 값을 이용하여 특정 좌표 사이의 값을 구할 수 있다.
만약 (2, 2)에서 (4, 4)까지의 value를 구한다고 하면 (4, 4)까지의 누적 값에서 (2, 2) 바로 전인 (1, 1)을 기점으로 (1, 4)와 (4, 1)까지의 값을 빼고 두번 빼진 값을 한번 더해준 값을 빼면 된다. 그래서 정리된 식은 다음과 같다.
dp[x][y] - dp[i - 1][y] - dp[x][j - 1] + dp[i - 1][j - 1]
여기서 x와 y는 위에서 (4,4) i,j 는 (2,2)이다.
그렇게 해서 나온 소스코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
package test;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public enum InputType {
ROWCNT {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0] <= 300;
}
},
COLCNT {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0]<= 300;
}
},
VALUE {
@Override
public boolean isCheckRange(int... value) {
return value[0] >= 1 && value[0] <= 10000;
}
},
CALRANGE {
@Override
public boolean isCheckRange(int... value) {
return value[0] <= value[1];
}
};
public boolean isCheckRange(int... value) {
return false;
}
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int arrayRowCnt = scanner.nextInt();
if (!InputType.ROWCNT.isCheckRange(arrayRowCnt)) {
System.out.println("Row must 1 ~ 100 range.");
scanner.close();
return;
}
int arrayColCnt = scanner.nextInt();
if (!InputType.COLCNT.isCheckRange(arrayRowCnt)) {
System.out.println("Col must 1 ~ 100 range.");
scanner.close();
return;
}
int dp[][] = new int[301][301];
// value 받기
for (int i = 1; i <= arrayRowCnt; i++) {
for (int j = 1; j <= arrayColCnt; j++) {
int value = scanner.nextInt();
if (!InputType.VALUE.isCheckRange(value)) {
System.out.println("Value must 1 ~ 10000");
scanner.close();
return;
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + value;
}
}
int count = scanner.nextInt();
for (int index = 0; index < count; index++) {
int i = scanner.nextInt();
int j = scanner.nextInt();
int x = scanner.nextInt();
int y = scanner.nextInt();
if (!InputType.CALRANGE.isCheckRange(i, x) ||
!InputType.CALRANGE.isCheckRange(j, y)) {
System.out.println("Range Error.");
scanner.close();
return;
}
System.out.println(dp[x][y] - dp[i - 1][y] - dp[x][j - 1] + dp[i - 1][j - 1]);
}
scanner.close();
}
};
|
cs |
참 알고리즘이 알면 쉽게 해결할 수 있는건데 모르면 고생을 해야하는 것 같다.
많이 공부하자.
'JAVA > 알고리즘' 카테고리의 다른 글
| 백준 알고리즘 10988번 문제 팰린드롬 문제 풀기 (0) | 2018.07.09 |
|---|---|
| 피보나치 수열 재귀, DP, loop 방법으로 구현하고 차이 확인 (0) | 2018.07.09 |
| 정렬알고리즘 - 버블정렬 (0) | 2018.05.28 |
| 정렬알고리즘 - 삽입정렬 (0) | 2018.05.28 |
| 정렬알고리즘 - 선택정렬 (0) | 2018.05.28 |