🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)
이진 탐색 트리(BST) = 정렬된 키로 빠르게 찾기·넣기·빼기가 필요할 때 씁니다. 스킬 ID·아이템 ID를 키로 두면 "ID 12번 스킬 이름 찾기"가 로그 시간에 가능해요. 해싱 = 이름으로 바로 찾기. "물약"이라는 문자열을 해시 함수로 칸 번호로 바꿔서 저장해 두면, 이름으로 검색할 때 평균 O(1)에 찾을 수 있어요. 아이템 이름→ID 매핑에 자주 씁니다.
이진 탐색 트리(BST, 비에스티)
트리로 만든 구조에서, 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 지키면 찾기·넣기·빼기가 모두 편해요. 중위 순회하면 정렬된 순서로 나와요. 프로그래밍기능사 실기에서 트리 순회·탐색이 나올 수 있어요.
해싱(Hashing, 해싱)
"키(key, 키)"(이름, 번호 등)를 해시 함수(hash function)로 계산해서 "저장할 칸 번호"를 정하는 방법이에요. 같은 칸에 두 값이 들어가면 충돌이라고 하고, 이걸 푸는 방법이 체이닝(chaining, 체이닝)(리스트로 연결), 개방 주소법(다른 빈 칸 찾기)이에요. 시험에 나올 수 있어요.
📌 이론(알고리즘) ↔ 파이썬 표현 (배열 이진 탐색)
이진 탐색 가운데 인덱스 → mid = (left + right) // 2 | 구간 좁히기 → left = mid + 1 / right = mid - 1
대응 이진 탐색은 "현재 구간의 가운데 인덱스"를 구하고, 찾는 값과 비교해서 절반만 남기며 반복해요.
(left + right) // 2- 정수 나눗셈 //로 가운데 인덱스를 구해요. 인덱스는 정수여야 하므로 /가 아니라 //를 씁니다.
리스트[mid]- mid번째 칸의 값. 이 값과 target을 비교해서 "같으면 찾음", "target이 더 크면 오른쪽 절반", "더 작으면 왼쪽 절반"으로 구간을 좁혀요.
left = mid + 1/right = mid - 1- target이 arr[mid]보다 크면 오른쪽 절반만 보면 되므로
left = mid + 1. 더 작으면right = mid - 1로 줄여요.
왜 이렇게 쓰나요? 이진 탐색의 핵심은 "매번 가운데를 보고 절반을 버리는 것"이에요. //와 left/right 갱신이 그대로 코드에 반영됩니다.