분할 정복 기법

문제를 나누어서 계산하는 알고리즘 기법

개요

• 문제를 나누어서 계산하고, 각각의 해를 합쳐서 전체 문제의 해를 구하는 방법이다.

시간복잡도

O(log2N)

이진 탐색 (Binary Search)

과정

1. 자료의 중앙에 있는 원소를 고른다.
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색을 끝낸다.
4. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
5. 찾고자 하는 값을 찾을 때 까지 반복한다.

퀵 소트

병합 정렬