알고리즘의 설계 기법 - 분할정복기법/분할정복 알고리즘

알고리즘의 설계 기법

• 문제를 해결해 나가는 기법
• 알고리즘이 채택한 전략이나 관점

대표적인 알고리즘 설계 기법

• 분할 정복 기법 (Divide and Conquer)
• 욕심쟁이 기법 (Greedy method)
• 동적 프로그래밍 기법 (Dynamic programming)

분할 정복 기법 (Divide and Conquer)

• 하향식 설계 기법
• 문제의 크기를 작게 나누어서 좀 더 쉽게 해결할 수 있는 상태로 변환하여 문제를 해결하는 방법
  • 하나의 문제를 여러 개의 작은 문제로 나누고, 각각에 동일한 해결 기법을 계속적으로 적용한 후 결과를 연합하여 원래의 문제를 해결하는 기법
• 분할된 부분의 문제들이 크기가 커서 해결이 쉽지 않을 경우, 각 부분의 문제에 ㄷ대해 다시 분할 정복 기법 적용
• 각 부분의 문제들이 간단히 해결될 수 있는 상태에 이를 때까지 반복(순환 : recursion)
• 재귀함수는 분할 정복 기법을 위한 구현 기술
  • factorial, 피보나치 etc...
• 처리 과정 분할된 작은 문제들이 서로 동일한 경우가 발생되며 재귀적으로 처리하는 알고리즘에서 중복된 계산이 계속 발생
  • 이를 방지하기 위해 동적 프로그래밍 기법 사용

### 분할 정복 기법으로 최대/최소 값 구하는 예의 알고리즘 처리 과정

예: [45 7 2 36 61 25 22 15]

분할: [45 7 2 36] / [61 25 22 15] 

분할: [45 7] / [2 36] / [61 25] / [22 15]

`max = 45 min = 7 / max = 61 imn = 25`

 `max = 36 min = 2 / max = 22 min =  15`

결합: [45 7 2 36] / [61 25 22 15]

`max = 45 min = 2 / max = 61 min = 15`

결합: [45 7 2 36 61 25 22 15]

`max = 61 min = 2`

분할 정복 기법 응용 예

• 이진 탐색
• 2원 합병 정렬
• 퀵 정렬

이진 탐색(Binary Search)

• 전체 데이터 집합을 두 부분으로 나누어 검색하는 방법
• 값이 어느 부분에 속하는가 결정하여 그 부분에 대하여 순환적으로 탐색을 수행하는 방법
• 즉, 정렬된 리스트에서 중간에 위치한 키 값과 찾고자 하는 값이 같으면 탐색 성공
• 서로 다르면, 중간 항목을 기준으로 두 부분 중 한쪽 리스트를 선택하여 키를 정한 후 다시 이진 탐색해서 찾으면 성공
• 그래도 없으면, 나머지 다른 한쪽에서 이진 탐색

이진(이분) 탐색 특징

• 분할 및 정복에 의한 탐색 방법의 하나
• 리스트가 정렬되어 있는 경우에 적합한 탐색 방법
• 따라서, 이진 탐색을 적용할 경우,
  • 리스트의 항목들을 정렬시켜야 하는데 레코드의 삽입, 삭제가 빈번히 발생되는 경우는 리스트 재구성에 의한 항목들의 이동이 요구됨
  • => 데이터의 삽입, 삭제가 거의 없는 리스트에 적합

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

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

퀵 정렬(Quick sort)

• 분할 정복 정렬 방법의 하나
• 전체 리스트를 2개의 부분 리스트로 분할하고
• 각각의 서브 리스트를 다시 퀵정렬로 정렬
• 기준 값보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽으로 재배열

정렬 방법

• 전체 리스트에서 한 원소를 기준 값(pivot)으로 선정
• 피벗을 기준으로 두 개의 서브 리스트로 분할
• 왼쪽 서브 리스트
  • 피벗보다 작은 값의 원소들로 구성
• 오른쪽 서브 리스트
  • 피벗보다 큰 값의 원소들로 구성
• 각각의 파티션에 대해 다시 퀵 정렬을 순환 적용
  • 피벗 선정 및 파티션 분할

재귀적 알고리즘

재귀 (recursion: 순환)

• 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
• 문제를 같은 형태의 작은 문제로 축소해서 원래의 큰 문제를 해결해가는 방식(분할 및 정복)에 사용
• 고려사항
  • 재귀호출이 한 번 이루어질 때마다 처리할 문제는 계속 작아져야 한다는 점
  • 무한히 계속되지 않고 최종적으로는 끝날 수 있도록 종료 조건 필요

상품 포장 작업(x개)

- 포장된 상품 갯수가 x개인지 확인
- x개가 되면 '상품 포장 작업' 종료
- x개가 안됐을 경우, '상품 포장 작업' 진행

재귀 호출(recursive call)

• 프로그래밍에서 함수가 자기 자신을 호출하여 순환 수행되는 것
• 장점
  • 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식보다 프로그램의 크기를 줄이고 간단하게 작성 가능

연습문제

재귀 호출 예(1) - 피보나치 수열

• SUM(N) = N + (N-1) + (N-2) + ... + 1
• SUM(5) = 5 + 4 + 3 + 2 + 1
• 재귀 호출 사용할 경우

SUM(5) = 5 + SUM(4)
       = 5 + 4 + SUM(3)
       = 5 + 4 + 3 + SUM(2)
       = 5 + 4 + 3 + 2 + SUM(1)
       = 5 + 4 + 3 + 2 + 1

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();

        for(int i = 1; i<=num; i++){
            System.out.print(fibo(i)+" ");
        }
    }

    public static int fibo(int n){
        if(n==1 || n==2) return 1;
        else return fibo(n-2) + fibo(n-1);
    }
}

재귀 호출 예(2) - 팩토리얼 값 구하기

• n! = n * (n-1) * (n-2) * ... *1

import java.util.Scanner;

public class Factorial {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int num = scan.nextInt();
        System.out.printf("%d! = ",num);
        for(int i = 1; i<=num; i++){
            System.out.printf("%d * ", (num-i+1));
        }
        System.out.print("= ");
        System.out.println(factorial(num));
    }

    public static int factorial(int n){
        if(n <= 1) return n;
        else return factorial(n-1) * n;
    }
}

재귀 호출 예(3) - 하노이의 탑

• 퍼즐의 일종으로 원판 이동 횟수 구하기
• 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판 존재
• 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여있음
• 게임의 목적 두 가지 조건을 만족하면서, 한 기둥에 꽂힌 원판들을 순서 그대로 다른 기둥으로 옮겨 다시 쌓는 것
  • 한 번에 하나의 원판만 옮길 수 있음
  • 큰 원판이 작은 원판 위에 있어서는 안 됨

import java.util.Scanner;

public class Hanoi {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.print("원반 갯수 입력: ");
        int num = scan.nextInt();

        // 1번 기둥의 n개를 3번 기둥으로 옮김
        hanoi(1,2,3,num);
    }

    // from -> to로 원판 n이동
    static void hanoi(int from, int m, int to, int n){
        System.out.printf("f:%d m:%d t:%d, n:%d\n",from, m, to, n);

        if(n == 0)
            return;

        // 원판 n-1을 from -> m으로 이동
        hanoi(from, to, m, n-1);
        System.out.printf("원반 [%d]을 %d에서 %d로 이동\n", n, from, to);
        hanoi(m, from, to, n-1);
    }
}