안녕

1. Binary Search의 알고리즘 및 코드 분할 정복의 기본은 재귀이기 때문에 반복문이 아닌 재귀를 통해서 binary search를 하겠습니다. 반복문을 통한 binary search는 앞 글을 참고해주세요. Problem : 원소가 n개인 (오름차순)정렬된 리스트 S안에 검색하려는 수 x가 있는가? input : 양의 정수 n, 정렬된 리스트 S, 검색키 x output : x의 위치, 만약 없다면 -1를 반환 알고리즘 구상) 1) x와 S의 중간 값과 비교해 같다면 그대로 끝 2) 만약 다르다면 두 가지 방법을 이용한다. 2.1) x가 S의 중간 값보다 작다면 중간 위치를 기준으로 왼쪽 리스트를 탐색한다. 2.2) x가 S의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다...

1. 분할 정복이란? 분할 정복은 이름에서 볼 수 있듯이 말 그대로 분할 정복입니다. 분할 정복의 접근법) 1. divides an instance of a problem into two or more smaller instances. 2. if they are too large to be sorved, they can be divided into still smaller instances 3. if solutions to them can be obtained readily, these smaller solutions can be combined into original solution 즉, 문제를 두 개 이상의 instance로 쪼갠다. 그래도 instance가 여전히 크면 또 쪼갠다. 만약 분할한 i..