본문 바로가기
반응형

이진 탐색2

Binary Tree Traversal, DFS, BFS [ Binary Tree Traversal ] 트리를 순회하는 방법을 "Binary Tree Traversal"이라고 한다. 어떻게 하면 트리의 맨 아래에 있는 가지를 전부 둘러보면서 조회를 할 수 있을까를 방법론으로 만든 것이다. 방법은 3가지가 있다. InOrder, PreOrder 그리고 PostOrder이다. InOrder는 (LVR : Left, Root, Right)라고 하며 왼쪽, 가운데 그리고 오른쪽을 차례대로 순회한다. PreOrder는 (VLR : Root, Left, Right)라고 하며 가운데, 왼쪽 그리고 오른쪽을 차례대로 순회한다. 마지막으로 PostOrder는 (LRV : Left, Right, Root)라고 하며 왼쪽, 오른쪽 그리고 가운데를 차례대로 순회한다. (1) InO.. 2021. 4. 25.
Binary Search Algorithm [ 이진 탐색 알고리즘 ] 이진 탐색 알고리즘(Binary Search Algorithm)은 리스트에 존재하는 특정 값을 찾기 위해서 리스트의 범위를 절반씩 좁혀가며 찾는 알고리즘이다. 처음부터 끝까지 값을 비교하는 순차 탐색에 비해 이진 탐색 알고리즘은 속도가 월등하게 빠르다. 이진 탐색은 시작, 끝 그리고 중간에 있는 데이터의 인덱스를 통해 범위를 줄이고 비교대상을 찾는다. 다만 이진 탐색 알고리즘을 사용할 때는 리스트 안의 값들이 이미 정렬이 되어 있어야 한다. 정렬이 되어 있지 않은 리스트에서는 이진 탐색 알고리즘을 사용할 수 없다. 그러므로 Mege Sort나 Quick Sort 등을 사용해서 리스트를 먼저 정리하고 이진 탐색을 사용해야 하는 것이다. 정렬이 완료된 리스트에서 범위를 절반을 나누.. 2021. 4. 12.
반응형

티스토리툴바