완전 탐색과 이분탐색 비교

java18111 BF 문제를 풀었다

https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

이 문제는 어려워 보이지만 브루트포스로 풀경우 특이사항을 무시하고

0~256층 까지 무조건 연산해서 최적의 답을 출력하면 쉽게 통과 할 수 있었다

조금 연산 시간을 줄여보자면 2차원 배열 값의 최소,최대 수 범위를 넘어선 값이 답으로 나올수 없기때문에

층의범위 0~256 를 2차원 배열의 min~max 범위롤 줄여주면 조금 범위를 출일수 있다

 

당연히 0~256 까지인 최악의 케이스가 있을것이기 때문에 범위를 줄이는것은 시간초과(탈락)를 뒤집을수 있는 효율적인 요소는 아니다

결국 브루트포스 자체를 변경해야 의미있는 시간차를 만들수 있다

 

그래서 이분탐색을 적용시킬수 있다고 가정한 후

결과가 같은 반례를 시험해서 얼마나 과정을 단축 할 수 있는지 테스트 해보기로 했다

 

당연히 이 문제는 이진탐색으로 풀수없다

1층(높이)씩 줄거나 늘어날때 2차원 배열의 블럭수가 일정하지 않아 각 층마다 작업량이 불규칙 적이다 

이분탐색을 구현하고 BF와 이진 모두 수행 가능한 테스트케이스를 적용하여 시간을 측정 하기로 했다

 

BF를 구현했던 코드를 복사해서 반복문만 수정해 바이너리서치를 완성 했다
그래서 입,출력과 2차원 배열 초기화 코드 부분이 같다

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int[][] ground = new int[N][M];
        int min = 256;
        int max = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                ground[i][j] = Integer.parseInt(st.nextToken());
                min = Math.min(min, ground[i][j]);
                max = Math.max(max, ground[i][j]);
            }
        }
        long startTime = System.currentTimeMillis();

        int ansSec = Integer.MAX_VALUE;
        int ansFloor = Integer.MIN_VALUE;
        
        // 구현부
        
        }
        System.out.println(ansSec+" "+ansFloor);
        long endTime = System.currentTimeMillis();
        long elapsedTime = endTime - startTime;
        System.out.println(" XXX 실행 시간: " + elapsedTime + "ms");

 

 

 

 

BF

long startTime = System.currentTimeMillis();

int ansSec = Integer.MAX_VALUE;
int ansFloor = Integer.MIN_VALUE;
for (int i = min; i <= max; i++) {
    //i층당 시간,층 을 구한다
    int sec = 0;
    int inven = B;
    for (int j = 0; j < ground.length; j++) {
        for (int k = 0; k < ground[j].length; k++) {
            Thread.sleep(10);
            int state = ground[j][k]-i;
            if (state < 0){
                sec += Math.abs(state);
                inven -= Math.abs(state);
            } else if (state > 0) {
                sec += Math.abs(state)*2;
                inven += Math.abs(state);
            }
        }
    }
    //보유 블럭으로 해결 가능 할때 각 층당 최적의 시간,층을 갱신 한다
    if (inven >=0){
        if (sec <= ansSec){
            ansSec = sec;
            ansFloor = i;
        }
    }
}
System.out.println(ansSec+" "+ansFloor);
long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;
System.out.println("브루트 포스 실행 시간: " + elapsedTime + "ms");

 

 

binarySearch

while (min <= max) {
    int midHeight = (min + max) / 2;
    int sec = 0;
    int inven = B;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            Thread.sleep(10);
            int temp = ground[i][j] - midHeight;
            if (temp > 0) {
                sec += temp * 2;
                inven += temp;
            } else {
                sec += Math.abs(temp);
                inven -= Math.abs(temp);
            }
        }
    }

    if (inven >= 0) {
        if (sec <= ansSec) {
            ansSec = sec;
            ansFloor = midHeight;
        }
        max = midHeight - 1;
    } else {
        min = midHeight + 1;
    }
}

System.out.println(ansSec + " " + ansFloor);
long endTime = System.currentTimeMillis();
long elapsedTime = endTime - startTime;
System.out.println("바이너리서치 실행 시간: " + elapsedTime + "ms");

 

 

연산 횟수가 큰(층 값이 높을수록) 두 코드의 처리속도 차이가 많이 날것이기때문에

반례목록중 큰 값을 선택 하려 했으나 그런 케이스들은 두 알고리즘의 답이 달랐다

이분탐색이 처리할수 없는것이다

그래서 같은 결과가 나오는 해당 테스트케이스를 사용 했다

4 4 36
15 43 61 21
19 33 31 55
48 63 1 30
31 28 3 8
//355 32

해당 케이스는 1~3ms 의 시간차를 가지고 있었는데

컴퓨터의 연산 오차범위와 비슷해서

32층이라는 값으로는 의미있는 값을 도출하지 못한다

 

그래서

부르트포스의 각 층에서 2차원 배열을 연산할때,

이분탐색에서 범위를 반으로 줄이면서 2차원 배열을 연산 할때

Thread.sleep(10);

10 밀리초를 딜레이 주었다

완전 탐색

이분  탐색

브루트포스 12288ms중 의미있는 값은 12초

바이너리 서치 1210ms중 의미있는 값은1초 로

역시 바이너리가 빨랐다

 

이문제는 이분탐색이 안되는 문제다

각 층마다 일정한 패턴을 가지고 값이 변하는 문제라면 당연히 바이너리로 풀것이다

테스트케이스가

1 2 3 4

5 6 7 8

처럼 각층마다 1 씩 차이가 난다거나 하는 패턴이 있다면 다양한 방법으로 풀수도 있다

바이너리가 빠르다. 라는 결과는 의미가 없고

얼마나 속도개선을 할수 있을까? 에 대한 대답은 테스트케이스의 조건에따라 다르기때문에

의미를 둘수 있는것이라고는 '해당 알고리즘 유형의 시간복잡도는 무엇이다' 정도다

 

요약 하면

해당하지않는 유형의 풀이라도 적용가능한 케이스로 성능을 비교 할수 있을까?

에 대한 결론은

할수는 있지만 의미가 없다,하지만 다양한 유형으로 풀수 있는 문제라면 성능 비교를 해도 좋을것이다

 

그냥 새벽 감성에 해보고싶어서 해봤다