알고리즘 실습: Python을 이용한 Linear Search 😎
Source: Dev.to
선형 탐색이란? 🤔
Linear search는 target이라고 부르는 값을 리스트(목록) 안에서 시작부터 끝까지 하나씩 요소를 검사하면서 찾는 방법입니다.
- 찾으면 → 해당 위치(index)를 반환합니다.
- 못 찾으면 → “없어요!” 라고 알려줍니다 (보통
-1을 반환).
장점: 매우 간단하고 리스트가 정렬돼 있을 필요가 없습니다.
단점: 리스트가 아주 길면 느립니다 (target이 마지막에 있거나 없을 경우 모든 요소를 검사해야 함).
위 그림은 선형 탐색이 어떻게 동작하는지 보여줍니다: 인덱스 0부터 시작해 하나씩 검사하면서 target을 찾습니다.
선형 탐색 작동 방식 단계별 📝
예시 리스트: [10, 20, 30, 40, 50] 와 target: 30
- 인덱스 0부터 시작:
10 == 30? 아니오. - 인덱스 1:
20 == 30? 아니오. - 인덱스 2:
30 == 30? 네! 인덱스 2에서 찾음.
target이 60인 경우: 끝까지 모두 검사 → 찾지 못함.
이 그림은 탐정이 사라진 물건을 찾는 것처럼, 단계별로 자세히 보여줍니다! 🕵️♂️
파이썬 구현 🐍
우리는 linear_search라는 간단한 함수를 만들겠습니다.
def linear_search(arr, target):
for i in range(len(arr)): # Loop dari 0 sampai panjang list - 1
if arr[i] == target: # Kalau elemen ke‑i sama dengan target
return i # Kembalikan index‑nya
return -1 # Kalau loop selesai berarti tidak ketemu예제 1: 정수 리스트에서 숫자 찾기 👍
daftar_angka = [15, 7, 23, 42, 9, 31]
target = 23
hasil = linear_search(daftar_angka, target)
if hasil != -1:
print(f"Ketemu! {target} ada di index {hasil}")
else:
print(f"{target} nggak ada di list 😢")Output: Ketemu! 23 ada di index 2
예제 2: 문자열 리스트(과일 이름)에서 문자 찾기
daftar_buah = ["Apel", "Pisang", "Jeruk", "Mangga", "Durian"]
target = "Mangga"
hasil = linear_search(daftar_buah, target)
if hasil != -1:
print(f"Yummy! {target} ada di urutan ke-{hasil + 1} (index {hasil})")
else:
print("Buahnya habis stok 😭")Output: Yummy! Mangga ada di urutan ke-4 (index 3)
예제 3: 찾지 못함 (Return -1)
daftar_hewan = ["Kucing", "Anjing", "Kelinci", "Burung"]
target = "Singa"
hasil = linear_search(daftar_hewan, target)
if hasil != -1:
print(f"Ketemu hewan {target}!")
else:
print(f"{target} nggak ada di kebun binatang ini 🦁")Output: Singa nggak ada di kebun binatang ini 🦁
예제 4: 빈 리스트 또는 처음/끝에 있는 타깃
# Target di awal
list1 = [100, 200, 300]
print(linear_search(list1, 100)) # Output: 0
# Target di akhir
print(linear_search(list1, 300)) # Output: 2
# List kosong
list_kosong = []
print(linear_search(list_kosong, 5)) # Output: -1보너스: 이진 탐색과 비교 🔍
선형 탐색은 리스트가 작거나 정렬되지 않았을 때 적합합니다. 리스트가 이미 정렬돼 있다면, 이진 탐색이 더 빠릅니다 (마치 사전을 중간부터 펼치는 것처럼).
위 그림은 차이를 보여줍니다: 선형 탐색은 모든 요소를 검사하고, 이진 탐색은 절반씩 줄여가며 탐색합니다.
당신을 위한 연습! 💪
- 코드를 수정해서 함수가 target이 몇 번 등장하는지 반환하도록 해보세요 (중복이 있을 경우).
- 친구들의 이름 리스트에 선형 탐색을 적용하고, 자신의 이름을 찾아보세요.
- 타이밍 테스트: 예를 들어 1000개의 요소가 있는 큰 리스트를 사용하고
time모듈로 실행 시간을 측정해 보세요.
실습을 마치고 나면 선형 탐색을 이해한 것이며, 숙련된 프로그래머에 한 걸음 더 다가선 것입니다. 궁금한 점이 있으면 언제든 물어보세요 또는 직접 실험해 보세요. 즐거운 코딩 되세요! 🎉🐍