python4 [알고리즘] 깊이 우선 탐색(DFS) - Python 깊이 우선 탐색 Depth-First Search깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드에서 시작해 여러개의 다음 노드로 펼쳐 나간 방식과 달리 한 노드에서 다음 하나의 노드로 들어가는 방향을 말합니다. 미로찾기의 예시를 떠올리면 DFS의 탐색 방향을 이해하기 쉽습니다.아래 그림1을 보겠습니다. DFS로 그래프를 탐색하면, 아래 그림의 보라색 경로와 같이 탐색하게 됩니다. S1에서 출발하여 a,b,c,d만 순회하고 끝이 납니다. 하지만 c와 f가 남았으므로 S3에서 다시 탐색을 시작합니다. 그리고 c에서 e와 f중 아직 방문하지 않은 f노드를 탐색함으로써 DFS가 끝.. 2023. 11. 10. [알고리즘] 퀵 정렬 (Quick Sort) - Python 1. 퀵 정렬의 원리 퀵 정렬은 Divide and Conquer 방식을 따릅니다.Divide 단계에서는 Partition 방식을 통해 "pivot"을 기준으로 두개의 array로 나눕니다. 그 다음, pivot보다 작은 원소는 pivot 기준 왼쪽에 위치하도록, pivot보다 큰 원소는 오른쪽에 위치하도록 합니다.Conquer 단계에서는 재귀적으로 두개의 subarrays를 정렬합니다. 퀵 정렬의 Partition 단계에는 대표적으로 Hoare 방식과 Lomuto 방식이 있습니다.Hoare 방식양 끝에서 가운데로의 진행방향Lomuto 방식한쪽 끝에서 다른쪽 끝으로의 진행방향본 내용은 로무토(Lomuto) 방식의 퀵 정렬에 대한 설명입니다. 아래는 간략한 Lomuto Partition 과정 설명입니.. 2023. 10. 28. [알고리즘] 병합 정렬 (Merge Sort) - Python 1. 병합 정렬 원리 1.1. Merge_Sort병합 정렬은 Divide and Conquer 방식을 사용합니다. 먼저 Array를 둘로 나누고(divide), 각 나눠진 Array를 각각 정렬(Conquer)하여 다시 합치는 방식을 말합니다.이때, 재귀적으로 배열을 나누고, 정렬해주는 과정을 거칩니다.그림으로 나타내면 아래와 같습니다. 1.1. Merge이제 각자 정렬이 끝난 두 배열을 합치는 Merge 과정을 알아보겠습니다. (1) 나눠져 정렬을 마친 두 배열이 왼쪽 그림과 같이 있을 때,각 배열의 제일 앞에 있는 두 원소를 비교한다. (2) 두 원소 중 작은 원소는 결과 list에 append한다. (3) list에 append된 숫자는 지우고 index를 한 칸 증가시킨다. .. 2023. 10. 28. [알고리즘] 삽입정렬(Insertion Sort) - Python 1. 삽입정렬의 원리(1) 삽입정렬은 2번째 index에서 시작합니다 (코드 작성시 주의) (2) 현재의 key가 앞의 숫자보다 큰지 작은지 확인하고,앞의 숫자 앞의 숫자 > key 이면: 서로 위치 바꾸기 (Swap) (3) 이후, key를 오른쪽으로 한 칸 옮기기 (4) key인 4가 8보다 작으므로 swap (5) 작업이 끝났으니 다시 key 한 자리 옮기기 (6) 위 과정을 계속 반복하여 최종 정렬된 array 생성 2. 삽입정렬 Python 코드1. index "i"는 위 설명에서의 Key를 의미합니다. 또한, range를 1에서부터 시작하여 2번째 index부터 key로 설정될 수 있게 합니다.2. key에서부터 왼쪽으로 대소비교를 하여 정렬을 할 수 있도록, inner loop를 .. 2023. 10. 28. 이전 1 다음
