분할 정복 알고리즘
분할 정복은 분할과 정복 그리고 경우에 따라서 통합으로 나눠서 해결하는 것을 말한다. 주어진 문제를 부분으로 나눠서 해결하는 경우가 전체를 한번에 해결하는 경우보다 쉬워지는 성질을 이용한 케이스이다.
- 분할(Devide) : 해결할 문제를 여러 개의 작은 부분으로 나눔
- 정복(Conquer) : 나눈 작은 문제를 각각 해결
- 통합(Combine) : 해결된 해답을 모음
만약 N개의 동전중 무게가 가벼운 가짜 동전이 한개 있을때 이 가짜동전을 찾기위해서 한개씩 대조하는 방법을 사용하면 저울을 최소 1번, 최대 N/2번 사용해야 한다. 이는 시간도 많이 들고 비효율적이다. 가짜 동전을 더 효율적으로 찾기 위해서 분할 정복 기법을 사용할 수 있다.
가짜 동전을 찾기위해 하나의 동전씩만 저울에 올리는 것이 아닌 동전을 두 그룹으로 나눠서 저울에 올린다. 그 다음 더 가벼운 그룹의 동전을 다시 두 그룹으로 나눠서 무게를 비교하며 이 방법을 마지막 한개씩만 남을때까지 반복하면 가짜 동전을 찾을 수 있다.
이진 검색
이진 검색은 분할 정복을 이용한 대표적인 예시이다. 이진 검색을 사용하기 위해선 기본적으로 주어진 데이터가 정렬되어 있어야 한다.
- 입력값으로 데이터가 들어오고 찾을 범위를 데이터의 시작과 끝으로 설정한다.
- 주어진 데이터의 중간지점을 찾아 찾고자 하는 target이랑 비교한다.
- 만약 target이 중간지점의 값보다 클 경우 찾을 범위를 기존 범위의 중간지점 바로 다음부터 기존 범위 끝까지 설정하여 2번을 반복한다.
- 만약 target이 중간지점의 값보다 작을 경우 찾을 범위를 기존 범위의 시작부터 중간지점 바로 직전까지 설정하여 2번을 반복한다.
- 만약 target이 중간지점의 값과 일치 할 경우 해당 인덱스를 리턴한다.
- 만약 찾는 범위의 시작점과 끝지점이 역전되는 경우 값이 주어진 데이터안에 없는 경우이므로 검색을 종료한다.
public class BinarySearchTest {
static int[] map = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
public static void main(String[] args) {
int target = 5;
int result = binarySearch(target, 0, map.length - 1);
if (result != Integer.MAX_VALUE) System.out.println("target의 index : " + result);
}
static int binarySearch(int target, int x, int y) {
if (x > y) {
System.out.println("값이 주어진 숫자 배열 안에 없음");
return Integer.MAX_VALUE;
}
if (target > map[y] || target < map[x]) {
System.out.println("값이 주어진 숫자 배열의 값들을 벗어남");
return Integer.MAX_VALUE;
}
int center = (x + y) / 2;
if (map[center] == target) return center;
if (map[center] > target) return binarySearch(target, x, center - 1);
else return binarySearch(target, center + 1, y);
}
}
거듭 제곱 구하기
거듭 제곱 또한 분할 정복기법으로 구현할 수 있다. 거듭 제곱을 하고자 하는 수 x를 n번만큼 곱하는 연산을 하는 것보다 더 효율적으로 구할 수 있다.
- 거듭제곱을 구하는 방법은 지수 n이 짝수인 경우와 홀수인 경우로 나눠진다.
- 만약 짝수인 경우 지수 n를 2로 나눠서 x의 n/2제곱을 두번 곱하는 형태가 된다.
- 홀수인 경우 지수 n에서 1을 빼고 2로 나눈 값을 두번 곱하고 x를 한번 더 곱하는 형태가 된다.
public class PowTest {
// x의 n승 값 구하기
public static void main(String[] args) {
int x = 2;
int n = 20;
int result = 1;
for (int i = 0; i < n; i++) { // 시간 복잡도 O(n)
result *= x;
}
System.out.println(result);
System.out.println(pow(x, n)); // 시간 복잡도 O(log n / log 2)
}
static long pow(int x, int n) {
if (n == 1) {
return x;
}
if (n % 2 == 0) {
return pow(x, n / 2) * pow(x, n / 2);
} else {
return x * pow(x, (n - 1) / 2) * pow(x, (n - 1) / 2);
}
}
}
참고자료
댓글