✍️오늘 공부한 내용

• 자료 구조 개념 및 파이썬 코드로 구현해보기
  그래프
  다익스트라 알고리즘
  * 이진 트리
  

📋새로 배우게 된 내용

• 그래프와 트리가 어떻게 다른지 알게 되었다. 트리는 acyclic (순환X) + directed (부모 ->자식/자손 방향으로만)+자식노드 하나 당 부모노드가 하나만 있는 제한적인 그래프인 것!
• 트리를 사용하는 것이 다른 자료구조들보다 유리한 경우가 어떤게 있는 지 알게 되었다.
• 단순히 개념을 공부하는 것보다는 배운 내용들이 어디에 어떻게 쓰이는 지 아는게 중요하다고 생각했는데, 이번 기회를 통해 해시테이블와 대조 시 장점에 대해 알 수 있었다.
  • 시간복잡도를 보면 트리를 사용하면 평균 O(n)이다. 하지만 리스트로 표현하기 어려운 폴더구조나 DOM구조처럼 계층이 있는 경우는 트리를 활용하는 것이 유리하다.
  • 또한 해시같은 경우는 충돌이 발생할 수 있어 메모리의 추가 소비가 필요하지만 트리의 경우 그렇지 않다.
• 다익스트라 알고리즘을 사용할 때 priority queue (우선순위 큐)가 사용된다. 최단거리를 구해야할 떄 지금까지 온 거리가 이전거리보다 짧다면 우선순위 큐에 넣어 weight랑 계산을 하겠지만 그렇지 않는 경우 배제한다. 아직 완벽하게 이해가 안된 거 같아서 다시 봐야겠다

🫥오해했던 점

• Directed graph와 Undirected graph의 개념에 대해 좀 오해했던 점이 상호배타적인 관계라고 생각했다. Directed graph는 무조건 한 방향을 가르키고 edge가 양방향일 가능성을 배제했는데, 사실 Directed graph도 양방향 edge를 가질 수 있다.
• 이진트리랑 이진탐색트리랑 같은 건 줄 알았다. binary tree랑 binary search tree인 건데, binary search tree는 binary tree의 개념보다 더 제한이 있다. 2개의 자식노드를 갖는데다가 오른쪽의 노드의 값보다 왼쪽의 노드의 값들이 항상 커야한다는 조건이 있다. (부모의 값이 항상 자식노드의 값보다 크다)

🤯어려웠던 점

1. 코드를 보면서 어떻게 그래프를 생성하는 지, 어떻게 트리를 생성하는 지에 대한 이해는 됐는데 아직 보지 않고 구현하려면 어렵다.

😸어려움을 해결한 방법

1. 문제 해결이라고 보기는 어렵지만🤔, 아직 개념 정리만 하고 실제 적용을 해보지 않았기 때문에 어렵다. 어려운 점을 파악했으니 앞으로의 공부 방향을 잡은 거 같다.

• 문제를 풀어보고, 풀이들을 보면서 다른 사람들이 어떻게 적용했는지 백준 문제들을 풀어보면서 익숙해지자. 이분탐색때도 처음에는 낯설어서 어려웠지만 점차 익숙해진 거처럼 그래프랑 트리도 처음이니까
• TIL에 넣을 gif 찾던 중 내일 참고할 자료를 우연히 찾은 거 같다! 트리 순회 방법 4가지

🤔아쉬웠던 점

• 어려웠던 점과 비슷하게 적용할 시간이 좀 부족한 날이었다. 내일은 백준에서 문제들을 풀어보면서 개념적용을 해보고 잘 이해했는지 확인하는 시간을 갖아야겠다. 1991번 문제를 풀려고 했는데 전위, 중위, 후위 트리 순회에 대한 공부가 아직 부족한 거 같아서 이쪽도 같이 파봐야겠다. 개념 공부는 했는데 코드로 구현은 아직!

😝느낀점

• 재미있는 건 자료구조들마다 각각 장단점이 있어서 그에 맞게 써야 효율적으로 데이터를 관리할 수 있는 것 같다.
• 트리의 종류에도 몇 개가 있었는데 그중에 어떠한 경우에도 (최악,평균,최적) 검색, 접근, 삽입 삭제가 O(logN)인 AVL tree와 redblack tree가 궁금해졌다.
• 좋은 코드를 짜려면 적절한 자료구조에 적합한 알고리즘을 써야할텐데 위의 두 친구는 어떤 경우에 쓰이는 건지 궁금해졌다.🤔

👊다짐

• 아직 개념정리가 완벽하게 되지는 않았으나 적용을 해보면서 직접 쓰이는 방식에 대해서도 보자! 너무 이론만 보는 것보다는 적용도 자유롭게 되어야 비로소 내꺼라고 할 수 있지 않을까.

🚀오늘의 한줄평

• 어제까지만 해도 트리랑 그래프랑 어떻게 다른 지 몰랐는데 오늘은 어떻게 순회하는 걸 구현할 지 고민하는 내 자신..좀 성장 하는 걸지도😁🤣