CS공부/알고리즘
-
정렬CS공부/알고리즘 2022. 10. 13. 22:49
분할 정복법 (Divide and Conquer) 탐욕 알고리즘 (Greedy) 동적 계획법 (Dynamic Programming) 알고리즘 응용 정렬 알고리즘 선택 정렬, 거품 정렬, 삽입 정렬 분할 정복법 (Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 ex)퀵 정렬, 합병 정렬, 이진 탐색 분할된 문제는 서로 독립적이다. 분할된 작은 문제는 원래 문제와 성격이 동일하다 => 입력 크기만 작아짐 1) divide : 원래 문제를 분할하여 더 작은 하위 문제로 분할이 가능할 때까지 나눈다. 2) conquer: 하위 문제를 재귀적으로 해결 3)combine: conquer한 문제들을 통합하여 원래 문제의 답을 얻ㅇ 해결 장점 top-down..