[알고리즘] 분할정복 (feat. Java)

분할정복 알고리즘이란

분할정복 알고리즘은 그대로 해결할 수 없는 큰 문제를 작은 문제로 분할하여 작은 문제부터 정복하여 결국에는 큰 문제를 해결하는 알고리즘이다.

 

대표적인 분할정복 알고리즘을 이용한 정렬 알고리즘은 퀵 정렬, 합병 정렬, 이진 탐색 등이 있다. 아래의 정렬 알고리즘 비교 표를 보면 알 수 있듯이 분할정복 알고리즘을 사용할 경우 적은 시간복잡도로 인해 실행시간이 빨라진다는 장점이 있다.

 

정렬 알고리즘	최대 실행 시간	최소 실행 시간	평균 실행 시간
선택 정렬	O(n^2)	O(n^2)	O(n^2)
삽입 정렬	O(n^2)	O(n)	O(n^2)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(n^2)	O(nlogn)	O(nlogn)

 

여기서는 정렬 알고리즘을 예로 들었지만 정렬 뿐만이 아닌 다른 문제들도 분할정복 알고리즘을 통해서 짧은 시간 복잡도로 해결이 가능하다.(EX : 이진탐색)

 

그렇기 때문에 정렬 알고리즘을 통해 분할정복 알고리즘에 먼저 이해하고 익숙해진 다음 그것을 다른 문제에 적용해보면 더 쉽고 간단하게 적용할 수 있을 것이다.

 

 

 

분할 정복 설계

• Divide : 문제를 더 작은 하위 문제로 더 이상 쪼개질 수 없을 때까지 나눈다.
• Conquer : 하위 문제를 재귀적으로 해결. 더 이상 나눌 수 없는 하위 문제를 만났을 때 탈출 조건을 설정(return)하고 해결
• Combine : Conquer한 문제를 통합하여 원래 문제의 답을 해결

 

분할정복 알고리즘에서 중요한 것은 큰 문제를 어떤 작은 문제로 Divide할 것인지가 주요 요점이다. 무작정 하위문제로 나눈 것이 아닌 작은 문제를 통해 큰 문제의 답을 도출할 수 있는 하위 문제로 잘 Divide한다면 Conquer, Combine과정은 쉽게 해결 할 수 있다.

 

 

 

분할정복 특징 및 장단점

• 분할된 작은 문제는 원래의 문제와 성격이 동일하다 -> 크기만 작아지는 것!!
• 분할된 문제는 서로 독립적이다 -> 순환적 분할 및 결과 결합 가능
• 장점
  • Top-down 재귀 방식으로 구현하기 때문에 코드가 직관적
  • 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결 가능
• 단점
  • 재귀 함수 호출로 오버헤드가 발생
  • 스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생할 수 있음

 

 

 

합병 정렬(Merge Sort)

설계

• Divide : 배열의 2개로 쪼갬
• Conquer : 부분 배열을 정렬
• Combine : 정렬도니 부분 배열을 하나의 배열로 합침

 

 

구현 코드

import java.io.*;

public class Main {
	
	static int[] arr, tmp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		arr = new int[n];
		tmp = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		mergeSort(0, n-1);
		for(int num : arr) {
			sb.append(num+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static void mergeSort(int left, int right) {
		if(left >= right) return;
		
		int mid = (left+right)/2;
		// divide
		mergeSort(left, mid); // 왼쪽 분할
		mergeSort(mid+1, right); // 오른쪽 분할
		
		// 분할(divide) -> 합병(merge)
		merge(left, mid, right);
	}
	
	static void merge(int left, int mid, int right) {
		int l = left;
		int r = mid+1;
		int idx = l;
		
		while(l <= mid || r <= right) {
			// 1. 오른쪽 분할의 원소를 이미 다 가져온 경우
			// 2. 왼쪽 분할에서 가져오지 않은 원소가 있고, 해당 원소(l)가 오른쪽 분할 원소(r)보다 작은 경우
			if(r>right || (l<=mid && arr[l]<arr[r])) {
				tmp[idx++] = arr[l++];
			}else { // 위에 해당하지않으면 오른쪽 분할에서 원소를 가져온다.
				tmp[idx++] = arr[r++];
			}
		}

		// left~right구간 정렬한 부분을 원래 배열 arr에 저장한다.
		for(int i=left; i<=right; i++) {
			arr[i] = tmp[i];
		}
	}

}

 

 

 

퀵 정렬(Quick Sort)

설계

• Divide : pivot 하나를 선택하여 pivot을 기준으로 배열을 두개로 쪼갬
• Conquer : pivot을 기준으로 pivot보다 큰값 혹은 작은 값을 찾는다. 왼쪽에서부터 pivot보다 큰 값을 찾고 오른쪽에서는 부터는 pivot보다 작은 값을 찾아서 두 원소를 비교, 분활된 부분 배열의 크기 0또는 1이 될때 까지 반복
• Combine : conquer과정에서 값의 위치가 바뀌므로 따로 결합 과정을 거치지 않는다.

 

 

구현 코드

import java.io.*;

public class Main {
	
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		quickSort(0,n-1);
		
		for(int num : arr) {
			sb.append(num+"\n");
		}
		System.out.println(sb.toString());
		
	}
	
	static void quickSort(int left, int right) {
		if(left>= right) {
			return;
		}
		
		int pivot = partition(left, right);
		quickSort(left,pivot-1);
		quickSort(pivot+1,right);
	}
	
	// 왼쪽 피봇 선택하는 경우
	static int partition(int left, int right) {
		int pivot = arr[left];
		int i = left;
		int j = right;
		while(i < j) {
			while(arr[j] > pivot&& i<j) {
				j--;
			}
			while(arr[i] <= pivot && i<j) {
				i++;
			}
			swap(i,j);
		}
		swap(left,i);
		return i;
	}
	
	static void swap(int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}

 

 

 

이진 탐색

설계

• Divide : 배열의 가운데 원소를 기준으로 왼쪽, 오른쪽 부분 배열로 분할, 탐색키와 가운데 원소가 같으면 분할 종료
• Conquer : 탐색키가 가운데 원소보다 작으면 왼쪽 부분 배열을 대상으로 이진 탐색을 호출, 크면 오른쪽 부분 배열을 대상으로 이진 탐색 호출
• Combine : 탐색 결과가 직접 반환되므로 결합은 불필요

 

 

구현 코드

// left : start, right: arr.length()-1
static int binarySearch(int[] arr, int left, int right, int key) {
	int mid =0;
	
	while(left<= right) {
		mid = (left+right)/2;
        
		if(key == arr[mid]) return mid;
        
		if(arr[mid] < key) {
			left = mid+1;
		}else {
			right = mid-1;
		}
	}
	return -1; // not found
}