알고리즘은 정해진 문제의 입력으로부터 원하는 결과를 얻기 위한 명확한 계산 절차이다. 어떤 문제를 푸는지, 어떤 입력을 허용하는지, 결과가 무엇을 뜻하는지를 함께 정의해야 한다. 알고리즘은 특정 프로그래밍 언어의 코드와 구별되며 같은 절차를 여러 언어로 구현할 수 있다.
명세부터 정하기
“값을 찾는다”는 말만으로는 결과가 충분히 정해지지 않는다. 같은 값이 여러 번 있을 때 첫 위치를 돌려줄지 모든 위치를 돌려줄지, 값이 없으면 어떤 표시를 할지를 결정해야 한다. 빈 입력을 허용하는지도 명세에 포함한다.
이 문서의 예제는 유한한 목록과 찾을 값을 받아 첫 번째 일치 위치를 돌려준다. 위치는 0부터 세고, 값이 없으면 -1을 반환한다고 정한다. 이런 약속을 먼저 두면 구현과 테스트에서 무엇이 맞는 결과인지 판단할 수 있다.
예시: 선형 탐색의 실행 과정
입력이 [8, 3, 8, 5]이고 찾을 값이 5라면 왼쪽에서 순서대로 비교한다. 위치 0의 8은 다르고, 위치 1의 3도 다르며, 위치 2의 8도 다르다. 위치 3의 5에서 처음 일치하므로 3을 반환한다.
찾을 값이 8이면 첫 비교에서 0을 반환한다. 나중의 위치 2까지 찾을 필요가 없다. 찾을 값이 4이면 모든 원소를 확인한 후 -1을 반환한다. 빈 목록에서도 비교할 원소가 없으므로 곧바로 -1이 된다. 같은 절차라도 입력 내용에 따라 비교 횟수는 달라진다.
예시 코드와 결과
다음 코드는 Python 3에서 실행할 수 있는 선형 탐색의 간결한 표현이다. enumerate는 위치와 값을 차례로 제공하고, 생성기 표현식은 일치하는 위치를 순서대로 만든다. next는 첫 위치를 얻고 없으면 기본값 -1을 사용한다. 출력은 3과 -1이다.
코드가 짧아도 검색 비용이 상수 시간이 되는 것은 아니다. next가 결과를 얻을 때까지 생성기 내부에서 원소를 비교한다. 이 예제의 핵심은 구현 문법의 길이와 수행하는 작업량이 다르다는 점이다.
values = [8, 3, 8, 5]
print(next((i for i, value in enumerate(values) if value == 5), -1))
print(next((i for i, value in enumerate(values) if value == 4), -1))정확성과 종료성
선형 탐색에서 현재 위치 앞의 원소를 모두 확인했고 그곳에는 목표 값이 없다는 조건을 유지할 수 있다. 다음 원소가 같으면 그 위치가 첫 일치이고, 다르면 검사한 구간을 한 칸 넓힌다. 끝까지 일치가 없으면 부재를 보고한다. 이런 방식으로 반복 중 유지되는 조건을 설명하면 단순히 “여러 번 돌려 보니 맞았다”보다 강한 근거가 된다.
반복이 언젠가 끝나는지도 따로 설명해야 한다. 유한한 목록에서 검사할 위치를 매번 한 칸씩 앞으로 이동시키면 남은 원소 수가 줄어들고 결국 종료한다. 결과가 맞을 것이라는 설명만 있고 종료 근거가 없으면 무한 반복 가능성을 놓칠 수 있다.
시간·공간 복잡도
길이 n인 목록에서 선형 탐색은 최악의 경우 n개를 확인하므로 시간 복잡도는 O(n)이다. 첫 원소가 목표 값인 경우에는 한 번만 비교한다. 최선·최악은 단순히 작은 입력과 큰 입력의 차이가 아니라 같은 크기의 입력에서 내용에 따라 필요한 작업이 달라지는 구분이다.
인덱스와 현재 값만 유지하는 구현은 입력 목록 외에 상수 크기의 보조 상태를 사용한다. 반면 모든 일치 위치를 모아 새 목록으로 반환하면 출력 공간이 필요하다. 복잡도를 말할 때는 입력과 출력 공간을 포함했는지, 원소 비교를 어떤 비용으로 보는지 밝혀야 한다.
자료구조와 전제 조건
정렬된 배열에는 이분 탐색을 적용해 후보 구간을 줄일 수 있다. 그러나 정렬되지 않은 입력에 이분 탐색을 그대로 적용하면 값을 놓칠 수 있다. 탐색 전에 정렬할 경우 정렬 비용과 원래 위치가 바뀌는 문제도 고려해야 한다.
같은 자료를 수없이 조회할 때는 별도 인덱스를 만드는 비용을 감수할 수 있지만 한 번만 조회할 작은 입력에서는 단순 선형 탐색이 충분할 수 있다. 알고리즘을 선택할 때 전처리, 갱신 빈도, 메모리와 필요한 결과를 함께 본다.
검증과 흔한 실수
빈 입력, 원소 하나, 첫 위치·마지막 위치의 일치, 값이 없는 경우, 중복값을 테스트한다. 테스트는 구현 오류를 찾는 데 유용하지만 모든 가능한 입력의 정확성을 자동으로 증명하지는 않는다.
빠른 구현을 찾기 전에 반환값과 경계 조건을 일관되게 정한다. -1을 부재 표기로 정했다면 이를 실제 인덱스로 바로 사용하지 않는다. 특히 Python에서 음수 인덱스는 끝에서부터의 위치를 뜻하므로 부재 검사를 빠뜨리면 엉뚱한 원소를 읽을 수 있다.