1. 예고 ¶
요구사항 : 지금까지 배운 내용을 모두 알고 있어야 함
출제방식 : 새로운 개념을 이용하는 프로그램을 만든다
보상 : 테스트 실패시 보강 진행
출제방식 : 새로운 개념을 이용하는 프로그램을 만든다
보상 : 테스트 실패시 보강 진행
문제 | 종류 | 난이도 |
1단계 | Binary Search | 보통 |
2단계 | BFS / DFS 중 하나 출제 | 어려움 |
3단계 | Bayesian Classifier | 지옥불 |
2.1. Binary Search ¶
문제
binary search(이진 탐색)는 이미 정렬된 배열을 대상으로 수행하는 검색 알고리즘이다.
첫 번째 과제는 오름차순으로 정렬된 정숫값을 가지는 1차원 배열로부터 원하는 값의 존재유무와 인덱스 번호를 출력하는 binary_search 함수를 구현하는 것이다.
만약 찾으려는 값이 배열에 존재하지 않으면 -1을 리턴한다.
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* arr, int tofind, int start, int end) { int pivot = [start와 end의 중간]; /* 주요부분 생략 */ if (end < start) return -1; return binary_search(arr, tofind, start, end); }
테스트용 코드
#include <stdio.h> #pragma warning(disable:4996) int binary_search(int*, int, int, int); //function prototype int main(void) { int arr1[10] = { 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 }; int arr2[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }; int arr3[10] = { 5, 5, 5, 10, 10, 10, 10, 15, 15, 15 }; for (int i = 0; i < 10; i++) { printf("%d ", arr1[i]); } printf("\n\n===================\n\n"); for (int i = 0; i < 10; i++) { printf("%d ", arr2[i]); } printf("\n\n===================\n\n"); for (int i = 0; i < 10; i++) { printf("%d ", arr3[i]); } printf("\n\n===================\n\n"); int scan; printf("Input number to find : "); scanf("%d", &scan); printf("Input number found at %d, %d, %d", binary_search(arr1, scan, 0, 9), binary_search(arr2, scan, 0, 9), binary_search(arr3, scan, 0, 9)); return 0; }