공부/알고리즘1 알고리즘 공부 - 분할 정복 알고리즘, 합병(merge) 정렬, 퀵(quick) 정렬 분할 정렬 알고리즘이란?주어진 문제의 입력을 분할하여 문제를 해결 = 정복하는 알고리즘 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하여 이들의 해를 취합하여 원래 문제의 해를 얻음이때 분할된 입력에 대한 문제를 부분 문제라고 함 만약 입력 크기가 n이고 더이상 분할할수 없는 수준까지 갈려면 n/2를 반복함으로 결국 log n 이 된다 분할 정복 알고리즘의 분류합병 정렬문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘퀵 정렬문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘이진 탐색문제가 2개로 분할되나, 그중에 1개의 부분 문제는 고려할 필요 없이 부문문제의 크기가 1/2로 감소하는 알고리즘선택 문제 알고리즘문제가 2개로 분할되나, 그중에.. 2025. 3. 18. 이전 1 다음