(TIL) 20210604

1.Facts(한 것)

---

• 학교 과제 완성 
• DFS 재귀, 스택으로 구현하기
• 다익스트라 C++로 구현하기
• Bellman-Ford algorithm 공부
• 운동하기

2.Findings(배운 것)

---

다익스트라 알고리즘을 깊이 있게 공부했다.

다익스트라 알고리즘은 간선의 값을 가중해서 최단 경로를 구하는 알고리즘으로

dist[] 배열과, from[]배열을 통해서 시작점 부터 각 노드까지 필요한 비용을 알 수 있음과 동시에

각 노드가 어떤 노드를 거쳐서 왔는지까지 알 수 있다.

다익스트라 알고리즘의 시간복잡도는 O(E*V)이고

바이너리 힙으로 구현할 경우 삽입, 삭제, 키를 업데이트 하는데 비용이 평균적으로 E*logV 만큼 필요하다.

 

DFS를 C++로 재귀적방식, 스택을 이용한 방식 두가지로 구현을 해봤다.

코드는 재귀코드가 훨씬 짧아서 좋다

 

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>

using namespace std;

void dfs(vector<int> graph[], int start, bool check[]) {
    check[start] = true;
    cout << start << ' ';
    for (int i = 0; i < graph[start].size(); i++) {
        int next_node = graph[start][i];
        if (!check[next_node]) {
            dfs(graph, next_node, check);
        }
    }
}

int main() {
    vector<int> g[] = {{}, {2,3,8}, {1,7}, {1, 4, 5}, {3, 5}, {3,4}, {7}, {2, 6, 8}, {1, 7}};
    bool visited[9] = {false};
    dfs(g, 1, visited);
}

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(vector<int> graph[], int start, bool check[]) {
    stack<int> st;
    st.push(start);
   
    while(!st.empty()) {
        int cur = st.top();
        st.pop();
       
        if(check[cur]) continue;
        check[cur] = true;
        cout << cur << ' ';
        for(int i = graph[cur].size()-1; i >= 0; i--) {
            int next = graph[cur][i];
            if(!check[next]) {
                st.push(next);
            }
        }
    }
}

int main() {
    vector<int> g[] = {{}, {2,3,8}, {1,7}, {1, 4, 5}, {3, 5}, {3,4}, {7}, {2, 6, 8}, {1, 7}};
    bool visited[9] = {false};
    dfs(g, 1, visited);
}

 

 

위 코드는 스택을 이용한 DFS 코드이다.

 

3.Feeling(느낀 점)

---

알고리즘만 확실하게 익히면 문제를 푸는건 수월할 것 같다.

상대적으로 부족한 트리와 그래프 관련해서 심도있는 공부가 필요하다.

 

4.Affirmation(자기 선언)

---

• 日日新又日新

 

5. 여담

---

 운동을 2주 넘게 쉬다가 다시 가니 몸이 내 맘대로 움직이질 않는다.

무게가 줄은건 default이고, 종목을 3개이상 가져가질 못한다.

시간을 만들어서 가야겠다.