선형 탐색(Linear Search) 알고리즘이란? (JAVA)

안녕하세요? 코딩중독입니다.

 

저번 시간에는 파일의 끝을 나타내는 EOF를 처리하는 방법에 대해 알아 보았습니다.

 

이번 시간부터는 알고리즘 문제 풀이에 실질적인 도움이 되는 글을 쓰려고 합니다.

 

그 첫 시간이 바로 선형 탐색 알고리즘입니다.

 

 

선형 탐색은 무엇일까?

선형 탐색(Linear Search)은 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 것을 말합니다.

 

가령, 다음과 같은 배열있다고 가정합시다.

 

 

 

 

그리고 우리가 찾고 싶은 수가 4라고 하면, 왼쪽부터 4가 있는지 하나씩 다 살펴봅니다.

 

맨 처음 3은 4와 같지 않으므로 그 다음 수인 7, 그 다음 수인 -1을 비교하다가 마지막으로 4번째로 4를 찾으면 탐색이 종료됩니다.

 

선형 탐색은 탐색 알고리즘의 가장 기초가 되는 알고리즘으로 구현하기 매우 쉽다는 장점이 있지만, 반대로 배열의 크기가 커질수록 찾는 시간이 오래 걸린다는 단점이 있습니다.

 

최악의 경우 마지막 요소까지 탐색해야하므로 시간 복잡도는 O(N)을 갖습니다.

 

 

이제, 위 과정을 소스코드로 표현해 보겠습니다.

 

 

소스코드

 

 

정리

지금까지 선형 탐색 알고리즘에 대해 알아 보았습니다.

 

구현이 아주 easy하다는 장점이 있지만, 시간 복잡도가 효율적이지 않다는 단점이 있었습니다.

 

다음 시간에는 이러한 단점을 보완하는 이진 탐색 알고리즘에 대해 알아 보겠습니다.

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

 

 

 

 

이 포스팅과 관련된 다른 글도 읽어 보세요.

 

[PS/이론] - EOF의 사용 방법을 알아보자 (JAVA)

[PS/이론] - BufferedReader와 BufferedWriter의 사용법 (JAVA)

[PS/이론] - 당신이 PS에서 Scanner를 쓰면 안 되는 이유 (JAVA)