[9주차] 공간 트리

[ainochi-kor]

공간 트리에 대해서 알아보기로 해요!

[ainochi-kor]

정리

이제 슬슬 이해의 영역을 넘어섰네요. 🤔
공간 트리의 활용 용도를 보면 게임 같은 곳에 많이 쓰일 것 같아서 관심이 가는데
면접을 앞두고 있어서 그런지 눈에 잘 안들어오는 것 같기도 하네요ㅠ
반성합니다ㅠ

[sunhpark42]

면접 화이팅입니다다~

[ella-yschoi]

면접 화이팅 입니닷!

[thgr8ganzi]

화이팅입니다

[hanana1253]

면접 화이팅!!!!!!!!!!!!!!!!

[sunhpark42]

• 솔직히 이거 맨처음 이론 얘기하던 학자들 신났을 것 같다. 이거 해결하려고 격자 쓸 수 있어! 근데 격자 이게 비효율적이네? 이렇게 해보자! 근데 분포상 굳이 균일할 필요있어? 이렇게 효율화 하자! 이런 흐름으로 발전한 느낌이랄까. 세상은 항상 발전하고 파악해야 하는 데이터가 많아질 수록 어떻게 다룰 지 고민하고 그걸 해결하기 위한 방법을 찾아낸게 참 대단하면서도 변태같다. (ㅋㅋㅋ)
• 근데 여전히 내가 다루는 분야에서 어떻게 쓰일지 모르겠음.
• 공간적 자료구조로만 한 권을 채운 책이 있을까? 했는데 지리정보를 위해 많이 쓰나보다. 전공책으로 있었다.
• 확실히 관심 분야는 아니긴 했지만, 이런 사고 발전과정이 재밌는 듯, 언젠가 관련해서 하게된다면 생각나서 어떤걸 공부할 지 알게 된 것 같다. 트레이드 오프 재밌는데 어려웡~
• 오늘의 문장: 컴퓨터 과학에서 거의 모든 것과 마찬가지로, 각 접근 방식은 프로그램의 복잡성, 계산 비용, 메모리 사용과 관련된 고유한 트레이드오프 관계가 존재한다. 쿼드 트리와 k-d 트리는 어떻게 하면 최근접 이웃 탐색의 공간적 가지치기와 트리 기반 자료 구조를 결합해서 공간 트리를 우리가 가진 데이터에 맞게 적응시킬 수 있는지를 보여주는 우수한 예다.
  (알라딘 eBook <읽고 나면 진짜 쉬워지는 자료 구조 > (제레미 쿠비카 지음, 오현석 옮김) 중에서)

[sa02045]

정리

• 균일쿼드트리:
  • 2D 전용. 공간을 균일하게 4분할.
  • 균일하게 분할했기 때문에 메모리 낭비, 공간 낭비가 있을 수 있음
• k-d트리: 다차원. 각 노드를 하나의 차원을 기준으로 분할함
  • 균일쿼드트리보다 유연함. 값을 구분할 때에도 더 유연
  • 엄격한 공간 경계로 가지치기가 더 효율적

9.1 쿼드 트리

• 데이터에 따라 공간을 동적으로 분할
• 필요할 때만 추가 구조를 도입하여 부가 비용을 최적화한다
• 균일 쿼드 트리의 각 노드는 4개의 동일한 크기 사분면으로 분할된다. 비어 있지 않은 사분면마다 노드가 할당된다.
• 쿼드 트리 내부 노드는 메타 데이터와 함께 최대 4개의 자식 포인터를 저장한다.
• 할당된 공간을 더 작은 하위 영역으로 재귀적으로 분할하는 방식이다. 언제 분할을 중지하고 리프노드로 지정할지 결정하는 추가 논리가 필요하다.
• 가장 일반적인 방법은
  • 분할을 정당화할 만큼 충분한 점이 있는지?
  • 공간의 경계가 충분히 큰지?
  • 최대 깊이에 도달했는지?
• 노드에 점을 추가하는 것은 새로운 점의 위치를 찾기 위해 트리를 탐색하는 것으로 이루어짐
• 이 탐색은 리프 노드나 내부의 막다른 골목중 하나로 끝날 수 있음. 리프 노드에서 탐색이 중단되면 그 위치에 점을 추가하거나 분할 기준에 따라 노드를 하위 노드로 분할 할수도 있음
• 최근접 이웃 탐색
  • 각 노드에서 현재 후보보다 더 가까이 있는 점이 포함될 수 있는지를 먼저 확인한다.
    • 포함될 수 있다면 재귀적으로 탐색, 그렇지 않다면 가지치기
    • 점의 위치와 노드의 경계사이의 거리로 판독하기

9.2 k-d 트리

• 다차원 데이터를 다루려면 쿼드 트리는 한계가 있다.
• 차원 수가 늘어날 수록 확장하기 어렵기 때문이다.
• 더 높은 차원에 대해 효과적인 트리 확장을 하려면 가지를 뻗어나가는 비율을 조절해야한다.
• 이를 가능하게 하는 자료구조가 k-d 트리이다.

k-d 트리

• k-d 트리는 쿼드 트리의 공간 분할과 이진 탐색 트리의 뻗어나가는 특성을 결합한다.
• 모든 수준에서 모든 차원으로 공간을 분할하는 대신, k-d 트리는 한 차원을 선택해서 해당 차원을 기준으로 데이터를 분할한다.
• 각 내부 노드는 데이터를 정확히 두 자식으로 분할한다.
  • 왼쪽 노드는 분할 값보다 작은 점들, 오른쪽 자식은 분할 값보다 더 큰 점들
• k-d 트리는 쿼드 트리보다 더 유연하게 데이터 구조에 대응할 수 있다.
• 중앙값을 기준으로 공간을 분할해야한다는 제약이 없기 때문이다. 균일한 크기의 격자 상자로 공간을 분할하는 대신, 각 노드에서 데이터를 분할하기에 가장 적합한 차원과 분할 값을 선택할 수 있다.
• 따라서 각각의 내부 노드는 분할하는 차원과 분할의 기준이 되는 값을 모두 저장한다.
• 각 노드에서 데이터 구성을 기반으로 분할을 선택하면 탐색을 더 쉽게 해주는 트리 구조를 원하는 대로 만들어 낼 수 있다.
• k-d 트리의 노드는 전체 탐색 공간의 초직사각형을 이룬다.
• 복잡성 때문에 k-d 트리 노드는 상당한 양의 정보를 저장한다.

[ella-yschoi]

정리

어려운 개념이긴 했으나 마지막 9.3 핵심 정리가 잘 요약해준 것 같아요.
책 설명은 좀 어려웠지만 이것저것 찾아보고 더 쉽게 이해할 수 있었네요 (그래도 아직 어려움..)
100% 이해를 못했지만 그래도 한번쯤 읽고 이런 것이 있구나~ 한 것에 의의를 둡니다!

[thgr8ganzi]

정리?

• 이번장은 훨훨 넘겼습니다.(이런게 있구나~)
• 자료구조 너무 어려워요~~

[hanana1253]

공간 트리

• 균일 쿼드트리(uniform quadtree)
  • 격자 구조를 반영하는 동일한 크기의 하위 영역 사용
• k-d 트리
  • 데이터에 맞게 적응할 수 있고 더 높은 차원으로 확장할 수 있는 더 유연한 이진 분할 체계 사용

1. 쿼드 트리

• 격자의 trade off: 공간을 얼마나 세밀하게 분할하느냐에 따라 좌우되는 격자의 부가 비용과 유용성 (메모리, 탐색 회수 vs. 선형 스캔과 비슷한 비용)
• 데이터에 따라 공간을 동적으로 분할: 필요할 때만 추가 구조를 도입, 부가비용도 필요할 때만 추가
  • 트리의 분기 구조를 격자에 도입
  • 노드가 공간을 똑같은 크기의 하위 공간으로 분할: 할당된 공간을 점점 더 작은 하위 영역으로 재귀적으로 분할
• 언제 분할을 중지할지 결정하는 추가 논리 (하위 노드를 포함하는 내부 노드로 만들지, 점의 리스트를 포함하는 리프 노드로 만들지)
  • 분할을 정당화할 만큼 충분한 점이 있는지: 점이 너무 적으면 자식 노드까지의 거리를 확인하는 비용이 커진다.
  • 공간의 경계가 충분히 큰지: 같은 위치에 여러개의 점이 있으면 분할의 의미가 없음
  • 최대 깊이에 도달했는지: 정해둔 제한 기준을 넘었는지 검사
• 각 노드에 비어있지 않은 자식만 저장해 메모리를 절약

2. k-d 트리

• 쿼드 트리의 공간 분할과, 이진 탐색 트리의 2개 자식으로 뻗어나가는 특성을 결합
• 더 유연하게 데이터의 구조에 맞춰 대응 가능: 균일한 크기의 격자 상자가 아닌, 각 노드에서 가장 적합한 차원과 분할 값 선택
• 각 k-d 트리 노드는 상당한 양의 정보를 저장하는 비용이 들지만, 트리의 성능과 유연성에 의해 비용이 상쇄된다
• 노드의 전체 공간 경계 대신, 노드 안에 포함된 모든 점을 둘러싸는 최소 상자로 경계를 정의하여 공간 트리의 가지치기 효과 개선 가능

3. 쿼드 트리와 k-d 트리가 중요한 이유

• 동적 자료 구조의 강력함과 탐색 문제의 공간 구조를 결합
• 공간적 가지 치기와 트리 기반 자료 구조를 결합하여 공간 트리를 우리가 가진 데이터에 맞게 적응시키는 사례

느낀점

• 지난 주 8장 중간까지만 하고 슬쩍 넘어가려고 했더니 8장에 기반한 내용 + 이진 트리까지 적용되다니 신기
• 뭔 말이여 하면서 읽었는데 아무튼 개념 정도만 알 것 같다.
• 여담) 현 직장 입사 코딩테스트에 쿼드 트리가 나왔었는데.. 당연히 못 풀었다.

[ella-yschoi]

오우 코테에 쿼드트리가!! 그랬군요.....

[chloe-codes1]

내용 정리

쿼드 트리

• 격자의 한계
  • 많은 격자 상자를 사용하면 메모리 사용량이 많아지고, 탐색해야 할 상자의 개수도 증가
  • 격자를 너무 거칠게 분할하면, 각 상자에 많은 점이 포함되어 선형 탐색과 비슷한 성능을 보일 수 있음
  • 데이터에 따라 공간을 동적으로 분할하는 방식이 필요하며, 이를 해결하기 위해 균일 쿼드 트리가 사용됨
• 균일 쿼드 트리
  • 트리의 분기 구조를 격자에 적용하며, 각 노드는 특정 공간을 나타냄
  • 공간을 점점 더 작은 하위 영역으로 재귀적으로 분할하여 구성됨
  • 새로운 점을 추가할 때는 트리를 탐색하여 올바른 위치를 찾음
• 균일 쿼드 트리 탐색
  • 탐색은 루트 노드에서 시작
  • 현재 후보보다 더 가까운 점이 있는지를 먼저 확인한 후 탐색 진행
  • 가장 짧은 거리로 목표 위치에 도달할 수 있는 방향을 결정하는 데 활용됨

k-d 트리

• 구조
  • 쿼드 트리와 유사한 개념을 기반으로 하며, 공간 분할 방식과 이진 탐색 트리의 구조를 결합한 자료구조
  • 특정 차원을 기준으로 데이터를 분할하며, 노드가 많은 정보를 저장해야 하므로 설계 시 주의가 필요함
• 생성 과정
  • 이진 탐색 트리와 유사한 방식으로 재귀적으로 구축됨
  • 중복 데이터로 인해 무한 재귀가 발생하는 것을 방지하기 위해 특정 검사 방식을 적용함
  • 각 레벨에서 분할할 차원을 하나만 선택하는 것이 특징
• 연산
  • 주요 연산으로는 삽입, 제거, 탐색이 있으며, 쿼드 트리와 유사한 방식으로 수행됨
  • 트리의 최상위 노드에서 시작하여, 분할 값을 기준으로 적절한 자식 노드를 선택해 탐색함
  • 특정 사분면을 탐색하는 쿼드 트리와 달리, 두 개의 자식 중 하나를 선택하는 방식으로 동작

쿼드 트리와 k-d 트리의 중요성

• 쿼드 트리의 장점
  • 다차원 데이터를 저장할 때, 지역적인 데이터 밀도에 따라 격자의 해상도를 조절할 수 있음
  • 공간을 효율적으로 분할하여 데이터 탐색 속도를 높일 수 있음
• k-d 트리의 장점
  • 최근접 이웃 탐색 문제를 해결하는 데 효과적임
  • 적응형 가지치기를 통해 다양한 데이터 구조에 유연하게 대응