본문 바로가기
728x90
반응형

Language-LAB/Algorithm14

[알고리즘] 트리 탐색, 그래프 탐색 트리 탐색 알고리즘과 그래프 탐색 알고리즘은 둘 다 특정한 구조를 갖는 자료구조를 탐색하는 알고리즘 하지만 트리와 그래프는 서로 다른 특징과 제약 조건을 가지고 있어서 각각에 맞는 탐색 알고리즘이 존재 이진트리(Binary tree) 이진트리는 모든 노드가 2개의 서브 트리를 갖는 트리 이때 서브 트리는 공집합일 수도 있다 트리 탐색 알고리즘 전위 순회 루트 노드를 먼저 방문한 후, 왼쪽 서브트리를 전위 순회하고 오른쪽 서브트리를 전위 순회하는 방식 노드를 방문하는 순서는 "루트 노드 - 왼쪽 서브트리 - 오른쪽 서브트리" 중위 순회 왼쪽 서브트리를 중위 순회한 후에 현재 노드를 방문하고, 오른쪽 서브트리를 중위 순회하는 방식 노드를 방문하는 순서는 "왼쪽 서브트리 - 루트 노드 - 오른쪽 서브트리" 후.. 2023. 7. 9.
[알고리즘] 이진탐색(Binary Search) 이진탐색 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 중간값을 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식 시간복잡도 : O(logN) 검색이 반복될 때마다 목표값을 찾을 확률이 2배가 돼서 속도가 빠름 정렬된 리스트에만 사용할 수 있다는 단점 2023. 7. 9.
[알고리즘] 선형 탐색(Linear Search) 선형탐색 순차 검색 알고리즘이라고도 부르는 선형 탐색은 찾고자 하는 값을 리스트의 맨 앞부터 차례대로 찾아 나가는 것 시간 복잡도 O(n) 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용가능 검색 길이가 길면 매우 비효율적이다 2023. 7. 9.
[알고리즘] 카운팅 정렬(Counting Sort) 카운팅 정렬 리스트를 한번 스캔하면서 각 항목이 리스트에 몇 번 나타났는 지 빈도수를 계산 빈도수가 구해지면 가장 작은 항목부터 순서대로 빈도수만큼 나열 입력리스트 [14, 11, 12, 12, 15, 12] 입력의 제한과 추가 공간의 크기 기수 정렬과 같이 이 방법에서도 정렬을 위해 항목의 킷값들을 서로 비교하지 않았다. 각 항목의 빈도수를 세었을 뿐 대신 각 항목의 빈도수를 저장할 메모리를 추가 사용 킷값은 0~9 입력리스트[1, 4, 1, 2, 7, 5, 2] 2023. 7. 9.
728x90
반응형

티스토리툴바