1.Facts(한 것) 학교 과제 녹음 알고리즘 과제 제출 자료구조 트리, 그래프 포스팅 및 정리 알고리즘 복습 운동하기 2.Findings(배운 것) DFS와 BFS를 트리에서 구현했다. DFS와 BFS를 그래프에서 실행하는 것과 트리에서 실행하는 것에 가장 큰 차이점은 트리에서는 어떤 방향으로 나아갈지 설정을 해줘야하지만 그래프에서는 순서를 정해줄 필요가 없다. 그래프는 인접해 있는 모든 노드를 탐색하기 때문이다. 아래는 트리를 이용한 DFS와 BFS이다. void dfs(vector tree, bool check[]) { stack st; int start = tree[0]; st.push(start); while(!st.empty()) { int cur = st.top(); st.pop(); in..

1.Facts(한 것) 학교 과제 완성 DFS 재귀, 스택으로 구현하기 다익스트라 C++로 구현하기 Bellman-Ford algorithm 공부 운동하기 2.Findings(배운 것) 다익스트라 알고리즘을 깊이 있게 공부했다. 다익스트라 알고리즘은 간선의 값을 가중해서 최단 경로를 구하는 알고리즘으로 dist[] 배열과, from[]배열을 통해서 시작점 부터 각 노드까지 필요한 비용을 알 수 있음과 동시에 각 노드가 어떤 노드를 거쳐서 왔는지까지 알 수 있다. 다익스트라 알고리즘의 시간복잡도는 O(E*V)이고 바이너리 힙으로 구현할 경우 삽입, 삭제, 키를 업데이트 하는데 비용이 평균적으로 E*logV 만큼 필요하다. DFS를 C++로 재귀적방식, 스택을 이용한 방식 두가지로 구현을 해봤다. 코드는 재..