[알고리즘] 사전ADT(2) - 예제

[문제1] 정렬되어 있는 n개의 정수 키와 탐색할 키 k를 입력받아, 사전에서 k의 위치를 출력하는 프로그램(이진탐색-재귀버전)

- x ≤ k 를 만족하는 사전의 키 x 중 가장 큰 값의 위치(즉, 인덱스) 출력
(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 –1 출력)

- 즉, 키 k가 존재하는 경우에는 k의 위치를 출력하면 되고,
그렇지 않은 경우 k보다 작으면서 가장 큰 수의 위치를 출력하면 된다.

입력예시                                 출력예시

8 -7  -92 -31 -7 4 14 20 29 44	2          -> 사전에서 -7의 위치는 2
8 33  -92 -31 -7 4 14 20 29 44	6          -> 문제 조건을 만족하는 사전의                  키는 29, 29의 위치는 6

#include<stdio.h> #include<stdlib.h> int maxindex = NULL; int findElement(int *arr, int n, int k) { return rFE(arr, k, 0, n - 1); } int rFE(int *arr, int k, int l, int r) { int mid; if (l > r) { return -1; } mid = (l + r) / 2; if (k == arr[mid]) { return mid; } else if (k < arr[mid]) { return rFE(arr, k, l, mid - 1); } else { if (maxindex == NULL) { maxindex = mid; } else if (arr[maxindex]<arr[mid]) { maxindex = mid; } return rFE(arr, k, mid + 1, r); } } void main() { int n, k, *arr; scanf("%d", &n); scanf("%d", &k); arr = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } if (findElement(arr, n, k) == -1) { if (maxindex == NULL) printf(" %d\n", findElement(arr, n, k)); else printf(" %d\n", maxindex); } else { printf(" %d\n", findElement(arr, n, k)); } free(arr); }

[문제2] 정렬되어 있는 n개의 정수 키와 탐색할 키 k를 입력받아, 사전에서 k의 위치를 출력하는 프로그램(이진탐색-비재귀버전)

- x ≥ k 를 만족하는 사전의 키 x 중 가장 작은 값의 위치(즉, 인덱스) 출력
(위치는 0부터 시작한다고 가정하고, 위 조건을 만족하는 x가 없는 경우 n 출력)

입력예시    출력예시

8 -100  -92 -31 -7 4 14 20 29 44	0           -> 문제 조건을 만족하는 사전의                   키는 -92이고, -92의 위치는 0
8 55  -92 -31 -7 4 14 20 29 44	8           -> 55보다 큰 사전의 키가 없음,                        n값 8 출력

#include<stdio.h> #include<stdlib.h> int minindex = -1; int findElement(int *arr, int n, int k) { int mid, l = 0, r = n - 1; while (1) { if (l > r) { return -1; } mid = (l + r) / 2; if (arr[mid] == k) { return mid; } else if (arr[mid] > k) { if (minindex == -1) { minindex = mid; } else if (arr[minindex] > arr[mid]) { minindex = mid; } r = mid - 1; } else { l = mid + 1; } } } void main() { int n, k, *arr; scanf("%d", &n); scanf("%d", &k); arr = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } if (findElement(arr, n, k) == -1) { if (minindex == -1) printf(" %d\n", n); else printf(" %d\n", minindex); } else { printf(" %d\n", findElement(arr, n, k)); } free(arr); }