728x90 반응형 알고리즘6 [알고리즘] 트리 탐색, 그래프 탐색 트리 탐색 알고리즘과 그래프 탐색 알고리즘은 둘 다 특정한 구조를 갖는 자료구조를 탐색하는 알고리즘 하지만 트리와 그래프는 서로 다른 특징과 제약 조건을 가지고 있어서 각각에 맞는 탐색 알고리즘이 존재 이진트리(Binary tree) 이진트리는 모든 노드가 2개의 서브 트리를 갖는 트리 이때 서브 트리는 공집합일 수도 있다 트리 탐색 알고리즘 전위 순회 루트 노드를 먼저 방문한 후, 왼쪽 서브트리를 전위 순회하고 오른쪽 서브트리를 전위 순회하는 방식 노드를 방문하는 순서는 "루트 노드 - 왼쪽 서브트리 - 오른쪽 서브트리" 중위 순회 왼쪽 서브트리를 중위 순회한 후에 현재 노드를 방문하고, 오른쪽 서브트리를 중위 순회하는 방식 노드를 방문하는 순서는 "왼쪽 서브트리 - 루트 노드 - 오른쪽 서브트리" 후.. 2023. 7. 9. [알고리즘] 이진탐색(Binary Search) 이진탐색 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 중간값을 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식 시간복잡도 : O(logN) 검색이 반복될 때마다 목표값을 찾을 확률이 2배가 돼서 속도가 빠름 정렬된 리스트에만 사용할 수 있다는 단점 2023. 7. 9. [알고리즘] 선형 탐색(Linear Search) 선형탐색 순차 검색 알고리즘이라고도 부르는 선형 탐색은 찾고자 하는 값을 리스트의 맨 앞부터 차례대로 찾아 나가는 것 시간 복잡도 O(n) 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용가능 검색 길이가 길면 매우 비효율적이다 2023. 7. 9. [알고리즘] 퀵정렬(Quick Sort) 퀵 정렬 1. 분할(divide) : 먼저 피벗(pivot)을 선택한다. 편의상 리스트이 첫 번째 항목을 사용 피벗보다 작은 항목들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 항목들은 모두 피벗의 오른쪽으로 옮긴다 2.정복(Conquer) : 분할이 끝나면 피벗은 최종 위치에 있지만 왼쪽과 오른쪽 부분 리스트는 아직 정렬 미완성 분할 정복 전략을 다시 사용한다 만약 리스트의 크기가 1이면 이미 정복된 것! 3. 결합(Combine, merge) : 병합단계는 필요 없는 데 분할 할 때마다 피벗 중심으로 부분리스트로 정렬되기 때문이다. 분할과 정복이 모두 끝나면 그 자체가 이미 정렬 완료된 상태 2023. 7. 9. 이전 1 2 다음 728x90 반응형
