728x90 반응형 Data Structure & Algorithm2 정렬 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘정렬 시 고려사항시간 복잡도메모리 사용량안정성: 데이터의 순서가 바뀌지 않는지직렬 vs 병렬종류선택 정렬(Selection Sort)선택된 값과 나머지 데이터 중 비교하여 알맞은 자리를 찾는 알고리즘. 안정성은 보장되지 않음시간 복잡도: O(n^2)worst, average, best 모두 동일삽입 정렬(Insertion Sort)데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳으로 삽입하는 알고리즘성능은 버블 정렬보다 좋음시간 복잡도: O(n^2)worst, average 동일. best 이미 정렬 되어있다면 O(n)버블 정렬(Bubble Sort)인접한 두 수를 비교하여 오름차순 or 내림차순으로 정렬. 안정성 보.. 2025. 1. 25. [알고리즘] 깊이 우선 탐색(DFS, Depth First Search) 깊이 우선 탐색? 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해에 도달하는 데 가장 오랜 시간이 걸림 구현 스택 f.. 2023. 7. 10. 이전 1 다음 728x90 반응형
