분할과 정복 기법 (Divide and Conquer)

분할과 정복 기법  (Divide and Conquer)

 : 하향식 설계 기법

 : 문제의 크기를 작게 나누어서 좀 더 쉽게 해결할 수 있는 상태로 변환하여 문제를 해결하는 방법

 : 하나의 문제를 여러 개의 작은 문제로 나누어 각각에 동일한 해결 기법을 계속적으로 적용한 후, 결과들을 연합하여 원래의 문제를 해결

 : 분할된 부분의 문제들의 크기가 커서 해결이 여전히 쉽지 않을 경우, 각 부분의 문제들에 대해 다시 분할과 정복 기법 적용

 : 각 부분의 문제들이 간단히 해결될 수 있는 상태에 이를 때까지 반복 (순환 : recursion)

 

 재귀함수

 : 분할과 정복 기법을 위한 구현 기술

 : 처리 과정이 분할된 작은 문제들에 서로 동일한 로직이 여러 번 발생하는 것을 방지하기 위해 동적 프로그래밍 기법 사용

 

재귀적 알고리즘

 : 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법

 : 문제를 같은 형태의 작은 문제로 축소해서 원래의 큰 문제를 해결해가는 방식 (분할과 정복)에 사용

 

재귀적 알고리즘 설계 시 고려사항

 : 재귀호출이 한번 이루어질 때마다 처리할 문제는 계속 작아져야 함

 : 재귀호출이 무한히 계속되지 않고 최종적으로는 끝날 수 있도록 종료 조건이 있어야 함

 

재귀 호출 (recursive call)

 : 프로그래밍에서 함수가 자기 자신을 호출하여 순환 수행되는 것

 : 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 프로그램의 크기를 줄이고 간단하게 작성 가능

 

재귀 호출 예시

// 합계
public class exSum {
	public static void main(String[] args) {
		System.out.println(sum(10));
	}
    
	static int sum(int n) {
		if(n==0) {
			return 0;
		}
		else {
			return n + sum(n-1);
		}
	}
}

// 피보나치 수열
import java.util.Scanner;

public class exFibonacci {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		for (int i=1; i<=n; i++) {
			System.out.print(fib(i) + " ");
		}
		
		sc.close();
	}
	
	static int fib(int n) {
		if (n==1 || n==2) return 1;
		else return fib(n-1) + fib(n-2);
	}
}

// 팩토리얼 계산
import java.util.Scanner;

public class exFactorial {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.print("정수 입력 : ");
		int n = sc.nextInt();
		
		System.out.printf("%d! = ", n);
		System.out.print("1 = " + factorial(n));
		
		sc.close();
	}
	
	static int factorial(int n) {
		if (n == 0 || n == 1) return 1;
		else {
			System.out.print(n + " * ");
			return  n * factorial(n-1);
		}
	}
}

// 하노이의 탑
import java.util.Scanner;

public class Hanoi {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        System.out.print("원반 개수 입력 : ");
        int n = sc.nextInt();
        
        hanoi(1, 2, 3, n); //1번 기둥의 n개를 3번 기둥으로 옮김
	}
	
	static void hanoi(int from, int m, int to, int n) { // from -> to로 원판 n이동
		System.out.printf("f:%d m:%d t:%d n:%d\n", from, m, to, n);
		
		if(n == 0)
			return;
		
		hanoi(from, to, m, n-1); // 원판 n-1을 from -> m으로 이동
		System.out.printf("원반 [%d]을 %d에서 %d로 이동\n", n, from, to);//원판 n이 from -> to로 이동
		hanoi(m, from, to, n-1); // 원판 n-1을 m -> to로 이동
	}
}

 

분할과 정복 기법 응용 사례

이진 탐색 (Binary Search; 이분 탐색)

 : 전체 데이터 집합을 두 부분으로 나누어 검색하는 방법

 : 값이 어느 부분에 속하는지를 결정하여 그 부분에 대하여 순환적으로 탐색 수행

 : 정렬된 리스트에서 중간에 위치한 키 값과 찾고자 하는 값이 같으면 탐색 성공,

   다르면, 중간 항목 기준으로 두 부분 중 한쪽 리스트를 선택하여 키를 정한 후 다시 이진 탐색 -> 키 값과 같으면 성공

   여전히 탐색 실패 -> 나머지 다른 한쪽 리스트 이진 탐색

 

이진 탐색 특징

 : 분할 및 정복에 의한 탐색 방법 중 하나

 : 리스트가 정렬되어 있는 경우에 적합

 : 정렬되어 있지 않은 경우, 리스트의 항목들을 정렬 시켜야 함

   -> 레코드의 삽입/삭제 빈번하게 발생되는 경우, 리스트 재구성에 의한 항목들의 이동 요구됨

   -> 데이터의 삽입/삭제가 거의 없는 리스트에 적합

 

2원 합병 정렬 (Two-way merge sort)

 : 정렬된 2개의 리스트를 혼합하여 완전히 정렬된 하나의 리스트로 합하는 정렬 방식

 

퀵 정렬 (Quick sort)

퀵 정렬 설명은 아래 링크 참조

https://olli2.tistory.com/13?category=985942 

퀵 정렬 (Quick Sort)