티스토리 뷰
시작하며
삼성전자 SW 역량테스트 B형은 라이브러리를 사용할 수 없는 대신 Reference Code를 제공합니다. 제가 구현한 알고리즘들은 기본적으로 Reference Code를 바탕으로 하며 이해하는 과정에서 주석을 달며 정리했습니다. 구현 코드는 실제 시험에서 사용할 때는 달라질 수 있으며 각자에게 맞는 방식으로 구현하시는 것을 추천합니다.
이진 검색 알고리즘(Binary Search)
①
이진 검색 알고리즘(Binary Search)는 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식입니다. 처음 선택한 중간값보다 찾고자 하는 값이 크면 중간값은 새로운 최댓값이 되며, 작으면 중간값은 새로운 최솟값이 됩니다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있습니다.
②
아래 소스코드에서 binarySearch함수는 1차원 배열 arr[], low(최솟값의 index), high(최댓값의 index), target(찾고자 하는 값)까지 총 4개의 매개변수를 가지고 있습니다. binarySearch 함수의 동작은 다음과 같습니다.
low가 high보다 크다면 검색에 실패했고 -1을 return합니다.
mid(중간값의 index)는 low와 high의 중간값으로 설정합니다.
i) 만약 target이 arr[mid](중간값)보다 작으면 high값을 mid-1로 설정하고 binarySearch 함수를 진행합니다.
ii) 만약 target이 arr[mid]보다 크다면 low값을 mid+1로 설정하고 binarySearch 함수를 진행합니다.
위의 i)과 ii)의 조건에 충족되는 경우가 아니라면 target값을 찾은 경우이기 때문에 target값의 index인 mid를 return합니다.
③
아래 소스코드의 맨 아래 주석 부분을 보면 Input과 Output을 알 수 있습니다. 문제에서 요구하는 Output은 Binary Search를 이용하여 제시한 숫자가 있으면 해당 index를 출력하고, 없으면 -1을 출력하는 것입니다.
T(테스트 케이스의 개수)는 2이고, M(1차원 배열에 들어가는 숫자의 개수)은 12입니다. N(제시할 숫자의 개수)은 5이고 1차원 배열에 저장될 수들인 3 7 28 29 43 49 55 58 69 77 79 99가 들어옵니다. 그 다음 줄에 찾아야 하는 숫자들인 8 49 58 44 7이 들어옵니다. 해당 Input에 대한 Output은 -1 5 7 -1 1 이고 8과 49를 찾는 과정을 살펴 보겠습니다.
i) 8을 찾는 경우
binarySearch(arr, 0, 11, 8): binarySearch에 1차원 배열인 arr, 최솟값 index인 0, 최댓값 index인 11(M-1), target값인 8이 들어갑니다. 중간값 index인 mid는 (0+11)/2 = 5가 되고 arr[5] = 49이고 target값인 8은 49보다 작으므로 high를 4(mid-1)로 설정하고 binarySearch를 진행합니다.
binarySearch(arr, 0, 4, 8): mid는 (0+4)/2 = 2가 되고 arr[2] = 28입니다. target값 8은 28보다 작으므로 high를 1(mid-1)로 설정하고 binarySearch를 진행합니다.
binarySearch(arr, 0, 1, 8): mid는 (0+1)/2 = 0이 되고 arr[0] = 3입니다. target값 8은 3보다 크므로 low를 1(mid+1)로 설정하고 binarySearch를 진행합니다.
binarySearch(arr, 1, 1, 8): mid는 (1+1)/2 = 1이 되고 arr[1] = 7입니다. target값 8은 7보다 크므로 low를 2(mid+1)로 설정하고 binarySearch를 진행합니다.
binarySearch(arr, 2, 1, 8): low가 high보다 크므로 탐색에 실패함을 알 수 있고 -1을 return합니다.
ii) 49를 찾는 경우
binarySearch(arr, 0, 11, 49): binarySearch에 1차원 배열인 arr, 최솟값 index인 0, 최댓값 index인 11(M-1), target값인 49가 들어갑니다. 중간값 index인 mid는 (0+11)/2 = 5가 되고 arr[5] = 49이고 target값을 찾는데 성공함을 알 수 있습니다. target값의 index는 mid이고 5를 return합니다.
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
class STL_BinarySearch {
static final int MAX_M = 100;
static int T; // # of test case
static int M; // # of element in array
static int N; // # of numbers to search
static int arr[]; //arr[]: 입력 배열
static void binarySearch(int[] arr, int low, int high, int target) {
int mid;
if (low > high) { //target을 찾지 못한 경우
System.out.print("-1 ");
return;
}
mid = (low + high) / 2; //mid: 탐색 범위의 중간 index
if (target < arr[mid]) { //target이 중간값보다 작은 경우
binarySearch(arr, low, mid - 1, target);
} else if (arr[mid] < target) { //target이 중간값보다 큰 경우
binarySearch(arr, mid + 1, high, target);
} else { //target을 찾은 경우
System.out.print(mid + " ");
return;
}
}
public static void main(String arg[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
System.out.print("#" + test_case + " ");
M = sc.nextInt();
N = sc.nextInt();
arr = new int[M];
for (int i = 0; i < M; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < N; i++) {
int targetValue = sc.nextInt();
binarySearch(arr, 0, M - 1, targetValue);
}
System.out.println();
}
}
}
/*
input
2
12
5
3 7 28 29 43 49 55 58 69 77 79 99
8 49 58 44 7
7
3
3 4 5 6 7 8 9
1 2 3
output
#1 -1 5 7 -1 1
#2 -1 -1 0
*/
|
- Total