(TIL) 20210605

1.Facts(한 것)

---

• 학교 과제 녹음
• 알고리즘 과제 제출
• 자료구조 트리, 그래프 포스팅 및 정리
• 알고리즘 복습
• 운동하기

2.Findings(배운 것)

---

DFS와 BFS를 트리에서 구현했다.

 

DFS와 BFS를 그래프에서 실행하는 것과 트리에서 실행하는 것에 가장 큰 차이점은

트리에서는 어떤 방향으로 나아갈지 설정을 해줘야하지만

그래프에서는 순서를 정해줄 필요가 없다.

그래프는 인접해 있는 모든 노드를 탐색하기 때문이다.

 

아래는 트리를 이용한 DFS와 BFS이다.

 

void dfs(vector<int> tree, bool check[]) {
    stack<int> st;
    int start = tree[0];
    st.push(start);
    
    while(!st.empty()) {
        int cur = st.top();
        st.pop();
        int curIdx = (int)(find(tree.begin(), tree.end(), cur) - tree.begin());
        if(!check[cur]) {
            check[cur] = true;
            cout << cur << ' ';
        }
        
        int rightIdx = curIdx * 2 + 2;
        int leftIdx = curIdx * 2 + 1;
        
        if(rightIdx < tree.size()) {
            int right = tree[rightIdx];
            if(right) {
                st.push(right);
            }
        }
        
        if(leftIdx < tree.size()) {
            int left = tree[leftIdx];
            if(left) {
                st.push(left);
            }
        }
    }
}

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

 

void bfs(vector<int> tree, bool check[]) {
    queue<int> q;
    int start = tree[0];
    q.push(start);
    
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        int curIdx = (int)(find(tree.begin(), tree.end(), cur) - tree.begin());
        if(!check[cur]) {
            check[cur] = true;
            cout << cur << ' ';
        }
        
        int rightIdx = curIdx * 2 + 2;
        int leftIdx = curIdx * 2 + 1;
        
     
        if(leftIdx < tree.size()) {
            int left = tree[leftIdx];
            if(left) {
                q.push(left);
            }
        }
        
        if(rightIdx < tree.size()) {
            int right = tree[rightIdx];
            if(right) {
                q.push(right);
            }
        }
        
    }
}

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

이제는 트리와 그래프 관련한 문제를 한결 쉽게 풀 수 있을 것 같다.

 

중국어를 많이 쓸일이 없다보니, 실력에 녹이 조금 슬었다.

1-2년 전만해도, 영화 대본을 보고 읽을떄 크게 무리가 없었는데

이제는 내 발음에 의심이 생긴다.

부단히 노력해야겠다.

 

3.Feeling(느낀 점)

---

머리로 이해한것과 실제로 해보는 것은 많이 다르다.

자그만한 것이라도 많은 연습이 필요하다.

4.Affirmation(자기 선언)

---

• 日日新又日新

 

5. 여담

---

운동을 다시 시작한 결과

걸음을 걸을 떄 마다 다리가 아파온다.

내일은 가슴이 찢어지도록 아프겠지....