알고리즘 - 분할정복법 (Divide and Conquer)

본 게시물은 경희대학교 한치근 교수님의 '알고리즘분석' 강의를 듣고 노트한 내용입니다. 분할정복식 설계 전략 분할(Divide) 문제를 여러개의 작은 부분으로 나눈다. 정복(Conquer) 나눈 문제를 해결한다. 통합(Combine) 해결된 해답을 모은다. -> 하향식(Top-Down) 문제 해결 방법 이분 검색 (binary search) 크기가 n인 정렬된 배열 S에 x가 있는지 결정하는 문제 분할 - 배열을 반으로 나누어 중앙에 위치한 항목보다 크고 작음을 판단해 해당 배열 반쪽을 선택한다. 정복 - 선택된 반쪽 배열에서 x를 찾는다. 통합 - 필요없음 1. 입력파라미터인 n, S, x는 변하지 않는 값이므로 전역 변수 (global)로 선언해 메모리를 절약하라! 재귀호출에서는 인덱스만 넘겨준다! ..