[자료구조 및 알고리즘] (4) Divide & conquer에 대한 설명과 예시 3가지

이번 글에서는 1. Divide and conquer란 2.

예시 1: Counting inversions 3. 예시 2: Matrix multiplication 4.

예시 3: Closest pair 1. Divide and conquer란 알고리즘에서 divide and conquer란, 얼핏 보기에 노답인 알고리즘 (O(n^2), O(n^3))들을 조금 더 빨리 돌리기 위한 방법을 이야기한다. 3가지 스텝으로 나누어 볼 수 있다.

Divide: 주어진 인풋을 더 작게 나눈다. (보통 두 개로 쪼개는데, 그 이유는 세 개로 쪼개도 아래 combine step이 - O(1)이 아니라면 - 3배가 되어 improvement가 없기 때문이다.)

Conquer subproblem: 작게 쪼갠 인풋을 해결(?)한다.

Combine: 다시 하나로 합쳐서, 원래 인풋인 n에 해당하는 아웃풋을 만들어낸다. 이전에 다루었던 merge sort가 좋은 예시다. 2.

예시 1: Counting in...