모든 문제를 푸는 데에 있어서 가장 쉽고 간단한 방법을 짚고 넘어가겠다. 원래는 다른 탐색 알고리즘을 정리하기 전에 먼저 한 번 짚고 넘어가야 했지만,,, 은연중에 쉽다는 생각에 미뤄두었었다. 하지만 최근에 완전탐색 문제를 풀다가 제대로 깨진적이 있어서 정리하고 넘어가려고 한다.
단순하게 생각하면, 가능한 경우의 수를 일일이 모두 다 탐색해보는 것이다. 정확도는 100%에 달하는 유용한 방법이지만 세상에 좋은 기능만 있는것이 어디 있겠는가... 정확도가 증가하는 것에 비례하게 시간이 증가한다.
그렇기 때문에 정확도를 높게 유지한 상태로 코드를 문제에 맞게 조건을 걸어서 최적화를 해주어야 한다. 한 가지 간단한 예시를 들어보겠다. 사실 브루트 포스가 어려운 이유는 바로 후자, 조건에 맞게 코드를 최적화하면서 시간을 줄이는 일이지 않을까 싶다.
간단한 예시로 n개의 수 중에서 서로 다른 2개의 수를 더해서 나올 수 있는 합 중에서 가장 큰 것을 구하는 코드를 구현해보겠다. 비교분석을 위해서 최댓값을 구하는 것은 물론이고, 비교 연산 횟수와 실행시간을 측정했다.
[ 완전탐색_최적화x ]
|
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
|
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class refactoringtest {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
//최댓값을 누적해줄 변수
int max = 0;
//비교횟수, 여기서는 탐색횟수라고 하자
int cnt = 0;
//실행 시간을 측정해줄 변수
long start = System.currentTimeMillis();
for(int i=1; i<=n; i++) {
for(int k=1; k<=n; k++) {
if(i!=k) {
cnt++;
max = max < (i+k) ? (i+k) : max;
}
}
}
long end = System.currentTimeMillis();
System.out.println(max);
System.out.println(cnt);
System.out.println((end-start)/1000.0);
}
}
|
cs |
단순하게 2중 for문을 돌리는데, 두 숫자가 같지 않은 경우에만 합을 구하고 최댓값보다 더 큰지 비교를 하여 최댓값을 갱신해 나가는 방식으로 진행했다. 숫자의 범위가 1000정도면, 요즘은 워낙 컴퓨터의 속도가 빠르기 때문에 최적화를 하던 안하던 큰 차이가 나지 않을 것이다. 하지만 수의 범위가 백만, 천만을 벗어나면, 위의 코드와 같은 방식은 O(N^2)의 시간복잡도를 가지므로 상당히 오랜 시간이 걸릴 것이다. 위의 코드를 실행하면 아래와 같은 결과가 나온다. 비교를 위해 더 큰 값을 넣어보고 싶었지만,,, 필자의 노트북이 너무 오래되었다보니 십만이상의 값은 오래걸려서 결과조차 나오지 않는다,,,
[ 완전탐색_최적화 ]
이 문제를 최적화 하는 방법은 간단하다.위의 예시에서는 필자가 입력값의 크기에 따른 실행 속도의 차이를 보여주기 위함이었지만, 실제로는 값의 개수만이 아닌 n개의 값을 직접 입력받는다고 가정하자.(테스트코드로 10000개의 데이터를 넣을 수가 없다...). 실제로는 최적화를 하지 않은 방법은 N^2의 탐색을 진행하고, 최적화를 하면 1번의 탐색을 진행하는 것이 핵심이다.
이 경우 단순히 정렬을 하고 가장 큰 값 2개를 더하면 결과가 된다. 이번에는 비교를 위해 배열에 값을 1부터 넣어주고 시작하겠다.
|
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
|
package Main;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class refactoringtest {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int N[] = new int[n];
//최댓값
int max = 0;
//배열에 1부터 n까지의 값을 저장한다.
for(int i=1; i<=n; i++) {
N[i-1] = i;
}
//실행 시간을 측정해줄 변수
long start = System.currentTimeMillis();
//오름차순 정렬 -> O(NlogN)
Arrays.sort(N);
System.out.printf("최댓값 : %d\n", N[N.length-1] + N[N.length-2]);
long end = System.currentTimeMillis();
System.out.println("실행시간: " + (end-start)/1000.0);
}
}
|
cs |
위 코드를 실행하면 결과는 아래와 같이 나온다.. 압도적으로 다른 것이 눈에 들어오는가? 저 시간 또한 정렬을 하는데 소요된 시간이지 최적화를 하지 않은 방법과는 다르게 최댓값보다 큰 값인지 비교조차 하지 않는다.
코드를 최적화하지 않은 경우에는 10000개의 수가 최대였는데,, 1억개의 수까지도 가능하다.
오늘은 아주 단순하게 완전탐색의 맛(?)만 보았다. 위에서도 필자가 잠시 언급한 내용처럼 브루트 포스는 모든 경우의 수를 다 탐색을 하게 되면, 시간초과가 반갑게 인사할 것이다. 여러가지 유형의 문제를 풀어보고 스킬을 익혀야 한다.
일단 모든 경우의 수를 탐색한다는 생각으로 접근을 하다가, 이 방법은 어차피 안 될것 같은데? 라는 유망성을 체크해보고 미리 탐색을 하지 않는 방식의 최적화를 진행해야 한다. 이에 대한 연습은 유망성을 체크하는 그리디 알고리즘을 연습해보면 도움이 될 것이다.
