본문 바로가기

합병정렬1

10. 합병정렬 (merge sort) - 분할정복알고리즘(Divide and Conquer) 그냥 말 그대로, 배열을 분할하고, 해결하고, ... 이를 반복하는 알고리즘이다. 1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 2. 정복 : 각각의 작은 문제를 순환적으로 해결 3. 합병 : 작은 문제의 해를 합하여(merge), 원래 문제에 대한 해를 구함 대표적인 분할정복알고리즘에는 합병정렬(merge sort)과 퀵정렬(quick sort)이 있다. 분할은 하나의 큰 문제를 각자 작은 문제로 나누는 것이다. 이 각각의 작은 문제들은 원래 문제와 동일한 문제여야 한다. 정복이라는 의미는 각각의 작은 문제를 해결하는 것이다. 위의 그림은 합병정렬을 간단하게 표현한 예이다. 예를 들어 위의 배열에서 최댓값을 구하는 문제를 .. 2020. 10. 15.

이전 1 다음

티스토리툴바