📚TIL

day4

이진 탐색

• 정렬되어 있는 요소들을 반 씩 제외하며 찾는 알고리즘으로 O(log n)만큼의 시간 복잡도가 소요됨
• 반드시 정렬되어 있어야 하며 배열과 이진트리를 이용하여 구현 가능
• 이진 탐색 트리 : 이진 탐색을 위한 이진트리이며 루트보다 작은 값은 왼쪽, 큰 값은 오른쪽에 모여있음
• 이진 탐색 트리에서 삭제할 요소가 두개의 서브트리를 가지는 경우엔 왼쪽 서브트리의 가장 큰 값이나 오른쪽 서브트리의 가장 큰 값과 교체
• 이진 탐색 트리는 최악의 경우 편향트리가 될 수 있으며 이 경우 순차 탐색과 동일한 시간 복잡도를 가짐 - AVL트리, 레드-블랙 트리를 이용해 해결

너비우선 탐색(BFS)

• 그래프 탐색 알고리즘이며 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• 큐를 이용하여 구현이 가능하며 시작 지점에서 가까운 정점부터 탐색
• 시간복잡도는 O(V+E) : V - 정점의 수, E - 간선의 수

깊이우선 탐색(Trie)

• 그래프 탐색 알고리즘이며 최대한 깊은 정점부터 탐색하는 알고리즘
• 스택을 이용하여 구현이 가능하며 시작 정점에서 깊은 것부터 탐색
• 시간 복잡도 O(V+E) : V - 정점의 수 , E - 간선의 수

그리디(Greedy)

• 모든 선택에서 그 순간 가장 최적인 답을 선택하는 알고리즘
• 최적해를 보장하지 않지만 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많음
• 크루스칼, 다익스트라 알고리즘 등에 사용
  
  

🌊하루를 마치며

탐색 방법이 정말 다양하다는 생각이 들었다. 몇가지의 탐색법을 배웠는데도 새로 배우는 패턴은 매번 색다른 방식으로 탐색한다. 탐색법은 이론으로 들으면 이해가 잘 되는데 막상 적용해야하는 순간에 어떤 탐색법이 적합할지 떠올릴 수 있을까 걱정이 된다. 정리를 해놓고 많이 보면서 익혀야 할 것 같다.

내일은 실습을 최대한 해결하할 예정이다. 화이띵 ! ! !