[알고리즘] 작업 스케줄링 알고리즘(JobScheduling) & 허프만 압축(Huffman)

* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요.

 

 

 

 

작업 스케줄링이란?

 

 

알고리즘 문제를 풀다보면 시작 시간과 종료 시간이 지정된 어떠한 작업들을 수행하는 문제에 마주칠 때가 있다. 이때 문제를 해결하기 위해서 정렬이나 맵 같은 자료구조를 쓰면 될 것 같은데.. 막상 구현해보면 쉽지 않을 것이다.

 

 

 

 

따라서 이러한 문제 유형에 대해서는 어느정도 틀을 가지고 푸는 것이 좋다. 지금까지 내가 본 바로는 결국 그 틀 내에서 크게 벗어나지 않기 때문이다.

 

 

 

 

그래서 작업 스케줄링이 무엇인가 하면, 모든 작업을 수행하는 문제이다. 물론 그냥 수행하는 것이 아니라 해당 작업들의 수행 시간이 뒤죽박죽 섞이지 않고 최소한으로 기계를 사용해야 한다. 기계가 아니어도 강의실 배치, 컴퓨터 등 작업을 수행할 수 있는 수행 주체면 모두 가능하다.

 

 

 

 

다시말해, 작업 스케줄링은 각 작업에 시작시간, 종료 시간이 존재할때 최소한의 기계(강의실, 컴퓨터...)를 사용하여 모든 작업을 수행하는 것이다.

 

 

 

자 이제, 작업 스케줄링이 무슨 알고리즘인지는 대충 알겠고, 어떻게 해야 최적의 해를 보장할 수 있을 지 생각해야 한다. 여기서 말하는 최적의 해란, 최소한의 기계로 모든 작업을 수행할 수 있음을 말한다.

 

 

 

그러한 방법으로는 크게 네 가지 정도가 있다.

 

1️⃣ 빠른 시작시간 작업 우선(Earliest start time first) 배정

 

2️⃣ 빠른 종료시간 작업 우선(Earliest finish time first) 배정

 

3️⃣ 짧은 작업 우선(Shortest job first) 배정

 

4️⃣ 긴 작업 우선(Longest job first) 배정

 

 

이 중에서 가장 많이 사용하는 것은 1번의 경우이다. 최적해를 완전하게 보장하는 알고리즘이 1번밖에 없기 때문이다. 물론 상황에 따라서 최적해를 보장하지 않더라도 사용해야만 하는 때도 있긴 할 것이지만 자주 사용하지는 않는다.

 

 

 

 

 

 

 

 

 

 

 

 

작업 스케줄링의 수도 코드(Pseudo Code)

 

 

 

 

다음으로 살펴볼 것은 의사 코드이다. 그 로직만 충분히 파악하고 있다면 어떠한 언어라도 쉽게 적용할 수 있을 것이다.

 

입력 : n 개의 작업(t1 ~ tn)
출력 : 각 기계에 배정된 작업 순서

시작 시간으로 정렬한 작업 리스트: L(오름 차순 정렬)
whlie L이 비어있지 않다면
    L에서 가장 이른 시작 시간 작업 ti를 가져온다.
    if ti를 수행할 수 있는 기계가 있다면
        ti를 수행할 수 있는 기계에 배정한다.
    else
        새 기계에 ti를 배정한다.
    ti를 L에서 제거한다.
return 각 기계에 배정된 작업 순서

 

 

 

 

작업들을 정렬하고, 각 작업 시간대를 처리할 수 있는 최소한의 기계를 찾아 배정하는 것. 그것이 전부이긴 하다. 이 때문에 시간 복잡도도 정렬 시간 O(nlogn)에 기계를 찾고 while문으로 작업을 배정하는 과정인 O(mn)을 더한 값이다.(O(nlogn) + O(mn)

 

 

아래는 작업 스케줄링의 수도 코드를 Java로 구현한 예시이다. 수도 코드를 실제 코드를 구현하는 과정도 봐둬야 나중에 덜 힘들 수 있다. 한 번씩 살펴보자.

 

📝 작업 스케줄링 코드 예시(Java)

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Job {
    int id;
    int startTime;
    int endTime;

    public Job(int id, int startTime, int endTime) {
        this.id = id;
        this.startTime = startTime;
        this.endTime = endTime;
    }
}

public class JobScheduling {

    public static List<List<Job>> scheduleJobs(List<Job> jobs) {
        Collections.sort(jobs, Comparator.comparingInt(job -> job.startTime));

        int numMachines = 1;
        List<List<Job>> machineSchedule = new ArrayList<>();
        machineSchedule.add(new ArrayList<>(Arrays.asList(jobs.get(0))));

        for (int i = 1; i < jobs.size(); i++) {
            Job currentJob = jobs.get(i);
            boolean assigned = false;

            for (int j = 0; j < numMachines; j++) {
                List<Job> machine = machineSchedule.get(j);
                Job lastJob = machine.get(machine.size() - 1);

                if (currentJob.startTime >= lastJob.endTime) {
                    machine.add(currentJob);
                    assigned = true;
                    break;
                }
            }

            if (!assigned) {
                List<Job> newMachine = new ArrayList<>(Arrays.asList(currentJob));
                machineSchedule.add(newMachine);
                numMachines++;
            }
        }

        return machineSchedule;
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>();
        jobs.add(new Job(1, 7, 8));
        jobs.add(new Job(2, 3, 7));
        jobs.add(new Job(3, 1, 5));
        jobs.add(new Job(4, 5, 9));
        jobs.add(new Job(5, 0, 2));
        jobs.add(new Job(6, 6, 8));
        jobs.add(new Job(7, 1, 6));

        List<List<Job>> machineSchedule = scheduleJobs(jobs);

        for (int i = 0; i < machineSchedule.size(); i++) {
            System.out.println("Machine " + (i + 1));
            for (Job job : machineSchedule.get(i)) {
                System.out.println("Job " + job.id + " ("+job.startTime + "," + job.endTime + ")");
            }
        }
    }
}

 

 

🔲 class Job은 시작 시간, 종료 시간, id 값을 가진다.

 

 

🔲 Comparator를 통해서 시작 시간을 기준으로 오름차순 정렬한다.

 

 

🔲 현재 Job(currentJob)이 기존에 가지고 있는 machine들로 처리가 가능한 지 알아본다. 이 때 시간대가 겹치는 지의 여부에 따라 가능한지 아닌지 확인할 수 있다. 결국에는 중복이 없어야 한다는 것이 이 작업 스케줄링의 목적이기 때문이다.

 

 

🔲 만약 현재 가지고 있는 machine들로 처리가 불가능하다면, 새로운 newMachine을 만들어서 처리해야 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

허프만 코딩(HuffmanCoding)

 

 

우리는 항상 빠른 시간, 그리고 좋은 효율을 추구한다. 이는 설령 파일을 누군가에게 전송한다고 할 때도 마찬가지로 적용된다. 만약 전송하고자 하는 파일의 크기를 줄일 수 있다면 메모리 공간을 효율적으로 사용할 수 있으며, 파일 전송 시간도 굉장히 짧아질 것이다.

 

 

 

이를 위한 "파일 압축"의 기법에 있어서는 다양한 방법들이 있지만, 우리는 알고리즘적으로 접근하기 쉬운 "허프만 압축"에 대하여 알아보자.

 

 

 

"허프만 압축"의 큰 특징 중 하나는 접두부 특성이라는 것이다. 허프만 압축 기법이 아닌 다른 압축 기법은 코드와 코드 사이를 구분 짓기 위해 특별한 문자를 사용한다. 예를 들어 101#10#1#111 등 #을 사용하여 각 코드를 구분 지었다. 이와 달리 허프만 코드는 각 문자에 할당된 이진 코드가 다른 문자의 할당된 이진 코드의 접두부가 되지 않는다.

 

 

 

 

즉, 허프만 압축에 있어서는 #과 같이 구분을 위한 문자의 필요가 없다. 그렇기 때문에 파일의 압축과 해제에 있어서도 별다른 코드가 필요하지 않다.

 

 

 

 

그렇다면 허프만 압축은 어떠한 방식으로 압축을 하는 것일까? 여기에 있어서는 각 문자의 빈도 수에 기반을 둔 이진 트리를 만들어 각 문자에 이진 코드를 할당하는 방법을 사용한다. 이렇게 만들어진 이진 코드를 허프만 코드라고 한다.

 

 

 

 

 

 

 

 

 

 

 

허프만 코딩(HuffmanCoding)의 수도 코드(Pseudo code)

 

 

입력 : 입력 파일 n개의 문자에 대한 각각의 빈도 수
출력 : 허프만 트리


각 문자 당 노드를 만들고, 그 문자의 빈도 수를 노드에 저장한다.
n 노드의 빈도 수에 대해 우선 순위 큐를 만든다.

while Q에 있는 노드 수 >= 2
    빈도 수가 가장 적은 2개의 노드(A와 B)를 Q에서 제거한다.
    새 노드 N을 만들고, A와 B를 N의 자식노드로 만든다.
    N의 빈도 수 = A의 빈도 수  + B의 빈도 수
    노드 N을 Q에 삽입한다.

return Q

 

 

 

🔲 우선 순위 큐를 왜 만드는 가?

 

빈도 수에 대한 정렬을 하여야 효율적인 허프만 코드를 만들 수 있다. 예를 들어 A라는 문자가 B라는 문자보다 빈도 수가 많다고 할 때, 이에 대한 허프만 코드를 "1010"으로 저장하는 것보단 "10"으로 저장하는 것이 훨씬 좋다.

 

즉, 정렬은 효율적인 허프만 코드를 만드는데 있어 필수적인 요소이므로 우선순위 큐를 사용한다.

 

 

 

 

아래는 허프만 코딩을 Java로 구현한 예시이다. 위의 로직이 어느 부분에서 사용되는 지 살펴보자.

 

 

📝 허프만 코드 예시(Java)

 

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Arrays;

class Entry {
    private int frequency;  // 빈도
    private String word;    // 문자 또는 단어
    private Entry left;     // 왼쪽 자식 노드
    private Entry right;    // 오른쪽 자식 노드
    private String code;    // Huffman 코드

    public Entry(int newFreq, String newValue, Entry l, Entry r, String s) {
        frequency = newFreq;
        word = newValue;
        left = l;
        right = r;
        code = s;
    }

    public int getKey() {
        return frequency;
    }

    public String getValue() {
        return word;
    }

    public String getCode() {
        return code;
    }

    public Entry getLeft() {
        return left;
    }

    public Entry getRight() {
        return right;
    }

    public void setCode(String newCode) {
        code = newCode;
    }
}


public class Huffman {
    private static Entry[] minHeap;
    private static int size;

    public Huffman(Entry[] entries, int n) {
        minHeap = new Entry[n + 1];
        size = 0;

        for (int i = 1; i <= n; i++) {
            minHeap[++size] = entries[i];
        }

    }

    public void createHeap() {
        // 최소 힙으로 변환
        for (int i = size / 2; i >= 1; i--) {
            minHeapify(i);
        }


    }

    public Entry createTree() {
        while (size >= 2) {
            Entry a = extractMin();
            Entry b = extractMin();

            Entry n = new Entry(a.getKey() + b.getKey(), "", a, b, "");

            insert(n);
        }

        return minHeap[1];
    }

    private void minHeapify(int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int smallest = i;

        if (left <= size && minHeap[left].getKey() < minHeap[i].getKey()) {
            smallest = left;
        }

        if (right <= size && minHeap[right].getKey() < minHeap[smallest].getKey()) {
            smallest = right;
        }

        if (smallest != i) {
            swap(i, smallest);
            minHeapify(smallest);
        }
    }

    private Entry extractMin() {
        if (size < 1) {
            return null;
        }
        Entry min = minHeap[1];
        minHeap[1] = minHeap[size--];
        minHeapify(1);
        return min;
    }

    private void insert(Entry entry) {
        if (size >= minHeap.length - 1) {
            minHeap = Arrays.copyOf(minHeap, minHeap.length * 2);
        }
        minHeap[++size] = entry;

        int i = size;
        while (i > 1 && minHeap[i].getKey() < minHeap[i / 2].getKey()) {
            swap(i, i / 2);
            i = i / 2;
        }
    }

    private void swap(int i, int j) {
        Entry temp = minHeap[i];
        minHeap[i] = minHeap[j];
        minHeap[j] = temp;
    }

    public void preorder(Entry root) {
        if (root != null) {
            if (!root.getValue().isEmpty()) {
                System.out.print(root.getValue() + ": " + root.getCode() + " ");
            }
            preorder(root.getLeft());
            preorder(root.getRight());
        }
    }

    public static void print() {
        for (int i = 1; i <= size; i++) {
            System.out.print("[" + minHeap[i].getKey() + " " + minHeap[i].getValue() + "] ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Entry[] a = new Entry[7];
        a[1] = new Entry(60, "a", null, null, null);
        a[2] = new Entry(20, "b", null, null, null);
        a[3] = new Entry(30, "c", null, null, null);
        a[4] = new Entry(35, "d", null, null, null);
        a[5] = new Entry(40, "e", null, null, null);
        a[6] = new Entry(90, "f", null, null, null);

        Huffman h = new Huffman(a, 6);
        System.out.println("최소 힙 만들기 전");
        print();

        h.createHeap();
        System.out.println("최소 힙:");
        print();

        System.out.println("허프만 코드:");

        Entry root = h.createTree();
        h.generateHuffmanCodes(root, "");
        h.preorder(root);
        System.out.println();
    }

    public void generateHuffmanCodes(Entry root, String code) {
        if (root != null) {
            root.setCode(code);

            generateHuffmanCodes(root.getLeft(), code + "0");
            generateHuffmanCodes(root.getRight(), code + "1");
        }
    }
}

 

 

🔲 Entry 클래스는 Huffman Tree의 노드를 나타낸다.

 

🔲 Entry는 단어, 단어의 빈도수, 왼쪽 자식, 오른쪽 자식에 대한 정보를 가진다.

 

🔲 앞선 설명에서는 우선 순위 큐를 통해서 최소 값을 찾는다고 하였지만, 해당 예제에서는 최소 힙을 사용하였다.

 

🔲 minHeapfy 메서드를 통해서 자기 자신 노드와 왼쪽, 오른쪽 자식에 대해 최소 값을 찾아 상위 노드로 지정한다.

 

🔲 extractMin 메서드는 최소 값을 뽑는 함수이다. 

 

🔲 createTree 메서드에서 두개의 최소 값 노드를 제거하고, 새 노드를 만들어 삽입한다.

 

 

 

 

 

 

🔲  generateHuffmancodes를 통해서 허프만 코드를 얻을 수 있다. 루트 노드로 부터 재귀적으로 탐색해 나가며, 코드를 붙일 수 있으며 마지막 단말노드에서 획득하는 코드가 각 문자의 허프만 코드임을 알 수 있다.