10. 시간-공간 변환 (Space-Time trade off)

  앞선 시간에 리스트 안에 있는 데이터의 개수를 구하는 방법에 대한 알고리즘을 배워보았다. Brute Force 방식을 이용해 O(n^2) 시간 복잡도를 가지는 알고리즘을 배웠고, Transform & Conquer를 이용하여 미리 정렬을 수행한 다음 차례대로 그 숫자를 읽는 방법에 대해 배웠다. 두가지 방법보다 더욱 쉽게 데이터 안에 있는 숫자들의 개수를 구하는 방법이 있다. 

A = {5, 2, 7, 5, 4, 1, 2, 3}

  다음과 같이 총 8개의 자료가 존재한다고 하고 리스트 안에 있는 최소값과 최대값이 1과 7이라는 사실을 알고 있다고 가정하자. 그렇다면 공간 7개를 가지는 별도의 리스트를 만든다. (Ex. B[7]의 리스트 생성) 그리고 인덱스 0부터 7까지 있는 해당 배열에 A를 탐색하며 해당 숫자와 인덱스가 일치하는 경우 B값을 1씩 추가한다. 그런 방식으로 A 전체를 읽는다. 다시, B전체를 읽으면서 최대값을 찾게 된다면 총 N번의 탐색 2번으로 리스트 A에 있는 값 중 빈도가 높은 숫자가 무엇인지 알아 낼 수 있을 것이다. 해당 알고리즘의 시간 복잡도는 O(n)이 된다.

  이처럼 기존의 배열과 다른 별도의 리스트 공간을 만들어 더욱 빠른 알고리즘을 구현 해낼 수 있다. 이 방식이 바로 Space-Time trade off이다.

1. Radix Sorting

  가장 대표적인 Space-Time trade off 알고리즘 바로 기수 정렬(radix sorting)이다. 만약 한 리스트에 존재하는 숫자들이 모두 정수형 숫자들이라는 가정이 있다면, 기수 정렬을 통해서 무려 O(n)의 정렬 알고리즘을 만들어 낼 수 있다.

A = {107, 33, 25, 77, 59, 80, 55, 102, 210, 188, 680, 47}

  위 와 같이 리스트에 정수형 숫자 12개가 저장되어 있다고 가정하자. 이 숫자들의 1의 자리 숫자들만 가지고 정렬을 시작한다. 정렬 방식은 0부터 9까지의 숫자가 있는 별도의 리스트를 만들고, 만약 1의자리 숫자가 7이라면 7번 리스트에 연결시킨다. 그다음 숫자 33은 3번 리스트에 연결된다. 그다음 큰 리스트 번호가 작은 순서대로 다시 자료들을 읽어 나간다. 기수 정렬에 대한 구조는 아래와 같게 나타난다.

  1의 자리를 통해 정렬된 후의 리스트는 아래와 같다.

A = {80, 210, 680, 102, 33, 25, 55, 107, 77, 47, 188, 59}

  위와 같은 방식으로 10의 자리 역시 정렬을 하면 리스트가 아래와 같이 정렬된다.

A = {102, 107, 210, 25, 33, 47, 55, 59, 77, 80, 680, 188}

  마지막으로 100의 자리에 대한 정렬을 수행하면 리스트가 다음과 같이 정렬된다.

A = {25, 33, 47, 55, 59, 77, 80, 102, 107, 188, 210, 680}

  이런 방식을 적용한다면 가장 큰 자리수가 d라고 할 때, O(dn)의 시간 복잡도를 가지는 정렬 알고리즘을 구할 수 있다. 정수형에 대해서만 정렬할 수 있다는 한계점이 분명 존재하지만, 가정 하에서는 매우 강력한 정렬 알고리즘이다. 별도의 배열 혹은 리스트 공감을 만들어 더욱 빠른 정렬 알고리즘을 만들 수 있다.

2. Hashing

  해싱 함수는 Space-Time trade off 알고리즘의 대표적인 예시입니다. 해싱은 자료 구조의 일종으로 데이터를 저장하는 공간에 해싱 데이터를 붙여 구성되어 있는 구조다. 

    

  총 4명의 이름에 대한 값이 0부터 15로 구성된 Hash Table에 저장되게 된다. 위의 사진의 경우 'John Smith'와 'Sandra Dee'사이에 해시 충돌이 발생했다. Key 값은 임의로 만든 hash function에 의해 변환된다. 

  우리가 해시 구조를 사용하는 이유는 여러가지가 있다. 실제 값을 숨기고 암호화 하기 위해서 사용하기도 하고, 데이터 구분의 편의성을 위해서 사용하기도 한다. 하지만 알고리즘 학문에서 해시를 사용하는 가장 큰 이유는 탐색 과정의 시간 복잡도를 비약적으로 줄이기 위해서 사용한다. Hash Function을 알고 있다면, 시간 복잡도 O(1)로 해당 데이터에 접근이 가능하다. 예를 들어서 알아보자.

  총 20명의 사람을 데이터에 저장하기로 했다. 이들을 해시 구조로 저장할 것이며, 해시 값은 이름 첫번째 알파벳이 A~Z 순으로 해당하는 순서 숫자에 저장한다고 가정하자. 예를들어 'Alice'라는 사람이 접근하게 된다면 해시 값은 1로 부여 받게 될 것이고, 'Kaithy'라는 사람이 접근하게 되면 해시 값은 10이 부여 될 것이다. 데이터를 모두 저장한 다음 앞서 말한 20명 중에서 'Smith'라는 사람을 찾으려고 한다고 가정하자. 해시 함수를 알고 있다면 Smith가 저장된 위치는 해시 값이 18이라는 사실을 쉽게 알 수 있다. 이런 식으로 시간 복잡도 O(1)로 접근이 가능하다. 이 과정을 Java Code로 해시 자료구조를 구현해보자.

import java.util.*;
 
public class Solution {
 
    public static HashMap<String,Integer> map = new HashMap<String,Integer>();
    
    public static Integer HashFunction(String key){
        char[] arr = key.toCharArray();
        if(arr[0]=='a') return 1;
        if(arr[0]=='b') return 2;
        if(arr[0]=='c') return 3;
        if(arr[0]=='d') return 4;
        if(arr[0]=='e') return 5;
        if(arr[0]=='f') return 6;
        if(arr[0]=='g') return 7;
        if(arr[0]=='h') return 8;
        if(arr[0]=='i') return 9;
        if(arr[0]=='j') return 10;
        if(arr[0]=='k') return 11;
        if(arr[0]=='l') return 12;
        if(arr[0]=='m') return 13;
        if(arr[0]=='n') return 14;
        if(arr[0]=='o') return 15;
        if(arr[0]=='p') return 16;
        if(arr[0]=='q') return 17;
        if(arr[0]=='r') return 18;
        if(arr[0]=='s') return 19;
        if(arr[0]=='t') return 20;
        if(arr[0]=='u') return 21;
        if(arr[0]=='v') return 22;
        if(arr[0]=='w') return 23;
        if(arr[0]=='x') return 24;
        if(arr[0]=='y') return 25;
        if(arr[0]=='z') return 26;
        return 0;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        for(int i=0;i<20;i++){
            String input = new String();
            input=sc.nextLine();
            map.put(input, HashFunction(input));
        }
        
        String show = new String();
        show = sc.nextLine();
        
        System.out.println(map.get(show)+" : "+show);
    }
    
}
 

  Java Collection에 존재하는 Hashmap을 이용한다면 보다 쉽게 해시 구조 코드를 설계 할 수 있다.

3. B-tree

  B-tree는 이진트리 구조를 확장하여 하나의 노드에서 가질 수 있는 자식 노드의 개수를 최대 2개 이상 가지는 트리 구조를 의미한다. 그리고 B-tree의 노드 안에 있는 값들은 항상 정렬되어 있어야 한다. 그렇기 때문에 단시간 내에 원하는 자료를 찾기에 매우 유리하다.

 

  B-tree는 각 노드에 데이터가 들어갈 수 있는 크기보다 하나 큰 자식 노드를 생성할 수 있다. 위의 자료에서 최상위 노드에 7과 16 2개의 노드가 존재하는 경우 자식 노드는 총 3개가 나올수 있고, 각 자식 노드는 상위 노드에 있는 숫자에 따라 결정된다. 즉, B-tree가 가지고 있는 가장 큰 특징은 노드가 가지고 있는 데이터의 크게에서 숫자 1개가 항상 많은 자식 노드 포인터를 보유하고 있다는 점이고, 이를 이용해 데이터를 탐색하고 삽입힌다.

  탐색의 경우 최상위 노드부터 숫자를 비교해가면서 아래로 내려가게 된다. 위의 B-tree에서 18이라는 숫자를 찾게 된다면, 최상의 노드의 7, 16과 비교를 수행하고 16보다 크게 되므로 마지막 자식노드로 내려가 18이라는 숫자를 찾는다.

  삽입의 경우 아래와 같은 과정을 거친다.

부적절한 상태에 있는 노드란, 그 노드에 허용된 자식 노드의 숫자가 허용된 범위 밖인 노드를 의미한다.

1. 삽입될 노드가 어느 위치로 삽입될지 찾아 해당 부모 노드에 삽입한다.
2. 부적절한 상태의 노드가 없다면, 삽입 과정을 종료한다.
3. 만약, 어떤 노드가 너무 많은 항목을 가지고 있다면, 이를 두 노드로 분리한다. 이 과정을 반복적으로 트리를 타고 올라가며 진행한다. 만약 루트 노드를 분리하였다면, 새로운 루트 노드를 만든다.

(위키 백과 b-tree 참조)

  B-tree를 활용한 B+ tree도 존재한다. B+ tree는 모든 자료는 최하위 자식 노드에만 위치해있고, 상위 노드의 경우 Key값만을 저장한 경우다. 

  Space-Time trade off는 주로 시간을 빠르게 하기 위해서 많은 공간을 사용하는 알고리즘이다. Radix Sort같은 경우 데이터가 실제로 들어가지 않는 공간이 다소 많지만, 다른 정렬 알고리즘보다 훨씬 빠른 성능을 보유하고 있다. 다음 시간에는 Space-Time trade off 알고리즘의 심화 과정으로 'String Searching Algorithm'을 소개할것이다. 공간을 활용해 문장 내에서 내가 원하는 단어를 찾는 여러 방법에 대해 소개하도록 하겠습니다.