Divide-and-Conquer Algorithm

📌 Divide-and-Conquer Algorithm이란

문제를 여러 부분으로 나눈 뒤, 각 부분을 재귀적으로 해결한다.

그 후, 각 부분의 해답을 결합해 전체 문제의 해답을 도출한다.

1. 분할(Divide): 문제를 더 작은 하위 문제로 나눈다.
2. 정복(Conquer): 하위 문제를 재귀적으로 해결한다.
3. 결합(Combine): 하위 문제의 해를 결합하여 전체 문제를 해결한다.

---

📌 Merge Sort

• divide-and-conquer 방식 기반으로 동작
• 문제를 나눠 해결하고, 통합하는 방식

 

시간 복잡도

• 분할
  • 단순히 배열을 반으로 자르는 작업으로, 한 번 나눌 때 걸리는 시간은 상수 시간 O(1)
  • 전체 분할은 트리 구조로 log₂n 단계까지 진행됨.
  • ✅ O(log₂n)
• 정복
  • 두 배열을 순회하면서 합치는 과정 O(n)
  • 병합은 트리 구조로 log₂n 단계 동안 일어남.
  • ✅ O(nlog₂n)

✅ 즉, 시간 복잡도는 O(nlog₂n)임.

---

📌 Quick Sort

• divide-and-conquer 방식 기반으로 동작
  • 하지만, 결합 과정이 거의 필요 없는 게 특징임.
• pivot을 설정하고, 이를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치 조정
  • pivot 오른쪽 시작할 경우 ⇒ left와 change
  • pivot 왼쪽 시작할 경우 ⇒ right와 change

1. pivot 선정. 비교를 위한 index 변수 할당 (left, right)
2. left, right를 pivot과 비교하며 이동
3. pivot의 위치 수정
4. 분할된 리스트에 1~3 과정 적용 및 반복

 

각 단계별 시간

• 분할 : 한 번에 pivot 기준으로 전체를 훑음 → O(n)
• 깊이 : 최선이면 logn, 최악이면 n

 

시간 복잡도

• 평균 : O(nlog₂n)
  • 분할 : O(log₂n)
  • 정렬 : O(nlog₂n)
• 최악 : O(n²)

---

📌 Counting Inversions

그냥 하면 부르트포스

Divide-and-Conquer의 Merge sort를 활용하면, conquer 과정 중 순서가 바뀌는 개수를 합산한 것

---

📌 Closest Pair of Points

생략