딩코딩 : Computer Science 블로그

Prim과 Dijkstra는 모두 그리디 알고리즘 중 하나이다.

Prim은 최소 스패닝 트리를 구하는데 사용되고,

Dijkstra는 한 노드에서 모든 노드로 최단 경로를 구하는데 사용된다.

두 알고리즘은 상당히 유사한데

차이점으로는

Prim은 vertex 집합으로 부터 가까이 있는 노드를 선택하며 vertex 집합을 확장해 나가는 것이고,

Dikstra는 하나의 노드에서 가까이 있는 노드를 선택하며 vertex를 확장한다.

둘다 그리디하게 가까이 있는 노드로 퍼져나가며 최소 스패닝 트리를 구하거나, 최단 경로를 구하는 것이다.

두 알고리즘 모두 우선순위 큐를 사용하면 더 효율적인 알고리즘을 구성할 수 있는데,

연습삼아 우선순위 큐를 사용하지 않고 코드를 작성해봤다.

Prim

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 1, 3, MX, MX},
        {1, 0, 3, 6, MX},
        {3, 3, 0, 4, 2},
        {MX, 6, 4, 0, 5},
        {MX, MX, 2, 5, 0}
};

vector<pair<int, int>> F;

void prim(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int nearest[n + 1], distance[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        nearest[i] = 1;
        distance[i] = W[0][i-1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (distance[i] >= 0 && distance[i] < min) {
                min = distance[i];
                vnear = i;
            }
        }
        e = {vnear, nearest[vnear]};
        F.push_back(e);
        distance[vnear] = -1;

        // 새로 추가된 vnear노드를 포함한 vertex 집합과 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (W[i-1][vnear-1] < distance[i]) {
                distance[i] = W[i-1][vnear-1];
                nearest[i] = vnear;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    prim(5);

    for(auto a : F){
        cout << a.first << ' ' << a.second << '\n';
    }

}

Dijkstra

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 7, 4, 6, 1},
        {MX, 0, MX, MX, MX},
        {MX, 2, 0, 5, MX},
        {MX, 3, MX, 0, MX},
        {MX, MX, MX, 1, 0}
};

vector<pair<int, int>> F;

void dijkstra(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int touch[n + 1], length[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        touch[i] = 1;
        length[i] = W[0][i - 1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //vertex 1번과 가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (length[i] >= 0 && length[i] < min) {
                min = length[i];
                vnear = i;
            }
        }
        e = {vnear, touch[vnear]};
        F.push_back(e);

        // 새로 추가된 vnear노드를 경유하는 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (length[vnear] + W[vnear-1][i-1] < length[i]) {
                length[i] = length[vnear] + W[vnear-1][i-1];
                touch[i] = vnear;
            }
        }
        length[vnear] = -1;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dijkstra(5);

    for (auto a: F) {
        cout << a.first << ' ' << a.second << '\n';
    }

}

InOrder + preOrder 결과나

InOrder + postOrder 결과가 있어야 원본 트리를 복원할 수 있다.

class Tree {
    class Node{
        int data;
        Node left, right;
        Node(int data){
            this.data = data;
        }
    }
    Node root;
    static int pIndex = 0;

    public void buildTreeByInPre(int in[], int pre[]){
        pIndex = 0;
        root = buildTreeByInPre(in, pre, 0, in.length-1);
    }
    private Node buildTreeByInPre(int in[], int pre[], int start, int end){
        if(start > end) return null;
        Node node = new Node(pre[pIndex++]);
        if(start == end) return node;
        int mid = search(in, start, end, node.data);
        node.left = buildTreeByInPre(in, pre, start, mid-1);
        node.right = buildTreeByInPre(in, pre, mid+1, end);
        return node;
    }

    public void buildTreeByInPost(int in[], int post[]){
        pIndex = post.length - 1;
        root = buildTreeByInPost(in ,post, 0, in.length-1);
    }

    private Node buildTreeByInPost(int in[], int post[], int start, int end){
        if(start > end) return null;
        Node node = new Node(post[pIndex--]);
        if(start==end)return node;
        int mid = search(in, start, end, node.data);

        node.right = buildTreeByInPost(in, post, mid+1, end);
        node.left = buildTreeByInPost(in, post, start, mid-1);
        return node;
    }

    private int search(int arr[], int start, int end, int value){
        int i;
        for(i=start; i<=end; i++){
            if(arr[i]==value) return i;
        }
        return i;
    }
    void printInorder(Node node){
        if(node == null) return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }
}

public class Main {
    public static void main(String args[]){
        Tree tree = new Tree();
        int[] pre = {4,2,1,3,6,5,7};
        int[] in = {1,2,3,4,5,6,7};
        int[] post = {1,3,2,5,7,6,4};
        tree.buildTreeByInPre(in, pre);
        tree.printInorder(tree.root);
        System.out.println();
        tree.buildTreeByInPost(in, post);
        tree.printInorder(tree.root);
    }
}

https://www.youtube.com/watch?v=KXolmVUpUQQ 

#include <bits/stdc++.h>
using namespace std;

#define STR_LEN 100

//인 수: 패턴문자열
//반환:lps 배열

int* calculate_lps(char* _pattern_str){
    int pattern_len;
    int* _lps = 0; //LPS 배 열
    int i,j;

    pattern_len = strlen(_pattern_str);

    // LPS 배열
    _lps = (int *)malloc(sizeof(int)* pattern_len);

    // LPS 배열초기화
    memset(_lps, 0 , sizeof(int)*pattern_len);

    /*
     LPS 배열 계산
     */

    j = 0;

    for(int i=1; i<pattern_len; i++){
        if(j>0 && _pattern_str[i]!=_pattern_str[j]){
            j = _lps[j-1];
        }


        if(_pattern_str[i]==_pattern_str[j]){
            j++;
            _lps[i] = j;
        }
    }

    return _lps;
}


int main() {
    int i, j;

    //target string
    char target_str[STR_LEN] = "ABABABABBABABABABCABABABABBABABABABCABABABABBABABABABCABABABABBABABABABC";

    //pattern string
    char pattern_str[STR_LEN] = "ABABABABC";

    int target_len;
    int pattern_len;

    target_len = strlen(target_str);
    pattern_len = strlen(pattern_str);
    int* lps = 0;

    lps = calculate_lps(pattern_str);

    for(i = 0; i< pattern_len; i++){
        cout << i << ' ' << lps[i] << '\n';
    }


    // --- string matching

    printf("------------ start string matching of %s to %s\n", pattern_str, target_str);


    // i : target str의 현재위치 index
    // j : pattern str의 현재위치 index

    j = 0;

    for(i = 0; i< target_len; i++){
        while(j>0 && target_str[i] != pattern_str[j]){
            j = lps[j-1];
        }
        
        if(target_str[i] == pattern_str[j]){
            if(j == (pattern_len - 1)){
                cout << "Found matching at " << i - pattern_len + 1 << '\n';
                j = 0;
            }
            else{
                j++;
            }
        }
    }



    return 0;
}