선형 탐색 알고리즘이란?

오늘은 탐색 알고리즘 중 가장 간단한 알고리즘 중 하나인 선형 탐색에 대해 알아보려고 한다

참고로 선형 탐색은 이름에서 알 수 있듯이 리스트의 원소들을 한번에 하나씩 선형적(linearly)으로 탐색한다고 해서 선형 탐색이라고 이름이 붙여졌다

선형 탐색이란?

선형 탐색 알고리즘은 리스트에서의 모든 원소를 순차적으로 검사하여 원하는 값을 찾는 가장 기본적이고 간단한 탐색 알고리즘으로

처음에 설명한 것처럼 원소를 한번에 하나씩 선형적(linearly)으로 탐색한다는 특징을 가졌다

선형 탐색의 작동 방식

이러한 선형 탐색은 다음과 같은 방식으로 작동한다

1. 리스트의 처음부터 끝까지 원소를 하나씩 확인한다
2. 찾고자 하는 원소를 발견하면 그 위치(인덱스)를 반환한다
3. 리스트의 끝까지 원소를 찾지 못하면 원소가 없다는 뜻으로 -1이나 다른 특별한 값을 반환한다

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 3을 찾을 때 선형 탐색 알고리즘을 사용한다고 했을 때

주어진 리스트: [5, 7, 2, 9, 1, 3]

진행 방식

5 - X
7 - X
2 - X
9 - X
1 - X
3 - O

위와 같이 순차적으로 리스트의 모든 원소를 돌아서 찾으려 하던 3을 찾게 된다

선형 탐색의 장단점

마지막으로 선형 탐색 알고리즘에 장단점을 알아보자

장점:

1. 간단하고 직관적이기 때문에 이해하거나 구현하기 어렵지 않다는 큰 장점이 있다
2. 데이터가 정렬되어 있지 않거나 정렬하기 복잡한 상황에서 유용하다

단점:

1. 데이터가 크거나 검색해야 할 횟수가 많은 경우에는 시간이 많이 소요될되어 비효율적이다
2. 데이터의 크기가 커지면 커질수록 필요한 연산 횟수가 증가하기 때문에 확장성에 문제가 있다