mergesort1 [알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 합병 정렬(merge sort) 분할 정복 알고리즘이란? 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘입니다. 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산합니다. 이들의 해를 취합하여 원래 문제의 해를 얻습니다. 분할 알고리즘의 분할은 부분 문제와 부분 해로 나누어 집니다. 분할된 입력에 대한 문제를 부분 문제(subproblem)라고 합니다. -> 해 계산 부분 문제의 해를 부분 해라고 합니다. 부분 문제는 더 이상 분할 할 수 없을 때까지 분할합니다. 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분 문제의 크기가 n/2일 경우의 분할의 예입니다. 총 분할한 횟수가 k라고 한다면, 처음 입력의 크기가 n이고, 분할된 그 다음의 크기는 n/2, 그 다음은 n/(2^2), ... , n/(2^.. 2023. 9. 24. 이전 1 다음
