[Java] 분할정복, 백트레킹, 이진탐색

1. 분할 정복

 

• Divide and Conquer
  • 해결할 문제를 여러 작은 부분 문제로 나눈다.
  • 나눈 작은 문제를 각각 해결한다.
• 접근법
  • Top-down approach
  • bottom-up approach

 

// Power 함수
import java.util.Scanner;

// x^n을 O(logN) 시간복잡도로 구하는 분할 정복 알고리즘
public class SquareNumberTest {

    static int callCnt1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int n = sc.nextInt(); // 최대 10억

        System.out.println(exp1(x,n));
        System.out.println(callCnt1);
        sc.close();
    }

    private static long exp1(long x, int n) {
        callCnt1++;
        if(n==1) return x;
        int half = n/2;
        long res = exp1(x, half);
        res *= res;

        return n%2==0 ? res : res*x;
    }

}

• Math.pow(2, 10000) → Infinity : Java 유틸리티의 한계. 스스로 Power함수를 구현할 수 있어야 한다.

 

//모듈러 연산
(a + b) % d
= (a%d + b%d) %d

(a + b) % d
= (a%d + b%d) %d

(a * b) % d
= (a%d * b%d) %d

(a + b) % d
= (a%d + b%d) %d

모듈러 연산도 분할 정복 알고리즘에 속한다.

 

2630번: 색종이 만들기

 

---

2. 백트레킹

 

• 퇴각검색
• 상태 공간 트리를 DFS한다.
• 도중에 유망하지 않다면(= 더 이상 해일 가능성이 없어지면) 부모 노드로 되돌아가서 다른 노드부터 다시 탐색한다.
• 일반적으로 경우의 수가 줄어들지만 최악의 경우 여전히 지수함수 시간을 요한다.

 

9663번: N-Queen

 

---

3. 이진 탐색

 

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법. (반띵)
• 이진 검색을 수행하기 위해서는 자료가 정렬되어있어야 한다.

binarySearch(S[].n, key)
    start <- 0
    end <- n -1
    WHILE start <= end
        mid <- (start + end) /2
        IF S[mid] == key
            RETURN mid
        ELIF S[mid] < key // 오른쪽 탐색
            start <- mid +1
        ELIF S[mid] > key // 왼쪽 탐색
            end <- mid -1
    END WHILE
    RETURN -1

import java.util.Arrays;

public class BinarySearchTest {

    static int[] arr;
    public static void main(String[] args) {
        arr = new int[]{2, 4, 7, 9, 11, 19, 23};
        int key = 5;

        // 이진 탐색
        //int ret = binarySearch(arr.length, key);
        //int ret = binarySearch2(key, 0, arr.length - 1);
        int ret = Arrays.binarySearch(arr, key);

        if(ret >= 0)
            System.out.println("index : "+ret+" value : "+arr[ret]);
        else
            System.out.println("index : " + ret+ " fail");
    }

    private static int binarySearch(int length, int key) {
        int start, mid, end;

        start = 0;
        end = length - 1;

        while(start <= end) {
            mid = (start+end)/2;

            if(arr[mid] == key) { // 탐색 성공
                return mid;
            }else if(arr[mid] < key) { // 오른쪽 탐색
                start = mid + 1;
            }else if(arr[mid] > key) { // 왼쪽 탐색
                end = mid - 1;
            }
        }

        return -1; // 탐색 실패
    }
    private static int binarySearch2(int key, int start, int end) {
        if(start > end) {
            return -1;
        }
        int mid = (start+end)/2;

        if(arr[mid] < key) { // 오른쪽 탐색
            start = mid + 1;
            return binarySearch2(key, start, end);
        }else if(arr[mid] > key) { // 왼쪽 탐색
            end = mid - 1;
            return binarySearch2(key, start, end);
        }else{ // mid == key
            return mid;
        }

    }

}

java에서는 java.util.Arrays.binarySearch를 지원한다.

 

배열은 정렬되어있어야 하고, 배열의 요소는 Comparable을 구현하고 있어야 한다.

 

단, 찾는 값이 없으면 음의 정수를 반환한다. (-1이 아닐 수 있다.)

 

키가 없을 때는 어느 위치에 넣어야 정렬 상태가 유지되는지 알려준다.

 

반환된 값에서 -1을 곱하고 1을 뺀 값을 인덱스로 삽입하면 정렬이 유지된다. (ret = -(idx+1))

 

Arrays (Java Platform SE 8 )

 

---