제로베이스 데이터사이언스 스쿨 - Part 05. 자료구조&알고리즘 with Python -22

Chapter 03. 알고리즘

선형 검색(Linear Search) 정리

 

 

1️⃣ 선형 검색이란?

 

선형 검색은 리스트(배열)의 처음부터 끝까지 순서대로 데이터를 하나씩 비교하며 원하는 값을 찾는 알고리즘이다.

• 데이터가 정렬되어 있지 않아도 사용 가능
• 구현이 매우 단순함
• 데이터 개수가 많아질수록 성능이 급격히 저하됨

즉, "앞에서부터 차례대로 다 확인해본다"는 가장 직관적인 검색 방식이다.

---

2️⃣ 선형 검색의 동작 방식

선형 검색의 기본 흐름은 다음과 같다.

1. 리스트의 첫 번째 요소부터 탐색을 시작한다.
2. 현재 요소와 찾고자 하는 값을 비교한다.
3. 값이 같으면 해당 위치(인덱스)를 반환한다.
4. 끝까지 찾지 못하면 검색 실패로 처리한다.

이 과정은 반복문(for, while)을 통해 구현된다.

---

3️⃣ 시간 복잡도

선형 검색의 시간 복잡도는 다음과 같다.

• 최선의 경우: O(1)
  • 첫 번째 요소가 바로 찾는 값인 경우
• 최악의 경우: O(n)
  • 마지막 요소이거나, 아예 없는 경우
• 평균 시간 복잡도: O(n)

이 때문에 데이터가 많고 검색이 잦은 경우에는 비효율적인 알고리즘이다.

---

4️⃣ 실습 문제 정리

실습 1: 숫자 7의 첫 번째 위치 찾기

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

for idx, num in enumerate(nums):
    if num == 7:
        print(idx)
        break

• enumerate()를 사용하면 인덱스와 값을 동시에 다룰 수 있어 가독성이 좋아진다.
• 첫 번째 7을 찾은 순간 반복문을 종료한다.

---

실습 2: 숫자 7의 모든 위치와 개수 찾기

nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]

count = 0
for idx, num in enumerate(nums):
    if num == 7:
        print(f"index: {idx}")
        count += 1

print(f"총 개수: {count}")

• 모든 요소를 끝까지 탐색해야 하므로 break를 사용하지 않는다.
• 조건을 만족할 때마다 개수를 누적한다.

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

선형 검색은 너무 단순해서 처음에는 굳이 알고리즘이라고 부를 필요가 있나 싶었다. 하지만 실습을 직접 해보면서, "모든 알고리즘은 결국 이 단순한 반복과 조건에서 출발한다"는 점이 인상 깊었다.

특히 첫 번째 값만 찾을 때와, 모든 값을 찾아야 할 때 로직이 어떻게 달라지는지를 코드로 직접 구현해보니, break 하나가 알고리즘의 동작 방식 자체를 바꾼다는 점이 명확하게 와닿았다. 또한 enumerate()를 사용하면 단순한 반복문도 훨씬 읽기 좋은 코드로 만들 수 있다는 점을 다시 한 번 체감했다.

이 실습은 성능보다도 문제 요구사항을 정확히 이해하고, 반복문의 흐름을 어떻게 제어할 것인가에 집중하게 만들어준 연습이었다.

---

🚀 적용점

• 정렬되지 않은 데이터에서 간단한 탐색 로직이 필요할 때 활용 가능
• 알고리즘 학습 초반에 반복문 + 조건문 사고 훈련용으로 매우 적합
• 이후 이진 검색, 해시 탐색 등 고급 탐색 알고리즘과의 비교 기준이 됨
• 실제 서비스 코드에서는 데이터 규모에 따라 반드시 다른 검색 방식과 비교 필요