(TIL) 20210603

1.Facts(한 것)

---

• 학교 과제 완성 및 제출
• 알고리즘 복습
• 운동하기
• C++, 자바스크립트로 프로그래머스 문제 풀기

2.Findings(배운 것)

---

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000

typedef struct GraphType {
    int n;
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int distance[MAX_VERTICES];
int found[MAX_VERTICES];

int choose(int distance[], int n, int found[]) {
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for(i = 0; i < n; i++) {
        if(distance[i] < min && !found[i]) {
            min = distance[i];
            minpos = i;
        }
    }
    return minpos;
}

void print_status(GraphType* g) {
    static int step = 1;
    printf("STEP %d: ", step++);
    printf("distance: ");
    for(int i = 0; i < g->n; i++) {
        if(distance[i] == INF) {
            printf(" * ");
        }
        else {
            printf("%2d ", distance[i]);
        }
    }
    printf("\n");
    printf("        found:      ");
    for(int i = 0; i < g->n; i++) {
        printf("%2d ", found[i]);
    }
    printf("\n\n");
}

void shortest_path(GraphType* g, int start) {
    int u, w;
    for(int i = 0; i<g->n; i++) {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
    }
    for(int i = 0; i < g->n; i++) {
        print_status(g);
        u = choose(distance, g->n, found);
        found[i] = TRUE;
        for(w = 0; w<g->n; w++) {
            if(!found[w])
                if(distance[u] + g->weight[u][w]<distance[w])
                    distance[w] = distance[u] + g->weight[u][w];
        }
    }
}

 

위 코드는 다익스트라 알고리즘을 C로 구현한 코드이다.

다익스트라 알고리즘은 방향이 있는 그래프(directed graph)에서 사용하는 알고리즘으로

s 에서 t까지 가는 가장 빠른(가장 비용이 적은) 길을 찾는 알고리즘이다. 

다익스트라 알고리즘의 시간복잡도는 주 반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n^2)의 복잡도를 가진다.

 

 

3.Feeling(느낀 점)

---

뭐든지 꾸준히 해야한다.

공부도 그렇고 운동도 그렇고.

 

4.Affirmation(자기 선언)

---

• 日日新又日新