자료구조 (Data Structures) (23) 썸네일형 리스트형 [Graph] 순회, Traversal https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 순회 (Traversal) 그래프의 모든 정점을 방문하는 체계적인 방법 - 깊이 우선 탐색 (DFS, Depth First Traversal) DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문하며 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아.. [Graph] 그래프, Graph https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 그래프 (Graph) 정점(Vertex)과 간선(Edge)의 쌍, G = (V, E) 하나의 간선은 두 개의 정점 사이를 연결하는 정점의 쌍 Undirected edge : 정점의 쌍에 순서가 없는 경우, 즉 (u, v) == (v, u) Directed edge : 정점의 쌍에 순서가 있는 경우, 즉 (u, .. [Sorting] 퀵 정렬, Quick Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 퀵 정렬 (Quick Sort) 입력의 맨 왼쪽 원소 혹은 맨 오른쪽 원소(피벗, Pivot)를 기준으로 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 피벗보다 작은 부분과 피벗보다 큰 부분을 각각 재귀적으로 정렬하는 알고리즘 - 수행 시간 최선 경우가 O(nlog(n)), 평균 경우가 O.. [Sorting] 합병 정렬, Merge Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 합병 정렬 (Merge Sort) 크기가 n인 입력을 1/2n 크기로 분할하고, 각각에 대해 재귀적으로 합병 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병하는 정렬 알고리즘 수행 과정에서 임시로 합병된 결과를 저장하기 위해 입력 리스트 a와 같은 크기의 보조 리스트가 필요 - 반복 합병 정렬 (Iterat.. [Sorting] 힙 정렬, Heap Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 힙 정렬 (Heap Sort) 최대 힙을 이용하여 루트를 힙의 가장 마지막 노드와 교환한 후 힙 크기를 1 감소시키고, 루트로부터 Downheap 연산을 통해 힙 속성을 복원하는 과정을 반복하여 정렬하는 알고리즘 - 수행 시간 먼저 상향식(Bottom-up)으로 힙을 구성하는 데 O(n) 소요 루트와 힙의 마지.. [Sorting] 쉘 정렬, Shell Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 쉘 정렬 (Shell Sort) 삽입 정렬을 이용하여 작은 값을 가진 원소들을 리스트의 앞부분으로 옮기며 큰 값을 가진 원소들이 리스트의 뒷부분에 자리 잡도록 만드는 과정을 반복하여 정렬하는 알고리즘 삽입 정렬에 전처리 과정을 추가한 것 전처리 과정은 삽입 정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원.. [Sorting] 삽입 정렬, Insertion Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 삽입 정렬 (Insertion Sort) 리스트가 정렬된 부분과 정렬되지 않은 부분으로 나뉘며, 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하는 방식의 정렬 알고리즘 리스트의 첫번째 원소를 현재 원소로 지정하여 정렬을 시작하고, 리스트의 마지막 원소를 이미 정렬되어 있는 앞부분에 삽입했을 때 정렬.. [Sorting] 선택 정렬, Selection Sort https://github.com/cuttingworms/Data-Structures-with-Python GitHub - cuttingworms/Data-Structures-with-Python Contribute to cuttingworms/Data-Structures-with-Python development by creating an account on GitHub. github.com - 선택 정렬 (Selection Sort) 리스트에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 선택하여 정렬되지 않은 부분의 가장 왼쪽의 원소와 교환하는 정렬 알고리즘 리스트의 앞쪽 부분은 정렬, 나머지 부분은 정렬이 되지 않은 상태로 마지막 한 개의 원소가 남을 때까지 반복적으로 수행 - 수행 시간 처.. 이전 1 2 3 다음
