읽고 나면 진짜 쉬워지는 자료 구조 - 8. 격자

다차원적인 값이나 대상을 고려할 때 어떤 일이 일어날까?

🔖 8.1 최근접 이웃 탐색 소개

최근접 이웃 탐색 이란?

• 주어진 탐색 목표와 가장 가까운 데이터 점을 찾는 것

• 이진 탐색에서 목표값 탐색과 밀접한 관련이 있으나, 차이는 '탐색에 성공하는 기준'

• 최근접 이웃 탐색은 단지 가장 가까운 항목을 찾기만 하면 된다

선형 스캔을 이용한 최근접 이웃 탐색

• 대부분의 프로그래밍 언어에서 간단한 루프로 구현 가능

• 다른 거리 함수나 다차원 점도 쉽게 지원

🔖 8.2 격자

격자란?

• 2차원 데이터를 저장하기 위한 자료 구조로, 배열과 마찬가지로 고정된 일련의 셀로 구성

• 배열과 달리 각 상자에 값을 하나만 답게 제한할 수 없음

• 데이터 점의 좌표를 이용해 각 저장소 결정

• 데이터의 공간 구조를 활용해 탐색 제한 가능

격자 구조

• 격자를 표현하는 최상위 자료 구조에는 관리를 위한 추가 정보 포함됨

• 격자를 만들 때는 데이터 점에 대해 for 루프 수행하면 됨

점 제거하기

• 상자에서 어떤 점을 제거해야 하는지 결정하는 것이 어려움

• 올바른 상자를 찾고 연결 리스트를 순회하며 같은 점을 찾고, 리스트에서 제거

🔖 8.3 격자에 대한 탐색

상자 가지치기

• 어떤 상자에 목표점과 주어진 거리 안에 있는 점이 하나라도 존재하는지 여부 확인

• 각 차원을 독립적으로 고려하면 어떤 점과 격자 상자의 경계 사이 거리 계산 가능

확장 탐색

• 목표점을 포함하는 상자에서 탐색 범위를 확장하며 최근접 이웃을 찾을 때까지 탐색 진행

• 상자에 대해 이상적인 확장 탐색 방법