제비 뽑기-알고리즘 해결.

알고리즘-이진탐색

제비 뽑기

어느 날 친구가 봉지를 들고 와 당신에게 게임을 제안했습니다. 봉지에는 숫자가 쓰여 있는 n장의 종이가 들어 있습니다. 당신은 봉지에서 종이를 한 장 뽑고, 숫자를 확인한 후 다시 봉지에 넣는 동작을 4번 반복하여, 그 숫자의 합이 m이면 당신의 승리, 그렇지 않으면 친구가 승리하게 됩니다. 당신은 이 게임을 몇 번이나 해 보았지만 한번도 이기지 못했습니다. 화가 난 당신은 봉지를 찢어 보든 종이를 꺼낸 후 정말 이길 수 없었는지를 조사했습니다. 종이에 쓰여 있는 숫자가 k1, k2, … , kn 일 경우 합이 m 이 되는 경우가 있는 지를 조사하고, 방법이 있다면 Yes, 없다면 No 를 출력하는 프로그래밍을 장성하세요.

요약

n개의 숫자가 적힌 종이가 주머니에 들어 있고, 손을 넣어서 임의의 종이를 꺼내서 숫자를 확인한 뒤 다시 넣고 또 거내는 것을 4번 반복하여 나온 숫자들의 합이 m인지를 확인 하는 것.

입력 예)

n = 3 : 종이의 개수

m = 10 : 꺼낸 종이에 씌여진 숫자의 합

k = {1, 3, 5} : 종이에 씌여진 숫자

출력 :

Yes ( 예를 들어 1, 1, 3, 5 가 나오면 합이 10이 됩니다.)

class Pick {

    public void solve() {
        int[] k = {1, 3, 5};
        int n = k.length;
        int m = 10;


//        합이 m 이 되는 것을 찾으면 true로 변경한다.
        boolean found = false;

//        4번을 뽑는데, 뽑은 종이를 다시 넣으므로 같은 종이를 다시 뽑을 수 있다.
//        그래서 모든 뽑는 방법을 조사한다.
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                for (int c = 0; c < n; c++) {
                    for (int d = 0; d < n; d++) {
                        if (k[a] + k[b] + k[c] + k[d] == m) {
                            found = true;
                            break;
                        }
                    }
                }
            }
        }

        if (found)
            System.out.println("Yes");
        else
            System.out.println("No");

    }
}

문제가 해결되었다.

그런데 문제가 있다.

문제가 해결되었다면서 문제가 있다니?? 무슨 말인지…

n의 갯수가 커지면 for문을 어마어마하게 돌아야 한다. 이를 빅오 표기법으로 하면 O(n^4) 이다. (빅오 표기법은 간략히 설명하면 최악의 경우 얼마나 걸리는지를 수식으로 나타난 것이다.) 현재는 n이 3이기 때문에 81번만 for문을 돌지만 만약 10이라면 10000번 100 이라면 1억번, 1000이라면 10^12 번 돌아야 한다.

이렇게 되면 속도가 굉장히 오래 걸리게 된다.

이 것을 개선하기 위해서

이진탐색(binary search)

를 이용하겠다.

m = k[a]+k[b]+k[c]+k[d] 이니까 

k[d]=m-k[a]-k[b]-k[c] 와 같으므로 이 값을 이진탐색을 통해서 찾는 것이다.

class Pick2 {

    static int[] k = {1, 3, 5};
    static int n = k.length;
    static int m = 10;

    public void solve() {


//        합이 m 이 되는 것을 찾으면 true로 변경한다.
        boolean found = false;

        Arrays.sort(k); // 정렬은 O(n log n)의 시간복잡도를 가진다.

//        1개의 for문이 제거되었다.
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                for (int c = 0; c < n; c++) {
//      제거              for (int d = 0; d < n; d++) {
                    if (binary_search(m - k[a] - k[b] - k[c])) {
                        found = true;
                        break;
                    }
//                    }
                }
            }
        }

        if (found)
            System.out.println("Yes");
        else
            System.out.println("No");

    }

    private boolean binary_search(int x) {
        int startIndex = 0;
        int lastIndex = n;

        while (lastIndex - startIndex >= 1) {
//            이진트리는 배열이 정렬되었다는 가정하에 동작한다.
//            원하는 값이 있고, 배열의 중간에서 제일 먼저 시작하여,
//            찾는 값이 더 큰지 작은지를 비교하여 절반씩 범위를 줄여 나가는 것이다.
            int centerIndex = (startIndex + lastIndex) / 2; // 가운데 인덱스를 찾는다.
            if (k[centerIndex] == x) return true;    // 찾았다면 true
            if (k[centerIndex] < x) startIndex = centerIndex + 1; // 찾는 값 x가 더 크다면 시작인덱스를 조절한다.
            else lastIndex = centerIndex;                       // 찾는 값 x가 더 작다면 끝 인덱스를 조절한다.
        }
        // 계속 돌았지만 못 찾았다면 값이 없는 것이다.
        return false;
    }
}

이렇게 하면 O(n^3 log n) - (정렬하는데 시간이 추가되었다.) 이 된다.

이를 더 개선해 보자.

2중 for문을 2번 사용하면 O(n^2 log n)이 된다.

class Pick3 {

    int[] k = {1, 3, 5};
    int n = k.length;
    int m = 10;
    int[] preCalc = new int[n * n];

    public void solve() {


//        합이 m 이 되는 것을 찾으면 true로 변경한다.
        boolean found = false;


//        O(n^2)
        for (int c = 0; c < n; c++) {
            for (int d = 0; d < n; d++) {
                preCalc[c * n + d] = k[c] * k[d];
            }
        }

        Arrays.sort(preCalc); // 정렬은 O(n log n)의 시간복잡도를 가진다.

//        2개의 for문이 제거되었다.
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
//      제거          for (int c = 0; c < n; c++) {
//      제거              for (int d = 0; d < n; d++) {
                if (binary_search(m - k[a] - k[b])) {
                    found = true;
                    break;
                }
//                    }
//                }
            }
        }

        if (found)
            System.out.println("Yes");
        else
            System.out.println("No");

    }

    private boolean binary_search(int x) {
        int startIndex = 0;
        int lastIndex = n;

        while (lastIndex - startIndex >= 1) {
//            이진트리는 배열이 정렬되었다는 가정하에 동작한다.
//            원하는 값이 있고, 배열의 중간에서 제일 먼저 시작하여,
//            찾는 값이 더 큰지 작은지를 비교하여 절반씩 범위를 줄여 나가는 것이다.
            int centerIndex = (startIndex + lastIndex) / 2; // 가운데 인덱스를 찾는다.
            if (preCalc[centerIndex] == x) return true;    // 찾았다면 true
            if (preCalc[centerIndex] < x) startIndex = centerIndex + 1; // 찾는 값 x가 더 크다면 시작인덱스를 조절한다.
            else lastIndex = centerIndex;                       // 찾는 값 x가 더 작다면 끝 인덱스를 조절한다.
        }
        // 계속 돌았지만 못 찾았다면 값이 없는 것이다.
        return false;
    }
}

만약 n이 1000 이어도 10^6 번만 돌면 된다.

알고리즘 공부의 필요성은 효율적으로 컴퓨터를 사용하기 위함이다.

동일한 n 값이 있을 때 이를 개선하면 더욱더 좋은 성능을 낼 수 있다. (참고로 컴퓨터의 성능은 2가지 기준이 있는데, 응답속도와 처리량이다.)

예제 출처) 프로그래밍 콘테스트 챌린징(http://www.roadbook.co.kr/49)