이 페이지는 강의 외 추가 강의예요. V단원에서 배운 순차·이진 탐색을 게임의 아이템 ID로 이름 찾기, 정렬된 스킬 테이블에서 번호로 검색 같은 구체적인 시스템으로 확장합니다. 자료구조 복기 → 사용 API → 실제 구현 활용 순으로 짚어요.
이진 탐색 — 정렬된 테이블에서 빠르게 찾기
게임에서 "아이템 ID 12번의 이름이 뭐지?", "스킬 번호 5의 설명은?"처럼 정렬된 테이블에서 번호(키)로 정보를 찾을 때 이진 탐색이 쓰여요. 순차 탐색은 정렬이 없어도 되지만 느리고, 이진 탐색은 정렬돼 있어야 하며 빠릅니다.
📌 복기: 이진 탐색
- 조건: 자료가 이미 오름차순(또는 내림차순)으로 정렬되어 있을 때만 사용.
- 방법: 현재 구간의 가운데 값을 보고, 찾는 값이 더 크면 오른쪽 절반만, 더 작으면 왼쪽 절반만 다시 탐색. 반씩 버리므로 빠름.
- 자료구조는 배열(리스트). 연산은 "가운데 인덱스 계산"과 "구간 좁히기(left/right 갱신)".
📌 사용하는 파이썬 API
mid = (left + right) // 2- 정수 나눗셈으로 가운데 인덱스를 구해요. 인덱스는 항상 정수여야 하므로 //를 씁니다.
left = mid + 1,right = mid - 1- 찾는 값이 arr[mid]보다 크면 오른쪽 절반만 보면 되므로
left = mid + 1. 더 작으면right = mid - 1로 구간을 줄여요. 리스트[mid]- mid번째 칸의 값. 이 값과 target을 비교해서 "같으면 찾음", "target이 더 크면/작으면" 구간을 좁혀요.
🎮 실제 구현에서 쓰는 곳
- 아이템/스킬 테이블: ID가 1, 2, 3, … 순으로 정렬된 테이블에서 "ID 12번 아이템 이름"을 찾을 때. 리스트를 (id, name) 쌍으로 두고 id로 정렬해 두면, 이진 탐색으로 12번이 몇 번째 인덱스인지 찾은 뒤 name을 반환.
- 정렬된 데이터가 전제: 게임 데이터를 "ID순"으로 미리 정렬해 두면, 런타임에 이진 탐색으로 로그 N 번만에 찾을 수 있어요.
🐍 실습: 이진 탐색
게임에서 "ID 12번 스킬 이름"을 찾는다면, 스킬 리스트를 ID순으로 정렬해 두고 위와 같이 target=12로 이진 탐색한 뒤, 찾은 인덱스의 "이름" 필드를 화면에 표시하면 됩니다.