그래프 시작 정점으로부터 가까운 정점부터 순차적으로 방문해나가는 탐색 알고리즘이다.인접한 정점들을 먼저 방문하고, 그 다음 그들의 인접 정점을 방문하는 방식으로 진행된다.즉, 최단 경로를 찾을 때 많이 사용한다. 💡 BFS의 정당성 ✅ 시작정점에서 도달 가능한 모든 정점을 정확히 한 번씩 방문한다. 1. Queue에서 정점 u를 꺼낸다.2. u에 인접한 모든 정점 v를 확인한다.3. 방문❌ 정점 v는 방문 표시를 하고, 큐에 삽입한다.즉, 한 번 방문한 정점은 다시 큐에 삽입❌ → 정점은 정확히 한 번 방문한다. 💡 BFS의 최단 경로성✅ BFS는 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는다. - 시작 정점 s에서 각 정점까지의 거리 : d(v) (= 간선의 수)- BFS는 항상 거리가..

그래프에서 가능한 깊이까지 먼저 탐색한 다음, 더이상 진행될 수❌ → 다시 돌아와 다른 경로를 탐색하는 알고리즘. 💡 DFS의 정당성 ✅ 시작정점에서 도달 가능한 모든 정점을 정확히 한 번씩 방문한다.- DFS는 방문한 정점에 대해 방문 표시를 한다.- 어떤 정점 v를 방문할 때, v에 인접한 정점 w 중, 방문❌ 정점에 대해 재귀적으로 탐색하거나 스택에 넣는다.- 한 번 방문한 정점은 다시 방문❌ → 각 정점은 정확히 1번 방문된다. 💡 DFS의 깊이 우선 탐색 특성✅ DFS는 가능한 깊이까지 탐색을 진행한 후, 막히면 되돌아가서 탐색을 이어간다.✔ 증명 (DFS 흐름은 다음과 같다.)1. 현재 정점 v에서 인접한 정점 w를 찾는다.2. 아직 방문❌ 정점 w 발견 → 그 정점으로 바로 이동해 탐..

Divide-and-conquer를 기반으로 하는 정렬 알고리즘으로, 방식은 아래와 같다.1. Pivot 선택 : 배열에서 하나의 원소를 pivot으로 선택한다. 2. 분할 : pivot을 기준으로 pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 배열한다.3. 재귀 호출 : 왼/오른쪽 부분 배열에 quick sort를 재귀적으로 수행한다. 💡 이상적인 경우 pivot이 항상 배열을 거의 절반으로 나누는 경우, T(n) = 2T(n/2)+O(n) 재귀식을 따른다.마스터 정리를 이용하면, T(n)=O(nlogn)이 된다. 💡 최악의 경우pivot이 항상 가장 작거나 or 큰 원소를 선택하는 경우이다.(= 배열이 거의 정렬되어 있거나 역순일 때 잘못된 pivot을 선택한다는 말)이때, partit..

Divide-and-conquer를 기반으로 하는 대표적인 정렬 알고리즘. 주어진 배열 n을 2/n으로 계속 분할해, 각 부분 배열이 하나의 원소를 가질 때까지 나눈 다음, 이를 다시 정렬하면서 병합하는 방식으로 전체 배열을 정렬한다. 즉, 크게 3개의 과정으로 나뉜다.1. Divide : 배열을 가운데 기준 두 부분으로 나누어준다. 🌐 O(1) (중간 인덱스만 알면 되니까)2. Conquer : 나눠진 배열 각각에 대해 재귀적으로 mergesort를 적용해 정렬한다. 2번의 정렬 작업이 이뤄진다.3. Combine : 정렬된 두 배열을 하나의 정렬된 배열로 병합한다. 🌐 O(n) (모든 원소를 한 번씩 비교해 합치니까) 이를 점화식으로 표현하면 아래와 같다. ✅ 분할이 log n 단계에 걸쳐 일어나..

📌 Divide-and-Conquer Algorithm이란문제를 여러 부분으로 나눈 뒤, 각 부분을 재귀적으로 해결한다.그 후, 각 부분의 해답을 결합해 전체 문제의 해답을 도출한다.분할(Divide): 문제를 더 작은 하위 문제로 나눈다.정복(Conquer): 하위 문제를 재귀적으로 해결한다.결합(Combine): 하위 문제의 해를 결합하여 전체 문제를 해결한다.📌 Merge Sortdivide-and-conquer 방식 기반으로 동작문제를 나눠 해결하고, 통합하는 방식 시간 복잡도분할단순히 배열을 반으로 자르는 작업으로, 한 번 나눌 때 걸리는 시간은 상수 시간 O(1)전체 분할은 트리 구조로 log₂n 단계까지 진행됨.✅ O(log₂n)정복두 배열을 순회하면서 합치는 과정 O(n)병합은 트리 구..