Grid

title: 2025-09-05 author: 강병호 date: 2025-09-05 category: TIL/강병호/2025/08 layout: post —

Grid 공간분할

해당 기법의 핵심철학은 다음과 같다.

멀리 있어서 절대 닿을 수 없는 대상은 아예 비교 대상에서 제외하자.

Grid란?

넓은 지도 위, 일정한 간격으로 선을 그어 여러 개의 작은 구역(Cell)을 나누는 것

예를 들어 30000 개의 데이터가 존재하면 30000번 호출이 되고 공간 NN의 경우 3000030000 을 비교하게 된다. 이런 전체 공감을 작은 셀들로 분할하여, 내가 필요한 정보가 있는 구역만 집어서 탐색하는 ㄴ것이다.

설계 방식

셀의 크기를 얼마로 할지.

탐색 범위의 크기(M)이 절대적인 기준치가 된다.

탐색 범위의 크기가 5라면 셀의 크기는 55 가 된다. 이렇게 셀의 크기가 55 가 되어 줄여진 범위에서는 3*3 구역안에만 다른 닿을 수 있는 정보들이 존재하게 된다.

그리드 정보의 저장 방법

• 2차원 배열 : 비효율적. 텅 빈 셀들까지 모두 메모리를 차지하게 된다.
• 해시맵 : 존재하는 셀의 정보만 저장하기에 매우 효유루적이다.
  • Key : 각 셀의 고유 ID를 생성한다. 즉, 2차원 자표를 1차원으로 변환한다. cellKey = cellRow * (그리드의 가로 너비) + cellCol 해당 방식을 사용하면 겹치지 않는 자신만의 번호를 가지게 된다.
  • Value : 해당 셀에 포함된 정보들의 목록