코드스테이츠 25일차

안형준·2022년 5월 30일
0

코드스테이츠

목록 보기
25/32
post-thumbnail

오늘의 학습목표 및 질문 키워드

이진 트리와 BST 이외에 어떠한 트리가 있을까요?
균형 이진 탐색 트리란 무엇일까요?
DFS와 BFS의 장단점은 또 무엇이 있을까요?
그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요?
반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요?

👻Tree traversal
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
트리를 순회하는 방법에는 크게 3가지로 나눌 수 있는데, 전위 순회, 중위 순회, 후위 순회이다.

전위 순회
[루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회

중위 순회
[왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회

후위 순회
[왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회

👻BFS / DFS
너비 우선 탐색 (BFS, Breadth-First Search)
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
주로 두 정점 사이의 최단 경로를 찾을 때 사용
큐를 이용해서 구현

깊이 우선 탐색 (DFS, Depth-First Search)
최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.
스택 또는 재귀함수로 구현

오늘은 트리를 순회, 탐색하는 방법에 대해 학습했고 Tree, Graph와 관련된 알고리즘 문제를 풀어보았다.
원래는 그 이후 문제들을 풀었어야 했지만 앞에서의 개념이 조금씩 흔들리고 있다는 생각이 들어 페어분과 합의하에 Tree, Graph, Binary Search Tree 구현 문제들을 해결했다.
문제의 양이 많지는 않았지만 그것들을 해결하는데에 정말 많은 노력을 기울였다.
그렇게 만족스럽게 구현 문제들은 끝마쳤고, 이제 그 이후 내용들에 대한 문제들을 따로 풀어보려고 한다.
저번 스트림, 재귀에 이어 오늘은 너무나도 절망적인 날이였고, 내가 정말 잘할 수 있을까란 생각이 또 다시 들었다.
하지만 이대로 포기한다면 난 어디가서든 끝까지 해내는 사람이 될 수 없을 것이다.
그렇기에 더욱 열을 내서 복습에 심혈을 기울일 생각이다.
오늘도 정말 고생했고 내일도 파이팅!

profile
개발 공부

0개의 댓글