J's tistory

🔎 합병 정렬이란?합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다. 즉, $n$개의 숫자들을 $n/2$개 씩 2개의 부분문제로 분할하고, 각각의 부분문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 다시 합병하여 정렬한다. 합병 과정이 문제를 정복하는 것이다. 합병(Merge)이란?합병은 2개의 각각 정렬된 숫자들을 하나의 정렬된 숫자들로 합치는 것이다. 🔽 다음은 각각 원소들이 정렬되어 있는 배열 A와 B를 합병하여 배열 C에 저장되어 있는 것을 보여준다. 🔎 합병 정렬 알고리즘MergeSort(A, p, q){ // 입력: A[p] ~ A[q] if(p  Line 3 : 정렬할 부분의 원소의 수가 2개 이상인 경우에만 ..

🔎 분할 정복 알고리즘이란?분할 정복 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고, 이들의 해를 취합하여 원래 문제의 해를 얻는 방식이다.이때, 분할된 입력에 대한 문제를 부분문제(subproblem)라고 하고, 부분문제의 해를 부분해라고 한다.부분문제는 더 이상 분할할 수 없을 때까지 분할한다. 🔽 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 $\frac{n}{2}$인 예시분할 과정은 다음과 같다.처음에 주어진 문제가 3개의 부분문제로 분할되고, 각 부분문제의 입력의 크기는 $\frac{n}{2}$이다.분할이 두 번 진행되면 부분 문제의 크기는 다시 각각 3개로 분할(총 ..