More actions
예고
요구사항 : 지금까지 배운 내용을 모두 알고 있어야 함 출제방식 : 새로운 개념을 이용하는 프로그램을 만든다 보상 : 테스트 실패시 보강 진행
| 문제 | 종류 | 난이도 |
| 1단계 | Binary Search | 보통 |
| 2단계 | BFS / DFS 중 하나 출제 | 어려움 |
| 3단계 | Bayesian Classifier | 지옥불 |
테스트
Binary Search
문제 binary search(이진 탐색)는 이미 정렬된 배열을 대상으로 수행하는 검색 알고리즘이다. 첫 번째 과제는 오름차순으로 정렬된 정숫값을 가지는 1차원 배열로부터 원하는 값의 존재유무와 인덱스 번호를 출력하는 binary_search 함수를 구현하는 것이다. 만약 찾으려는 값이 배열에 존재하지 않으면 -1을 리턴한다.
동작 방식은 다음과 같다. 여기서는 중복된 값이 일치하는 경우에 대해서는 아무 인덱스나 출력하면 되는 것으로 가정한다.
1. 배열의 중앙에 위치한 값을 pivot으로 잡는다. 2. 찾으려는 값과 pivot에 위치한 값을 비교한다. 2-1. 만약 그 값이 일치한다면, 찾은 것이다. 2-2. 만약 그 값이 pivot에 위치한 값보다 크면 3-1로 이동한다. 2-3. 만약 그 값이 pivot에 위치한 값보다 크면 3-2로 이동한다. 3-1. pivot을 포함해 그 이후의 부분들은 무조건 찾으려는 값보다 크므로 검색 대상에서 제외한다. 3-2. pivot을 포함해 그 이전의 부분들은 무조건 찾으려는 값보다 크므로 검색 대상에서 제외한다. 4. 만약 더 이상 제외할 수 없다면(최근의 검사 대상이 마지막 검색 대상이었다면) 이 배열에는 찾으려는 값이 없으므로 알고리즘을 종료한다. 5. 남은 부분의 배열에서 중간에 위치한 값을 pivot으로 잡고 2로 이동한다.
함수 프로토타입 예시는 다음과 같다.
int binary_search(int*, int, int, int); //function prototype
int binary_search(int* arr, int tofind, int start, int end) {
int pivot = [start와 end의 중간];
/* 주요부분 생략 */
if (end < start) return -1;
return binary_search(arr, tofind, start, end);
}
Depth-First Search
문제