반응형
순차 탐색(Linear Search)
맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에 순차 탐색이라는 이름이 붙어있다.
순차 탐색 알고리즘을 구현해보자.
배열 arr
| 1 | 2 | 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx0 | idx1 | idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
위 배열에서 3을 찾아본다면
* 첫번째 시도
1. idx0번이 3인지 확인
| ↓ |
| 1 | 2 | 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx0 | idx1 | idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
* 두번째 시도
1. idx1번이 3인지 확인
| ↓ |
| 2 | 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx1 | idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
* 세번째 시도
1. idx2번이 3인지 확인
| ↓ |
| 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
3 번째 3을 확인하고 로직이 종료된다. 이처럼 처음부터 끝까지 하나하나 찾아가는게 순차 탐색이다.
#include <stdio.h>
int LSearch(int ar[], int len, int target) // 순차 탐색 알고리즘 적용된 함수
{
int i;
for (i = 0; i < len; i++)
{
if (ar[i] == target)
return i; // 찾은 대상의 인덱스 값 반환
}
return -1; // 찾지 못했음을 의미하는 값 반환
}
int main(void)
{
int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27 };
int idx;
idx = LSearch(arr, sizeof(arr) / sizeof(int), 3);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
이진 탐색(Binary Search) 알고리즘
순차 탐색 알고리즘보다 더 빠른 속도를 갖고 있다.
이진 탐색알고리즘을 적용하기전에 데이터는 정렬이 되어 있어야한다.
아래 배열로 이진 탐색 알고리즘을 분석해보자
배열 arr
| 1 | 2 | 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx0 | idx1 | idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
배열 arr에서 숫자 3이 저장되어 있는지 확인하는 과정을 보자
* 첫번째 시도
1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.
2. 0과 8을 합하여 그 결과를 2로 나눈다.
3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.
즉, 배열의 중앙에 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘의 첫번째 시도이다.
| ↓ |
| 1 | 2 | 3 | 7 | 9 | 12 | 21 | 23 | 27 |
| idx0 | idx1 | idx2 | idx3 | idx4 | idx5 | idx6 | idx7 | idx8 |
arr[3]에 3이 저장되지 않았음을 확인 하였으니 두 번째 시도를 진행한다.
* 두번째 시도
1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다.
2. 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.
3. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.
4. 2로 나눠서 얻은 결과각 1이니 arr[1]에 저장된 값이 3인지 확인한다.
| ↓ |
| 1 | 2 | 3 | 7 |
| idx0 | idx1 | idx2 | idx3 |
* 세번째 시도
1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.
2. 대소의 비교결과는 arr[1] < 3 이므로 탐색의 범위를 인덱스 기준 2~3으로 제한한다.
3. 2와 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.
4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.
| ↓ |
| 3 | 7 |
| idx2 | idx3 |
3임을 확인하면 로직이 완료 된다. 이진 탐색 알고리즘은 탐색할때 마다 1/2씩 범위가 줄어든다. 때문에 순차 탐색 알고리즘보다 탐색속도가 빠르다.
#include <stdio.h>
int BSearch(int ar[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid;
while (first <= last)
{
mid = (first + last) / 2; // 탐색 대상의 중앙을 찾는다.
if (target == ar[mid]) // 중앙에 저장된 것이 타겟이라면
{
return mid; // 탐색 완료!
}
else // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
{
if (target < ar[mid])
last = mid - 1;
else
first = mid + 1;
}
}
return -1; // 찾지 못했을 때 반환되는 값 -1
}
// 2 번째 풀이..
int BSearch(int arr[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid = -1;
while (first < last)
{
if (mid > 0 && arr[mid] < target)
first = mid + 1;
if (mid > 0 && arr[mid] > target)
last = mid - 1;
mid = (last + first) / 2;
if (arr[mid] == target)
return mid;
}
return -1;
}
int main(void)
{
int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27 };
int idx;
idx = BSearch(arr, sizeof(arr) / sizeof(int), 3);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
이진 탐색(Binary Search)알고리즘 재귀로 구현
#include <stdio.h>
int BSearch(int ar[], int first, int last, int target)
{
int mid;
if (first > last)
return -1; // -1의 반환은 탐색의 실패를 의미
mid = (first + last) / 2; // 탐색대상의 중앙을 찾는다.
if (ar[mid] == target)
return mid; // 탐색된 타겟의 인덱스 값 반환
else if (target < ar[mid])
return BSearch(ar, first, mid - 1, target);
else
return BSearch(ar, mid + 1, last, target);
}
int main(void)
{
int arr[] = { 1, 2, 3, 7, 9, 12, 21, 23, 27 };
int idx;
idx = BSearch(arr, sizeof(arr) / sizeof(int), 3);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx = BSearch(arr, sizeof(arr) / sizeof(int), 4);
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
순차탐색 알고리즘과 이진탐색 알고리즘의 시간 복잡도 (worst case)
순차 탐색 알고리즘
데이터의 수가 n개일 때, 최악의 경우는 마지막 까지(n까지) 연산하는 것이다.
그러므로 최악의 경우는 T(n) = n
이진 탐색 알고리즘
데이터의 수가 n개일 때, 최악의 경우는 마지막 까지(n까지) 연산하는 것이다.
처음에 데이터의 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행
데이터의 수를 반으로 줄여서 그 수가 n/2 개일 때의 탐색과정에서 1회 비교연산 진행
데이터의 수를 반으로 줄여서 그 수가 n/4 개일 때의 탐색과정에서 1회 비교연산 진행
데이터의 수를 반으로 줄여서 그 수가 n/8 개일 때의 탐색과정에서 1회 비교연산 진행
....
데이터의 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행
위 과정을 일반화 하여 수식으로 표현하자면
n이 1이 되기까지 2로나눈 횟수 k회, 따라서 비교연산 k회 진행
데이터가 1개 남았을 때, 이때 마지막으로 비교 연산 1회 진행
최악의 경우에 대한 시간 복잡도 함수 : T(n) = k + 1
k를 구해보면, n이 1이 되기까지 2로 나눈 횟수가 k이니 n과 k에 관한 식을 다음과 같이 세울 수 있다.
n * (1/2)^k = 1
위 수쉭은 2로 몇 번을 나누어야 1이 되는가에 대한 답을 주는 수식 이다.
위 수식을 k에 관한 식으로 변경하면
n * (1/2)^k = 1 => n * 2^-k = 1 => n = 2^k
log₂n = log₂2^k => log₂n = k * log₂2 => log₂n = k
k = log₂n
이를 최악의 경우에 대한 시간 복잡도 함수에 대입해보면
T(n) = log₂n + 1 이 되고 n이 아주 많이 높은 숫자라 가정하면(최악의 경우이니..) 1은 작은 숫자이니 생략하면
T(n) = log₂n가 된다.
순차 탐색 알고리즘과 이진 탐색 알고리즘의 비교
#include <stdio.h>
int LSearch(int ar[], int len, int target)
{
int i;
int opCount = 0; // 비교연산의 횟수를 기록
for (i = 0; i < len; i++)
{
if (ar[i] == target)
return i;
opCount += 1; // 비교연산의 횟수 1증가
}
printf("LSearch 비교연산횟수: %d \n", opCount); // 탐색실패 시 연산횟수 출력
return -1;
}
int BSearch(int ar[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid;
int opCount = 0; // 비교연산의 횟수를 기록
while (first <= last)
{
mid = (first + last) / 2;
if (target == ar[mid])
{
return mid;
}
else
{
if (target < ar[mid])
last = mid - 1;
else
first = mid + 1;
}
opCount += 1; // 비교연산의 횟수 1증가
}
printf("BSearch 비교연산횟수: %d \n", opCount); // 탐색실패 시 연산횟수 출력
return -1;
}
void print(int idx)
{
if (idx == -1)
printf("탐색 실패\n");
else
printf("타겟 저장 인덱스: %d \n", idx);
}
int main()
{
int arr1[500] = { 0, };
int arr2[5000] = { 0, };
int arr3[50000] = { 0, };
int idx;
// 배열 arr1을 대상으로, 저장되지 않은 정수 1을 찾으라고 명령
printf("==500======================================================\n");
idx = LSearch(arr1, sizeof(arr1) / sizeof(int), 1);
print(idx);
idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 1);
print(idx);
printf("===========================================================\n");
// 배열 arr2을 대상으로, 저장되지 않은 정수 2을 찾으라고 명령
printf("==5000=====================================================\n");
idx = LSearch(arr2, sizeof(arr2) / sizeof(int), 2);
print(idx);
idx = BSearch(arr2, sizeof(arr2) / sizeof(int), 2);
print(idx);
printf("===========================================================\n");
// 배열 arr3을 대상으로, 저장되지 않은 정수 3을 찾으라고 명령
printf("==50000====================================================\n");
idx = LSearch(arr3, sizeof(arr3) / sizeof(int), 3);
print(idx);
idx = BSearch(arr3, sizeof(arr3) / sizeof(int), 3);
print(idx);
printf("===========================================================\n");
return 0;
}
반응형
