begin-play 님의 블로그

힙(Heap) / 우선순위 큐(Priority Queue)1. 힙(Heap)이란?이번에는 트리 자료구조에서 자연스럽게 이어지는 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 학습했다.힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가지면서, 부모 노드와 자식 노드 사이에 특정한 우선순위 관계를 유지하는 자료구조이다.힙은 크게 두 종류로 나눌 수 있다.Min HeapMax Heap여기서 중요한 점은 힙을 단순히 값이 정렬되어 있는 트리라고 생각하면 안 된다는 것이다.예를 들어 Max Heap은 다음과 같은 형태를 가질 수 있다. 100 / \ 80 70 / \ / \ 50 60 40 30Max Heap에서는..

Unreal Engine의 Foliage와 HISM, 그리고 자료구조·알고리즘의 연관성1. 오늘 학습한 내용오늘은 언리얼 엔진에서 많은 나무, 풀, 바위 등의 오브젝트를 배치할 때 사용하는 Foliage와 HISM(Hierarchical Instanced Static Mesh)에 대해 학습했다.처음에는 Foliage와 HISM을 단순히 여러 개의 Static Mesh를 효율적으로 배치하기 위한 언리얼 엔진의 기능이라고 생각했다.하지만 내용을 학습하면서 Foliage와 HISM이 자료구조와 알고리즘에서 배운 개념들과 연결된다는 것을 알게 되었다.특히 다음과 같은 개념들과 연관되어 있었다.배열(Array)인스턴스(Instance)공간 분할(Spatial Partitioning)계층 구조(Hierarchy)트..

Unreal Engine 네트워크 Replication 시행착오오늘 학습한 내용오늘은 LevelManager를 멀티플레이 환경에서 서버와 클라이언트가 동일하게 사용하도록 만드는 과정에서 Replication과 관련된 문제를 직접 확인하고 해결했다.처음부터 완성된 구조를 만든 것이 아니라,서버에서는 정상적으로 작동하는데 클라이언트에서는 왜 안 되는가?를 로그를 하나씩 확인하면서 원인을 찾아갔다.1. 서버와 클라이언트에서 Zone 배치가 달라지는 문제현재 게임에서는 여러 개의 Middle Zone을 가지고 있고, 게임이 시작될 때 서버에서 Zone의 순서를 랜덤하게 섞도록 구현했다.예를 들어 Middle Zone이:0 1 2 3 4 5라면 서버에서 Shuffle한 결과가:0 5 1 4 3 2처럼 만들어진다...

트리(Tree)1. Tree란?이번 학습에서는 Tree(트리) 자료구조에 대해 공부하였다.지금까지 학습했던 배열, 연결 리스트, 스택, 큐 등의 자료구조는 데이터를 일렬로 표현하는 형태가 많았다. 반면 Tree는 데이터를 계층적인 구조로 표현할 수 있다는 특징이 있다.대표적으로 컴퓨터의 폴더 구조를 생각할 수 있다.Root├── Folder A│ ├── File A│ └── File B└── Folder B ├── File C └── File DRoot 아래에 Folder가 있고, Folder 아래에 다시 File이 존재하는 것처럼 상위 데이터와 하위 데이터 사이에 부모-자식 관계가 존재하는 구조이다.따라서 Tree는 다음과 같은 계층 구조를 표현하는 데 적합하다.파일 시스템폴더 구조조..

해시(Hash)1. Hash란?이번에는 Hash(해시)에 대해 학습했다.해시는 데이터를 빠르게 저장하고 찾기 위한 방법이며, 특히 특정 데이터를 빠르게 탐색하는 상황에서 실전 활용도가 높은 자료구조이다.해시(Hash)는 쉽게 말하면 어떤 데이터를 일정한 규칙을 통해 다른 값으로 변환하는 것이다.예를 들어 문자열 "Apple"이라는 데이터를 어떤 계산을 통해 1234라는 숫자로 변환할 수 있다."Apple" → 1234이처럼 데이터를 다른 값으로 변환하는 과정을 해싱(Hashing)이라고 한다.해싱의 목적은 단순히 데이터를 다른 값으로 바꾸는 것이 아니라, 변환된 값을 이용해서 데이터를 빠르게 저장하고 찾는 것이다.2. Hash Function해시를 만들기 위해서는 Hash Function(해시 함수)이 ..

정렬 알고리즘1. 정렬 알고리즘이란?정렬 알고리즘은 여러 개의 데이터를 특정한 기준에 따라 순서대로 배치하는 알고리즘이다.예를 들어 다음과 같은 데이터가 있다고 하자.[5, 2, 8, 1, 3]오름차순으로 정렬하면 다음과 같이 된다.[1, 2, 3, 5, 8]정렬은 단순히 숫자를 순서대로 배치하는 것뿐만 아니라, 탐색, 데이터 처리, 우선순위 관리 등 다양한 알고리즘의 기초가 된다.이번에는 정렬 알고리즘을 난이도 순으로 학습했다.Bubble SortSelection SortInsertion SortMerge SortQuick SortHeap Sort각 알고리즘을 이해할 때는 단순히 시간 복잡도만 외우는 것이 아니라 다음 항목을 함께 확인해야 한다.동작 방식시간 복잡도공간 복잡도Stable 여부언제 사용하..

탐색 알고리즘1. 탐색 알고리즘이란?탐색(Search)은 주어진 데이터에서 원하는 값을 찾는 과정입니다.예를 들어 다음과 같은 배열이 있다고 하겠습니다.int arr[] = {10, 30, 20, 50, 40};여기서 50을 찾는 것이 탐색입니다.탐색 알고리즘에서는 대표적으로 다음 두 가지를 배웁니다.선형 탐색(Linear Search)이진 탐색(Binary Search)두 알고리즘의 가장 큰 차이는 데이터를 어떤 방식으로 확인하느냐입니다.2. 선형 탐색(Linear Search)선형 탐색은 가장 단순한 탐색 방법입니다.처음부터 끝까지 데이터를 하나씩 확인합니다.예를 들어 다음 배열에서 50을 찾는다고 하겠습니다.[10, 30, 20, 50, 40]처음부터 하나씩 비교합니다.10 → 30 → 20 → 5..

재귀(Recursion) — TIL 정리1. 재귀란?재귀(Recursion)란 함수가 자기 자신을 다시 호출하는 것이다.가장 기본적인 형태는 다음과 같다.void Function(){ Function();}Function()이 실행되면 다시 Function()을 호출하고, 그 함수가 다시 Function()을 호출한다.Function() └─ Function() └─ Function() └─ Function() └─ ...이렇게 계속 호출되면 프로그램이 끝나지 않고 호출 스택이 계속 쌓이게 된다.결국 Stack Overflow가 발생한다.따라서 정상적인 재귀 함수에는 반드시 종료 조건이 필요하다.2. 재귀 함수의 두 가지 핵심재귀 함수를 이해할 때 가장 중..

스택과 큐1. 스택과 큐란?스택(Stack)과 큐(Queue)는 여러 데이터를 저장하고 관리하는 자료구조이다.둘의 가장 큰 차이점은 데이터를 어떤 순서로 꺼내는가이다.Stack → LIFOQueue → FIFO즉, 데이터를 저장하는 방식보다 데이터를 꺼내는 순서가 핵심이다.2. Stack2-1. Stack이란?Stack은 LIFO(Last In, First Out) 방식의 자료구조이다.LIFO는 후입선출이라는 의미로, 가장 나중에 들어온 데이터가 가장 먼저 나간다.책을 위로 계속 쌓는 상황을 생각하면 이해하기 쉽다. [ C ] ← 가장 먼저 꺼냄 [ B ] [ A ]A → B → C 순서로 데이터를 넣었다면:Push(A)Push(B)Push(C)Pop() → CPop() → B..

TIL - 자료구조와 알고리즘: 연결 리스트1. 연결 리스트란?연결 리스트(Linked List)는 데이터를 Node(노드)라는 단위로 나누어 저장하고, 각 노드가 다음 노드를 가리키도록 연결한 자료구조이다.가장 기본적인 형태인 단일 연결 리스트(Singly Linked List)는 다음과 같은 구조를 가진다.Head ↓[10 | 다음] → [20 | 다음] → [30 | nullptr] ↑ Tail각 Node는 크게 두 가지 정보를 가지고 있다.[ 데이터 | 다음 Node의 주소 ]예를 들어 다음과 같이 구성할 수 있다.struct Node{ int Data; Node* Nex..