7. 부분 정복 알고리즘(Decrease and Conquer)

  대학교 M.T나 술자리에서 '베스킨라빈스 31'게임을 많이 해본적이 있는가? 여러명이 둘러 앉은 다음 숫자 1부터 차례대로 1개부터 3개씩 숫자를 말하다가 31을 말하게 되는 사람이 패배하게되는 게임이다. 해당 게임의 필승 전략이 있을까? 2명이서 이 게임을 즐기고 있다고 가정해보자. 31을 말하면 안되므로, 당신이 30을 말하게 된다면 이길 것이다. 그렇다면 30을 말하게 될려면 상대방의 숫자가 27,28,29 도록 말해야 자신이 30을 말할 수 있다. 그러면 27,28,29를 말하게 할려면 어떻게 해야할까? 이런식으로 문제를 풀어 나갈 수 있다. 우리의 최종 목표인 31을 말하지 않기 위해 그 범위를 줄여나가면서 푸는 알고리즘을 부분 정복 알고리즘 (Decrease and Conquer)라고 한다.

  1. Decrease and Conquer

  큰 문제를 축소시켜 작은 부분부터 차례대로 문제를 풀어 나가는 방식을 통틀어 부분 정복 알고리즘이라고 한다. 2^10에 대한 문제를 푼다고 할때 축소를 어떻게 시키느냐에 따라 갈라지게 된다. 2^10을 2 * 2^9로 나눌 수도 있고, 2^5 * 2^5로 나눌 수 있다. 두 경우 모두 부분 정복 알고리즘에 해당된다. 첫번째의 경우 크기를 1씩 줄여나가는 것이고, 두번째의 경우 크기를 절반으로 줄이는 것이다. 결론적으로 두 방법 모두 동일한 답을 구하게 된다.

  우리가 자주 사용하는 정렬 방식 중에서 삽입 정렬(Insertion Sorting)이 대표적인 부분 정복 알고리즘이다. 삽입 정렬은 전체 자료 중에서 이미 정렬 된 부분과 비교해가며 하나씩 숫자를 정렬해 나가는 방식이다. 첫번째 자료와 두번째 자료를 비교하여 정렬한 뒤. 세번째 자료 부터 앞서 정렬된 부분에 차례대로 정렬해 나가는 방식이다. 아래 그림을 살펴보자.

  

삽입 정렬의 경우 n개의 자료에 대해 각각 자신의 위치를 찾는 비교를 수행해야하므로 시간복잡도는 O(n^2)이 된다.

  2. 위상 정렬 문제

  트리 구조 (Tree Structure) 문제의 경우 노드와 방향이 존재한다. 아래와 같은 트리 구조가 있다고 가정해보자.

  시작점이 될 수 있는 노드는 0과 1이 있고, 최종 노드가 5라고 하면 시작점부터 끝까지 가는 여러가지 방법이 있을 것이다. 예를 들어 1에서 시작한다고 가정하면 1,3,5 혹은 1,4,5 2가지 방법이 있다. 이 문제를 풀 때도 부분 정복 알고리즘을 사용할 수 있다. 

  시작점은 두개가 존개하므로 0과 1 차례대로 문제를 구하고, 0의 경우 2와 3으로 이동 가능하다. 그렇다면 0->2로 이동하는 경우를 모두 찾고 그 다음 0->3으로 이동하는 경우를 모두 찾아가는 방식을 취하면 된다. 이런식으로 위 트리 구조에서 경로를 모두 찾아 낼 수 있다. 이렇게 방향성이 있는 자료형에 대한 문제를 찾는 것을 위상 정렬 문제라고 한다. 위상 정렬 문제는 알고리즘에 따라 크게 DFS와 BFS로 나뉘게 된다. 이 알고리즘에 대한 자세한 내용은 나중에 트리구조에 대해 설명할 때, 더욱 자세히 설명할 것이다. 

3. 순열(Permutation) 문제

  n에 대한 순열을 만드는 작업은 n-1에 대한 순열을 만드는 작업과 매우 유사하다. n-1에 대한 순열을 만들고 해당 순열에 모든 자리수에 n을 삽입하면 순열을 구할수 있다. 3에대한 순열은 총 6개가 나오고, 6개의 결과에 모든 자리수에 4를 삽입하면 총 24개의 순열이 나오고 이것이 4에대한 순열이 된다. 이 과정을 이용한다면 순열 문제도 부분 정복 알고리즘으로 쉽게 풀어낼 수 있다. 

  이 과정으로 풀면 그 과정은 매우 간단하지만 많은 메모리와 시간이 걸리는 단점이 있다. 부분 정복 알고리즘의 경우 1부분 알고리즘이 된다. 이를 보완하기 위한 방법이 바로 "Johnson-Trotter 알고리즘"이다. 

위에서 보이는 과정처럼 순열 문제를 풀 수 있다. 이를 Pseudo Code 표현하면 다음과 같다.

 - Mobile Element : 주변에 자신보다 작은 값이 있는 원소 (자신이 가진 방향성에서)

While ( Mobile Element가 존재 할때까지 계속 반복 )

1. Mobile Element 중 가장 큰 원소 k 찾기

2. k와 방향성이 인접한 원소와 Swap

3. k보다 큰 원소 전부 방향 전환

4. 순열에 해당 숫자 리스트 새로 추가

4. 러시아 농부 알고리즘

  러시아 농부 알고리즘은 두개의 양의 정수를 곱할 때, 곱셈을 사용하지 않고 구하는 방식이다. 일반적으로 곱셈 없이 곱셈작업을 마친다면 for문을 사용하여 n번 더하여 곱셈을 마칠 것이다. 하지만 러시아 농부 알고리즘을 사용한다면 조금 더 효율이 좋은 알고리즘을 이용 할 수 있다.

  우선 기본적으로 사용하는 방법은 아래와 같은 코드이다.

public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int result = 0;
        
        for (int i=0; i<M; i++){
            result=result+N;
        }
        
        System.out.println(result);
 
    }
 
}

N * M이라고 가정했을 때, 총 M번의 덧셈 연산을 하게 된다.

  이제 러시아 농부 알고리즘을 사용해보자. 러시아 농부 알고리즘은 N이라는 숫자가 짝수인지 홀수 인지 알게 된다면, 아래와 같은 정의를 이용해 곱셈을 쉽게 하는 과정을 의미한다.

  구체적인 예시를 들어 설명해보자. 만약 50 * 65에 대한 연산을 진행한다고 하자. 그렇다면 위의 코드를 사용한다면 덧셈 연산을 총 50번 수행해야한다. 러시아 농부 알고리즘은 아래와 같은 과정을 거친다.

  

  n의 크기를 반으로 나누고 홀수 일때 발생하는 나머지 값의 합계를 구한다면, 7번의 연산만으로 두 수의 곱셈을 구할 수 있게 된다. 아래는러시아 농부 알고리즘을 적용한 것이다.

public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        System.out.println(alarusee(N,M));
 
    }
    
    public static int alarusee(int a, int b){
        int result=0;
        int c = b;
        
        while(a!=1){
            if(a%2==1){
                result+=c;
            }
            c+=c;
            a/=2;
        }
        
        result+=c;
        
        return result;
    }
 
}
 

  이렇게 풀게 된다면 곱셈 과정 없이 두 수의 곱을 구할 수 있다. 연산 횟수의 크기가 작다면 처음 소개한 연속 곱셈 방법에 비해 크게 효율적이지 못하지만, 두 수의 크기가 충분히 커지게 되면 더욱 큰 효율을 발휘 할 것이다. 러시아 농부 알고리즘 역시 m에 대한 연속적인 덧셈과정을 반으로 나눈 나머지 단위로 묶어서 처리하는 방식인 대표적인 부분 정복 알고리즘에 해당된다.

 

  앞서 소개한 알고리즘 외에도, 우리가 엑셀을 하면서 자주 사용하는 보간 탐색이나 나중에 소개할 대표적인 검색 방법인 이진 트리 역시 대표적인 부분 정복 알고리즘에 해당된다. 앞서 소개한 알고리즘 중 삽입 정렬 알고리즘은 앞으로 배울 기본적인 세가지 Sorting 방법 중 평균적으로 가장 효율이 좋은 알고리즘이기 때문에 많이 사용된다. (절대적이 아니라 평균적이다!) 앞서 살펴봤듯이 부분 정복 알고리즘은 데이터의 크기가 클 수록 효율적이다. Brute Force는 단순하게 계속 더해가지만 사전 작업이 필요 없다는 장점이 있다. 하지만, 부분 정복 알고리즘은 문제의 크기를 나누기 위한 사전 작업이 필요하다. 문제에 따라서는 사전 작업의 시간이 단순 작업 시간 보다 앞지를게 되고, 그렇다면 부분 정복 알고리즘은 의미가 없어지게 된다. 또한, 연속적으로 구성된 자료형에서 매우 큰 효율을 발휘한다. 앞서 언급한 사전 작업에 대한 필요성이 사라지게 되므로 BruteForce 보다 무조건 좋은 효율을 발휘할 수 있다.