분할 정복

분할정복의 개념

1) 분할: 해결할 문제를 여러 개의 작은 부분으로 나누기

2) 정복: 나눈 작은 문제를 각각 해결하기 => 이 때 나눈 작은 문제가 더 나눠질 수 있다면 다시 나눈다.

3) 통합: 해결한 해답을 모으기

 

분할정복의 응용

1) 병합 정렬(top-down 방식) - 안정 정렬

 

(1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면  정렬

(2) 데이터 집합을 반으로 분할

(3) 나눈 집합을 하나의 집합으로 병합

(4) 최소 크기가 될 때까지 분할

(5) 조각난 데이터 집합을 정렬하며 병합(재귀 호출 이용)

시간 복잡도	공간 복잡도
O(nlogn)	O(n)

2) 퀵정렬 - 불안정 정렬

 

(1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면  정렬

(2) 데이터 집합을 반으로 분할 => 이때 기준 아이템(pivot item; 좌,우,증간값)을 중심으로 작은 것은 왼쪽 큰 것은 오른쪽에 배치
     - 호어 파티셔닝 방식

     - 로무토 파티셔닝 방식(백준 24090); 가장 마지막 값을 피봇 값으로 설정

import java.util.Scanner;

public class Main { // 로무토 파티션 활용
	static int k, cnt;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		k = sc.nextInt();

		int[] arr = new int[n];
		for (int a = 0; a < n; a++) {
			arr[a] = sc.nextInt();
		}
		int l = 0;
		int r = arr.length - 1;
		cnt = 0;
		quicksort_L(arr, l, r);
		if (cnt < k) {
			System.out.println(-1);
		}
		sc.close();

	}

	private static void quicksort_L(int[] arr, int l, int r) {
		if (l < r) {
			int norm = L_partition(arr, l, r);
			quicksort_L(arr, l, norm - 1);
			quicksort_L(arr, norm + 1, r);
		}
	}

	private static int L_partition(int[] arr, int l, int r) {
		// 가장 마지막 값을 피봇 값으로 지정
		int last = arr[r];
		int i = l - 1;
		for (int j = l; j < r; j++) { // 마지막 값 직전까지 반복문을 돈다.
			if (arr[j] <= last) { // 피봇값보다 작으면 //반대로, 크면 이동하지 않고 멈춰있음 -> 뒤에 작은 원소 나오면 교환하려고
				++i; // 증가시켜서
				int tmp = arr[j]; // i와 j 서로 값 바꾸기
				arr[j] = arr[i];
				arr[i] = tmp;
				cnt++;
				if (cnt == k) {
					System.out.print(arr[i] + " ");
					System.out.print(arr[j]);
				}
			}
		}
		if (i + 1 != r) {
			int tmp = arr[r]; // 서로 값 바꾸기
			arr[r] = arr[i + 1]; // 작은범위의 경계에 있는 원소보다 하나 큰 애랑 피봇이랑 교환
			arr[i + 1] = tmp; // 정렬된 최종 위치
			cnt++;
			if (cnt == k) {
				System.out.print(arr[i + 1] + " ");
				System.out.print(arr[r]);
			}
		}
		return i + 1; // 정렬된 원소의 위치 반환 이 값을 경계로 재 정렬
	}
}

(3) 데이터의 범위가 0이나 1이 될 때까지 분할 및 배

 

3) 거듭 제곱

 

(1) C^8 = C*C*C*C*C*C*C*C

(2) C^8 = (((C^2)^2)^2)  => 3번의 연산으로 같은 결과 도출 

(1) 단순히 자신을 n번 곱하는 경우 시간 복잡도	(2)지수를 반으로 나눠 거듭제곱 수행하는 시간 복잡도
O(n)	O(log2n)

 

3) 이진 검색