[UNITY]/TIL: UNITY

[Unity]자료구조 & 알고리즘

네,가능합니다 ㅣ 2024. 12. 23. 11:40

최근엔 면접에 자주 등장하는 자료구조, 알고리즘 등에 대해 작성하게 되는 것 같다.

그러면서 몰랐던 사실도 알게되고 궁금했던것도 알게되면서 재미도 있는것같다. 바로 시작해보자.

 

 

1. LinkedList (연결 리스트)

1.1. LinkedList의 특성

  • 노드 기반 구조: LinkedList는 노드로 구성됩니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다. (단일 연결 리스트 기준, 이중 연결 리스트는 이전 노드 포인터도 포함)
  • 동적 크기: 배열과 달리 크기가 고정되어 있지 않아, 삽입/삭제가 자유롭습니다.
  • 삽입/삭제 효율성: 특정 위치에 노드를 삽입하거나 삭제하는 연산이 배열에 비해 효율적입니다. (시간 복잡도: O(1) - 단, 해당 위치를 이미 알고 있는 경우)
  • 임의 접근 비효율성: 특정 인덱스의 요소에 접근하려면 처음부터 순차적으로 탐색해야 합니다. (시간 복잡도: O(n))

1.2. LinkedList 사용 적합/부적합 상황

  • 적합:
    • 삽입/삭제가 빈번하게 발생하는 경우 (예: 대기열, 이벤트 목록)
    • 데이터의 크기가 유동적인 경우
    • 순차적인 접근이 주를 이루는 경우
  • 부적합:
    • 임의 접근이 빈번한 경우 (예: 인덱스를 통한 빈번한 데이터 접근)
    • 데이터 크기가 작고 고정적인 경우 (배열이 메모리 관리 측면에서 유리)

1.3. 프로젝트 적용 경험(버프관리 등)

  • 적용 사례: 게임 내 실시간으로 발생하는 이벤트들을 관리하는 이벤트 목록에 LinkedList를 사용. 이벤트가 발생할 때마다 리스트에 추가하고, 처리 후 삭제하는 방식으로 구현.
  • 경험: 배열을 사용할 경우, 빈번한 삽입/삭제로 인해 메모리 재할당 및 데이터 복사 비용이 컸을 것. LinkedList 사용으로 삽입/삭제 성능을 향상시킴.

1.4. 추가 학습 내용

  • 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트의 차이점 및 장단점
  • LinkedList의 메모리 사용 방식 및 가비지 컬렉션과의 관계

2. Stack (스택)

2.1. Stack의 특성

  • LIFO (Last-In, First-Out): 후입선출 구조. 마지막에 추가된 요소가 가장 먼저 제거됩니다.
  • Push & Pop: 스택에 요소를 추가하는 연산을 Push, 제거하는 연산을 Pop이라고 합니다.
  • Top: 스택의 가장 위에 있는 요소를 가리킵니다.

2.2. Stack 사용 적합/부적합 상황

  • 적합:
    • 함수 호출 관리 (Call Stack)
    • Undo/Redo 기능 구현
    • 후위 표기법 계산
    • 깊이 우선 탐색 (DFS)
  • 부적합:
    • 임의 접근이 필요한 경우
    • 데이터의 순서가 중요한 경우 (예: 작업 대기열)

2.3. 프로젝트 적용 경험

  • 적용 사례: 플레이어의 행동을 기록하여 Undo/Redo 기능을 구현하는 데 Stack을 사용. 플레이어의 행동을 객체로 만들어 Stack에 Push하고, Undo 시에는 Pop하여 이전 상태로 복원.
  • 경험: Stack의 LIFO 특성을 활용하여 자연스럽게 Undo/Redo 기능을 구현할 수 있었음.

2.4. 추가 학습 내용

  • Stack Overflow 에러의 원인 및 해결 방법
  • Stack을 이용한 재귀 함수의 비재귀적 구현 방법

3. Queue (큐)

3.1. Queue의 특성

  • FIFO (First-In, First-Out): 선입선출 구조. 먼저 추가된 요소가 가장 먼저 제거됩니다.
  • Enqueue & Dequeue: 큐에 요소를 추가하는 연산을 Enqueue, 제거하는 연산을 Dequeue라고 합니다.
  • Front & Rear: 큐의 가장 앞에 있는 요소를 Front, 가장 뒤에 있는 요소를 Rear라고 합니다.

3.2. Queue 사용 적합/부적합 상황

  • 적합:
    • 작업 대기열 (예: 네트워크 요청, 인쇄 작업)
    • 버퍼 구현
    • 너비 우선 탐색 (BFS)
  • 부적합:
    • 임의 접근이 필요한 경우
    • LIFO 방식의 처리가 필요한 경우

3.3. 프로젝트 적용 경험

  • 적용 사례: 네트워크 멀티플레이어 게임에서 플레이어의 입력을 순차적으로 처리하기 위해 Queue를 사용. 플레이어의 입력 데이터를 Enqueue하고, 서버에서 순서대로 Dequeue하여 처리.
  • 경험: Queue를 사용하여 입력 순서를 보장하고, 공정한 게임 플레이를 유지할 수 있었음.

3.4. 추가 학습 내용

  • Circular Queue (원형 큐)의 장점 및 구현 방법
  • Priority Queue (우선순위 큐)의 개념 및 활용 사례

4. Tree Traversal (트리 순회)

4.1. 트리 순회 방법

  • Inorder (중위 순회): Left - Root - Right 순서로 방문 (주로 이진 탐색 트리에서 사용)
  • Preorder (전위 순회): Root - Left - Right 순서로 방문 (트리 복사, 식 트리 계산 등에 사용)
  • Postorder (후위 순회): Left - Right - Root 순서로 방문 (트리 삭제, 디렉토리 용량 계산 등에 사용)
  • Level Order (레벨 순회): 루트 노드부터 계층별로 방문 (너비 우선 탐색과 동일)

4.2. 추가 학습 내용

  • 각 순회 방법의 재귀적, 비재귀적 구현 방법
  • 특정 순회 결과가 주어졌을 때, 트리 구조를 유추하는 방법

5. DFS & BFS

5.1. DFS (Depth-First Search, 깊이 우선 탐색)

  • 특징: 하나의 경로를 끝까지 탐색한 후, 다음 경로로 넘어가는 방식.
  • 구현: Stack 또는 재귀 함수를 사용.
  • 장점: 메모리 사용량이 상대적으로 적음 (탐색 깊이가 깊지 않은 경우).
  • 단점: 최단 경로를 보장하지 않음. 무한 루프에 빠질 위험이 있음 (방문 노드 체크 필수).

5.2. BFS (Breadth-First Search, 너비 우선 탐색)

  • 특징: 시작 노드에서 가까운 노드부터 순차적으로 탐색하는 방식.
  • 구현: Queue를 사용.
  • 장점: 최단 경로를 보장.
  • 단점: 메모리 사용량이 상대적으로 많음 (특히, 분기 계수가 큰 경우).

5.3. 프로젝트 활용 경험

  • DFS 활용 사례: 적 AI가 플레이어까지의 경로를 탐색할 때 DFS를 사용. 게임 맵이 크지 않고, 최단 경로보다는 도달 가능 여부가 중요했기 때문에 DFS가 적합.
  • BFS 활용 사례: 특정 아이템으로부터 일정 거리 이내에 있는 모든 오브젝트를 찾기 위해 BFS를 사용. BFS를 통해 거리에 따른 순차적인 탐색이 가능했음.

5.4. 추가 학습 내용

  • DFS와 BFS의 시간 복잡도 및 공간 복잡도 분석
  • 양방향 탐색 (Bidirectional Search)과 같은 고급 탐색 알고리즘

6. Behaviour Tree (행동 트리)

6.1. Behaviour Tree란?

  • 정의: 게임 AI의 행동을 계층적이고 모듈화된 방식으로 정의하는 데 사용되는 트리 구조.
  • 구성 요소:
    • Root: 트리의 최상위 노드.
    • Composite: 자식 노드들을 제어하는 노드 (Selector, Sequence 등).
    • Decorator: 자식 노드의 실행 조건이나 결과를 변경하는 노드 (Inverter, Succeeder 등).
    • Action: 실제 행동을 수행하는 노드 (MoveTo, Attack 등).
    • Condition: 특정 조건을 검사하는 노드 (IsTargetInRange, IsHealthLow 등).
  • 장점:
    • 가독성과 유지보수성이 좋음.
    • 재사용성이 높음.
    • 복잡한 AI 로직을 쉽게 구현할 수 있음.

6.2. 추가 학습 내용

  • 다양한 Composite, Decorator 노드의 종류 및 동작 방식
  • Behaviour Tree 에디터를 활용한 비주얼 스크립팅
  • Behaviour Tree 라이브러리 비교 (Unity Asset Store 등)

7. 길찾기 알고리즘

7.1. 알고 있는 길찾기 알고리즘

  • A* (A-Star): 휴리스틱 함수를 사용하여 최적의 경로를 찾는 알고리즘.
  • Dijkstra's Algorithm (다익스트라 알고리즘): 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘.
  • Breadth-First Search (너비 우선 탐색): 가중치가 없는 그래프에서 최단 경로를 찾는 알고리즘.
  • Depth-First Search (깊이 우선 탐색): 도달 가능성을 확인할 때 주로 사용되지만 최단 경로를 보장하진 않음.
  • Jump Point Search (JPS): 그리드 기반 환경에서 A*를 개선한 알고리즘
 

7.2. A* 알고리즘

  • 개념: f(n) = g(n) + h(n) 공식을 사용하여 노드를 평가하고, 가장 낮은 f값을 가진 노드를 우선적으로 탐색.
    • g(n): 시작 노드에서 현재 노드까지의 실제 경로 비용.
    • h(n): 현재 노드에서 목표 노드까지의 예상 경로 비용 (휴리스틱 함수).
    • f(n): g(n)과 h(n)의 합.
  • 휴리스틱 함수: 목표 노드까지의 거리를 추정하는 함수. (예: 맨해튼 거리, 유클리드 거리)
  • 장점: 휴리스틱 함수를 통해 탐색 범위를 줄여 효율적으로 최단 경로를 찾을 수 있음.
  • 단점: 휴리스틱 함수가 admissible (실제 비용보다 과대평가하지 않음) 해야 최단 경로를 보장.

7.3. 프로젝트 적용 경험

  • A* 적용 사례: 2D 타일 기반 게임에서 적 캐릭터가 플레이어를 추적하도록 A* 알고리즘을 사용. 타일 맵을 그래프로 변환하고, 각 타일 간의 이동 비용을 계산하여 최단 경로를 탐색.
  • 경험: A* 알고리즘을 통해 적 캐릭터가 장애물을 피해 효율적으로 플레이어를 추적하도록 구현할 수 있었음. 휴리스틱 함수를 조정하여 알고리즘의 성능을 개선할 수 있었음.

7.4. 추가 학습 내용

  • 다양한 휴리스틱 함수 (맨해튼 거리, 유클리드 거리, 대각선 거리 등)
  • A* 알고리즘의 최적화 기법 (Jump Point Search, Hierarchical Pathfinding 등)
  • Navigation Mesh (NavMesh)를 이용한 3D 환경에서의 길찾기
  • 동적 장애물 회피 (Dynamic Obstacle Avoidance)

 

여기까지가 정리본 및 앞으로 추가로 학습이 필요해보이는 내용을 정리한 것이다.

여유가 생길 때 마다 계속해서 추가 학습을 진행해야할것같다...

[UNITY]/TIL: UNITY 다른글

티스토리툴바