컴퓨터 과학(Computer Science)/알고리즘(Algorithm)9 [알고리즘] 너비 우선 탐색(BFS) - Python 너비 우선 탐색 Breadth-First Search너비 우선 탐색(BFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 너비 방향(Breadth)으로 확장하는 방식의 탐색을 말합니다. 넓게 확장하는 것이란, 한 노드에서 인접한 모든 노드를 우선 탐색하는 것을 말합니다. 인접해있는 모든 노드의 탐색을 마친 후, 다음 노드에서의 너비 탐색을 시작합니다. Level탐색을 진행할 때 인접한 노드를 차례대로 모두 탐색하고 다음 인접 노드로 넘어간다고 했는데, 이때 같은 층위에 있는 인접 노드들을 level로 묶습니다. 그림을 보시면, root에서 시작해 root에 바로 인접해 있는 노드들을 level 1이라고 부르고, 이 level 1에 속해있는 노드들의 parent는 당연히 root .. 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 2 다음
