[CS-007][중급] 정렬과 검색을 함께 설계하기 > IT 기술 공유

• 목록

[이번 수업]
데이터를 순서대로 놓는 정렬과 원하는 값을 찾는 검색은 함께 설계해야 합니다. 이번에는 선형 검색과 이진 검색의 차이, 정렬 기준과 안정성, 여러 번 검색할 때 전체 비용을 Python 예제로 확인합니다.

[선수지식]
CS-004의 배열·리스트, CS-005의 해시맵, CS-006의 시간복잡도 개념을 알고 Python 리스트와 함수를 사용할 수 있어야 합니다.

[학습목표]
1. 선형 검색과 이진 검색의 전제 조건을 구분한다.
2. 정렬 키와 안정 정렬의 의미를 설명한다.
3. 정렬된 목록에서 `bisect_left`로 값을 안전하게 찾는다.

[핵심개념]
정렬은 데이터를 점수·날짜·이름 같은 기준에 따라 배치하는 과정입니다. Python의 `sorted()`는 원본을 바꾸지 않고 새 리스트를 만들며, `list.sort()`는 기존 리스트를 직접 바꿉니다. `key`에는 각 항목에서 비교 기준을 꺼내는 함수를 전달합니다. Python 정렬은 안정적입니다. 안정 정렬이란 기준값이 같은 항목들의 원래 순서가 유지된다는 뜻입니다.

선형 검색은 앞에서부터 하나씩 비교하므로 정렬되지 않은 목록에도 쓸 수 있습니다. 최악에는 n개를 모두 확인해 O(n)입니다. 이진 검색은 가운데 값과 비교할 때마다 탐색 구간을 절반으로 줄여 O(log n)이지만, 반드시 같은 기준으로 정렬된 데이터가 필요합니다. 정렬되지 않은 목록에 적용하면 실행은 되더라도 답을 믿을 수 없습니다.

선택은 한 번의 함수 속도보다 전체 작업으로 판단합니다. 조회가 한두 번이면 선형 검색이 단순할 수 있습니다. 같은 데이터를 반복 조회한다면 한 번 정렬한 뒤 이진 검색하는 편이 유리할 수 있습니다. 정확한 키를 자주 찾는다면 CS-005의 딕셔너리도 후보입니다. Python 공식 문서는 `insort()`가 위치를 O(log n)에 찾아도 리스트 삽입이 O(n)이므로 전체 삽입 비용은 O(n)이라고 설명합니다.

[따라하기]
아래 내용을 search_demo.py로 저장합니다. 점수순으로 정렬한 뒤 82점의 첫 위치를 찾습니다.

```python
from bisect import bisect_left

records = [
    {"name": "민수", "score": 82},
    {"name": "서연", "score": 95},
    {"name": "지우", "score": 82},
    {"name": "현우", "score": 70},
]

ordered = sorted(records, key=lambda item: item["score"])
scores = [item["score"] for item in ordered]
target = 82
index = bisect_left(scores, target)

print([(item["name"], item["score"]) for item in ordered])
if index < len(scores) and scores[index] == target:
    print("첫 82점:", index, ordered[index]["name"])
else:
    print("없음, 들어갈 위치:", index)
```

macOS·Linux에서는 `python3 search_demo.py`, Windows PowerShell에서는 보통 `python search_demo.py`로 실행합니다. 예상 결과는 다음과 같습니다.

```text
[('현우', 70), ('민수', 82), ('지우', 82), ('서연', 95)]
첫 82점: 1 민수
```

82점인 민수와 지우의 원래 순서가 유지되어 안정 정렬을 확인할 수 있습니다. `bisect_left`는 값 자체가 아니라 정렬 순서를 유지할 삽입 위치를 반환합니다. 따라서 인덱스 범위와 실제 값이 목표와 같은지 모두 확인해야 합니다. 같은 값이 여러 개면 가장 왼쪽 위치를 돌려줍니다.

[흔한 실수]
- 정렬하지 않았거나 다른 키로 정렬한 목록에 이진 검색을 적용한다.
- `bisect_left`가 돌려준 위치에 목표값이 있다고 바로 가정한다.
- `sorted()`가 원본도 바꾼다고 생각하거나 `list.sort()`의 반환값을 새 리스트로 저장한다.
- 검색 한 번만 보고 정렬·삽입·메모리 비용을 제외한다.

[보안 주의]
외부 입력의 항목 수와 문자열 길이에 상한을 두어 큰 정렬 작업으로 CPU와 메모리가 고갈되지 않게 합니다. 숫자 필드는 범위를 확인하고 `None`, 숫자, 문자열처럼 비교할 수 없는 형식이 섞이지 않게 검증하세요. 정렬 키를 입력 문자열로 실행하려고 `eval()`을 사용하지 말고, 허용한 키 이름을 미리 정의한 함수에 연결합니다. 실습 데이터는 본인 로컬 파일만 사용합니다.

[직접 해볼 과제]
목표 점수를 90으로 바꿔 “없음, 들어갈 위치”를 확인하세요. 이어서 `key=lambda item: (item["score"], item["name"])`로 바꾸고 동점자의 이름순이 어떻게 달라지는지 예상 결과와 비교합니다.

[확인문제]
1. 이진 검색 전에 데이터가 정렬되어 있어야 하는 이유는 무엇인가요?
2. 안정 정렬은 기준값이 같은 항목을 어떻게 다루나요?
3. `bisect_left` 뒤에 값이 같은지 다시 검사해야 하는 이유는 무엇인가요?

[다음 학습]
다음 TOOL-007에서는 중단점과 변수 관찰로 정렬·검색 코드의 실행 흐름을 디버깅합니다.

[공식 참고 자료]
- Python 정렬 방법: https://docs.python.org/3/howto/sorting.html
- Python bisect 모듈: https://docs.python.org/3/library/bisect.html
- NIST 순차 검색 정의: https://xlinux.nist.gov/dads/HTML/sequentialSearch.html
- NIST 이진 검색 정의: https://xlinux.nist.gov/dads/HTML/binarySearch.html