알고리즘 (1) 썸네일형 리스트형 분할정복 알고리즘 원리 주어진 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식입니다. 특성 분할된 작은 문제는 원래의 문제에 비해 입력 크기만 작아졌을 뿐 문제 자체는 원래 문제와 동일해야 합니다. 분할된 작은 문제들은 서로 독립적이어야 합니다. 하샹식 접근 방법을 사용합니다. 분할 -> 정복 -> 결합의 처리과정을 거칩니다. 종류 이진탐색 - 크기가 n인 문제를 n/2인 두 개의 작은 문제로 분할(그 중 하나의 작은 문제는 처리 대상에서 제외) 합병정렬 - 크기가 n인 문제를 n/2인 두 개의 작은 문제로 분할 퀵 정렬 - 크기가 n인 문제를 크기는 감소하지만 일정하지 않은 크기의 두 .. 이전 1 다음