9. 변환 정복 알고리즘 (Transform & Conquer)

  1부터 100까지의 숫자 중 특정한 숫자 하나를 찾는 방법은 무엇이 있을까? 가장 간단하고 정확한 방법은 찾으려는 1부터 100까지 숫자를 각각 비교해나가는 방법이다. 조금 무식하고 오래 걸리는 방법이긴 하지만 더 정확한 방법은 없다. 특히 숫자가 배열 구조로 저장되어 있다면 이런 방법을 사용할 수 밖에 없다. 이 구조를 이진 트리 구조로 바꿔보자. 최상위 노드에 중앙 값인 50을 넣고 그 아래는 각 서브트리에 해당하는 중앙 값은 25와 75를 차례대로 기록한다. 이런 방식으로 1부터 100에 대한 숫자를 이진 트리로 바꿔 저장되어 있다고 생각해보자. 찾으려는 숫자를 50과 비교하여 크다면 75서브트리로, 50보다 작다면 25서브트리로 내려간다. 이런 방식으로 숫자를 찾게 된다면 단 7번의 비교로도 원하는 숫자를 찾아낼 수 있다. 문제를 해결하기 위해 자료와 알고리즘 구조를 바꿔 문제를 해결 하는 것을 변환 정복 알고리즘 (Transform & Conquer)라고 한다.

1. Instance Simplification

  동일 문제를 더욱 간소한 사례로 변경 하는 것을 'Instance Simplification'이라고 한다. 복잡한 구조를 가진 문제를 쉽게 풀 수 있도록 단순화 하거나, 정렬하는 방식의 문제 해결 방법이다.

  예시로 보여줄 문제는 한 리스트에 있는 숫자들 중 가장 많이 들어있는 숫자가 무엇인지 파악하는 방법이다. 아래의 숫자를 저장하고 있는 리스트가 있다고 생각해보자.

A={5, 1, 5, 7, 6, 5, 7}

  사람의 뇌는 워낙 훌륭해서 지금 위에 있는 자료를 살짝만 보더라도 직관적으로 5가 가장 많은 숫자라는걸 단 한번에 알아차릴 수 있다. 하지만 컴퓨터는 그렇지 못하다. 자료의 처음부터 하나씩 검사를 해나가면서 가장 많은 수가 어떤 것인지 체크해야 한다. Brute Force 알고리즘으로 가장 많은 자료가 무엇인지 한번 찾아보자.

  총 7개의 자료 중에서 첫번째 자료인 5를 가져온다. 그리고. 5라는 숫자가 위에 리스트에서 몇번 나오는지 체크를 하고 그 개수를 저장을 한다. 이 과정에서 맨 앞의 5를 제외한 6개의 숫자를 비교하는 연산이 실시된다. 그 다음 자료 1을 가져와 다시 뒤에 있는 리스트를 비교한다. 이 과정에서는 총 5번의 비교 연산이 실시된다. 다음에는 다시 5번이므로 안해도 되고, 그 다음 숫자 7을 가져오고 총 3번의 비교 연산을 수행한다. 그 다음 저장한 숫자중 가장 값이 큰 숫자가 무엇인지 확인한다면 5가 리스트에서 가장 자주 나타난 숫자라는 사실을 알 수 있게 된다.

  n개의 자료가 존재한다면, (n-1)번의 비교 연산, (n-2)번의 비교 연산을 반복적으로 수행하게 된다. 그리고 저장된 숫자를 최종적으로 확인하여 계산이 끝나게 된다. 배열에서 가장 큰 숫자를 찾는 작업은 n번의 비교 연산으로 찾아 낼 수 있다. 위 문제를 Brute Force로 풀게 되면 아래와 같은 수식으로 구할 수 있다.

  n번의 비교 연산의 경우 시간복잡도가 O(n)이므로, O(n^2)에 속하게 된다. 따라서 위 알고리즘의 시간 복잡도는 O(n^2)이 된다. 최악의 연산을 보이는 경우는 리스트 안에 있는 숫자들 중 같은 숫자가 없는 경우다. 꼼짝없이 모든 숫자에 대한 비교 연산을 모두 시행해야 하기 때문이다.

  이 문제를 조금더 쉽게 풀기 위해서 변환 정복 알고리즘을 적용해보자. 원리는 간단하다 보다 간소한 사례의 알고리즘을 적용하기 위해 정렬되지 않은 리스트를 정렬 시킨다. 정렬 알고리즘은 앞서 배운 알고리즘중 Merge Sort 를 사용한다. Merge Sort의 시간 복잡도는 앞서 설명한 바와 같이 O(n log n)이다. 위의 리스트를 정렬한다면 아래와 같이 정리 될 것이다.

A={1, 5, 5, 5, 6, 7, 7}

  첫번쨰 숫자 1부터 리스트 상에서 나오는 길이를 계산하여 저장한다. 첫번째 숫자를 가지고 동일한 숫자가 반복되면 해당 숫자의 길이를 1 증가 시키고 다르다면 새롭게 길이를 저장한다. 1의 경우 1개의 숫자나오므로 1을 저장하고, 5는 3을 저장하게 된다. 이 과정은 총 n번의 연산으로 가능하게 된다. 이 과정의 시간 복잡도를 구하면 아래와 같다.

  앞서 구힌 알고리즘 보다 더 좋은 성능으로 문제를 해결 할 수 있다.

2. Representation Change

  표현 방식을 바뀌어 문제를 해결하는 방법을 Representation Change라고 한다. 앞서 설명한 이진 탐색트리를 통한 숫자 찾기 역시 이 방법 중 하나다. 이진 탐색 트리가 성립되기 위해서는 아래의 조건들이 필요하다.

1. 각 노드에 값이 있다.
2. 각 노드의 키값은 모두 달라야 한다.
3. 값들은 전순서가 있다.
4. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
5. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
6. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
7. 중복된 노드가 없어야 한다.

  이진 탐색 트리 중에서 최하위 노드의 차수들의 차이가 1 미만인 경우 트리를 AVL트리 라고 한다.  AVL트리는 기존 이진 탐색트리에서 발생할 수 있는 최악의 경우인, 좌측 혹은 우측으로 자료형이 쏠리게 되는 현상을 막아주게 된다. 이진트리의 경우 각 노드의 차수를 고려하지 않고 데이터를 저장하기 때문에 위와 같은 현상이 나타날 수 있다. 따라서, AVL트리를 이용한다면 어떤 경우에서나 비슷한 성능을 가져오는 알고리즘을 만들어 낼 수 있다. 따라서 AVL 트리에서 평균적인 탐색 연산에 대한 시간 복잡도는 O(log n)이 된다.

  다만, AVL 트리의 경우 데이터를 삽입, 삭제할 때 일반 이진 탐색 트리보다 복잡한 과정을 거치게 된다. 기존의 이진 탐색 트리와 같이 삽입 과정을 수행하다가 불균형이 발생하게 되는 경우가 있다. AVL 트리에서 말하는 불균형이란, 삽입 연산 이후 최하위 자식 노드의 차수가 2이상 차이나게 되는 경우다. x,y,z 3개의 노드가 존재하고, 이 중 z가 불균형이 발생된 트리 중 가장 최상위 root 노드라고 가정하자. 그렇다면 아래와 같이 4가지 타입의 불균형이 발생한다.

  첫 번째 사진은 불균형이 발생한 최상위 노드 C 기준 좌측 서브트리 중 좌측 노드에서 불균형이 발생된 LL타입의 불균형이다. 두 번째는 최상위 노드 A 기준 우측 서브트리 중 우측 노드에서 불균형이 발생된 RR타입의 불균형이다. 그리고 세 번째는 최상위 노드 A 기준 우측 서브트리 중 좌측 노드에서 불균형이 발생한 RL타입이다. 마지막은 최상위 노드 C 기준 좌측 서브트리 중 우측 노드에서 불균형이 발생한 LR타입이다. 

  이렇게 4개의 타입의 불균형을 해결하기 위해서 회전을 사용합니다. LL회전과 RR회전은 매우 간단합니다. 두 타입에서 공통적으로 있는 중앙 노드인 B를 상위 노드로 변경하고, 최상위 노드를 B의 하위 노드로 전환하면 간단하게 문제가 해결됩니다. LL 회전의 경우 C를 C 자신의 좌측 서브트리로 내리고. B를 원래 C가 있던 자리에 삽입하면 됩니다. RR 회전 역시 반대방향을 동일하게 문제를 해결하면 됩니다.

  하지만 RL 타입과 LR 타입의 경우 약간 복잡한 과정을 거쳐야 합니다. 두 경우 모두 위 사진을 기준으로 중앙에 존재하게 되는 값은 모두 B입니다. 그렇기 때문에 2번의 회전을 거쳐 불균형을 해결합니다. 우선, RL회전의 경우 하위 2개의 노드 C,B에 대하여 우측 회전을 실시 합니다. C를 우측 하위 노드로 내리고 그 자리에 B를 올려 RR 타입과 동일한 방법을 만듭니다. 그 이후 RR 타입을 해결했던 방식을 그대로 적용합니다. LR 타입 역시 마찬가지로 A,B에 대하여 좌측 회전을 실시하고 LL타입과 동일하게 문제를 해결하면 됩니다.

  3.Problem Reduction

  이미 알려져 있는 다른 문제로 치환해서 푸는 방법을 Problem Reduction이라고 한다. 이때 변형이 완료된 문제는 반드시 이전에 존재한 문제보다 휠씬 쉬운 알고리즘이어야 하며 변형하는데 소요되는 시간 역시 고려해야 한다.

  최대 공약수와 최소 공배수를 구하는 알고리즘은 대표적은 Problem Reduction이다. 항상 m > n이 성립하는 두 수 m, n의 최대 공약수와 최소 공배수를 구한다고 생각해보자. 우선 두 수의 최대 공약수를 구하는 코드는 아래와 같다.

import java.util.*;
 
public class Solution {
 
    public static int gcd(int m, int n){
        while(n!=0){
            int r = m%n;
            m=n;
            n=r;
        }
        
        return m;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
 
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        
        System.out.println(gcd(m,n));
    }
    
}

  직관적인 최소 공배수를 구하기 위해서는 각 숫자들의 배수를 구하고, 서로 일치하는 배수가 있을 때 까지 곱해나가야 한다. 이 과정으로 구한 코딩을 구현하면 아래와 같다.

public static int lcm(int m, int n){
    for (int i=1; i<n; i++){
        int p = m*i;
        if(p%n==0) return p;
    }
    return m*n;
}

  하지만, 최대공약수를 풀어내는 알고리즘을 가지고 있다면 더욱 쉽게 최대 공약수를 구할 수 있다.

public static int lcm(int m, int n){
    return m*n/gcd(m,n);
}

  딱 이 한줄의 코드로 충분히 최대 공약수를 만들 수 있다.

  변환 정복 알고리즘은 앞선 정복 알고리즘에 비해서 더욱 까다롭고, 사용 범위가 좁다. 그 이유는 변환 과정에 소요되는 자원이 너무 큰 경우가 매우 자주 발생하기 때문이다. 위 3가지 경우에서 모두 더 쉬운 알고리즘으로 바꾸는 작업을 수행 하는 과정이 더욱 복잡한 경우도 종종 있게된다. 변환 정복 알고리즘 사용을 위해서는 매우 제한 적으로 사용해야 할 것이다.