선형(순차) 탐색 알고리즘
오늘의 포스팅은 순차 탐색 또는 선형 탐색이라고도
불리는 "Linear Search (Sequential Search)"
알고리즘에 대해 써볼려고 합니다.
이 알고리즘은 탐색 알고리즘 중에서도 가장 기본이
되는 알고리즘 입니다.
"순차" 라는 단어를 보면 아마 다들 느낌이 오셨을 겁니다.
이 알고리즘은 그냥 다수의 데이터를 순차적으로 하나씩 조회 하면서 내가 찾고자 하는
아이템이 있는지를 탐색하는 것입니다.
찾고자하는 데이터를 찾을때 까지 모든 아이템을 검사하고 특정 데이터를 검사하게
되며 특정 데이터를 찾았을 경우에는 해당 아이템을 반환하고 알고리즘은
거기서 종료하게 됩니다.
간략하게 말하자면 10개의 데이터중 첫번째로 검색한 데이터가 내가 원하는
데이터이면 나머지 9개의 데이터는 조회할 필요없이 알고리즘은 종료됩니다.
못 찾았을 경우에는 모든 데이터를 다 검사하게 됩니다.
데이터를 따로 정렬하거나 건드릴 필요가 없고, 난이도가 쉬운 편이나,
데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩
일일이 비교하는 단점이 있기때문에 비효율적이라는 단점이 있습니다.
예를 들어 위와 같은 데이터를 데이터의 집합이 있을때
9를 찾을려면 7번의 비교를 거쳐야 합니다.
100만개의 데이터가 있고 찾을려하는 데이턱 100만번 째에 있다면
100만번의 비교를 해야 한다는 뜻입니다.
이와 같은 상황을 Worst Case라고 합니다.
관련되 용어로 평균적인 상황을 Average Case 좋은
상황을 Best Case 라고 합니다.
int LinearSearch(int arr[], int size, int target){
for(int i = 0; i < size; i++)
if(arr[i] == target) //arr이라는 배열에서 target을 찾는다.
return i; //찾으면 해당 방번호를 리턴
return -1; //못찾으면 -1을 리턴
}
int arr[] 데이터의 집합인 배열
int size 배열의 크기
int target 찾을려는 데이터 를 함수의 전달인자로 받습니다.
for 문 은 size에 크기 만큼 실행 시키고
if 문 안에 arr[0] 부터 i의 값을 증카시키면서 진행이 됩니다. arr[5]에서
target 9라는 값을 찾으면
int LinearSearch 함수에 return i 가 반환되고
만약 예시와 다르게 target값을 찾지 못했다면 반복문이 종료되어 -1이 반환됩니다.
-1일때는 예외처리문이 필수 입니다.
간단하게 소개해줬는데 코드를 보면 의외로 간단한 알고리즘 인걸
댓글
댓글 쓰기