깡총파파의 일상

세상의 모든 알고리즘 - 퀵정렬 퀵정렬(Quick Sort)은 대표적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방법을 사용합니다. 이 알고리즘은 평균적으로 가장 빠른 속도를 보이며, 대부분의 정렬 라이브러리에서 사용됩니다. 퀵정렬은 다음과 같은 과정으로 이루어집니다. 피벗(Pivot) 선택: 정렬할 배열에서 하나의 원소를 선택하여 피벗으로 지정합니다. 피벗은 배열을 나누는 기준이 됩니다. 분할: 피벗을 기준으로 배열을 두 개의 부분 배열로 분할합니다. 피벗보다 작은 원소는 왼쪽 부분 배열에, 큰 원소는 오른쪽 부분 배열에 위치시킵니다. 정복: 분할된 부분 배열에 대해 재귀적으로 퀵정렬을 수행합니다. 이때, 각 부분 배열에서 피벗을 다시 선택하고, 분할 및 정복 과정을 반..

세상의 모든 알고리즘 - DFS DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다. 이 알고리즘은 그래프의 모든 정점을 방문하는 방법 중 하나 DFS는 스택(Stack) 자료구조를 이용하여 구현 시작 정점을 스택에 넣고, 스택에서 정점을 꺼내어 방문하는 방식. 이때, 방문한 정점은 방문한 것으로 표시하고, 해당 정점과 인접한 정점들을 스택에 넣는다. 이후, 스택에서 다시 정점을 꺼내어 방문하고, 해당 정점과 인접한 정점들을 스택에 넣는 과정을 반복합니다. 이 과정에서 스택이 비어있게 되면 탐색을 종료함. DFS는 그래프의 모든 정점을 방문하며, 이를 이용하여 그래프의 연결성을 파악하거나, 최단 경로를 찾는 등의 문제를 해결할 수 있습니다. 또한,..

세상의 모든 알고리즘 - BFS 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 가까운곳 먼저 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다. 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다. 너비..