양양의 게임개발

쿼드트리(QuadTree) 쿼드트리(QuedTree)는 공간을 4 역으로 미리 분할한 뒤, 각 오브젝트를 자신의 위치와 크기에 가장 적합한 노드에 삽입하여 관리하는 구조이다. 이 구조에서 부모 노드의 AABB와 오브젝트의 AABB를 교차 검사하여 해당 오브젝트가 포함될 수 있는 자식 노드로 점진적으로 내려가며 삽입하게 된다. 쿼드트리 구조struct Object { AABB bound; }struct QuadNode{ AABB bounds; // 노드가 담당하는 영역 std::vector objects; // 여기에 포함된 오브젝트들 QuadNode* children[4]; // 4개의 자식 (NW, NE, SW, SE)}; 1. 트..

정렬(Sorting)정렬(Sorting)은 주어진 데이터 집합을 특정 기준(키 값)에 따라 순서 있게 재배치 하는 과정이다. 일반적으로 오름차순 정렬은 모든 인덱스 i, j에 대해 i주어진 데이터에 따라 정렬 성능이 달라지기 때문에 정렬할 데이터와 정렬 목적에 따라서 상황에 맞게 알고리즘을 선택해야한다. 정렬 알고리즘 선택 고려 사항고려 요소이유예시데이터의 크기 (n)데이터의 개수가 작을수록 단순한 알고리즘(삽입/선택/버블)도 충분히 빠름. 데이터가 많을수록 O(n log n) 이상의 효율이 필요함n=100 → 삽입정렬도 OK, n=1,000,000 → 퀵/힙/병합정렬데이터의 정렬 정도이미 거의 정렬된 데이터라면 삽입 정렬이 매우 빠름. 무작위거나 역순이면 퀵정렬이 느려질 수 있음삽입 정렬은 "거의 ..

휴리스틱(Heuristic) 함수휴리스틱(Heuristic)이란 어떤 문제를 정확히 풀기엔 너무 복잡하거나 많은 비용이 들 때, 경험적 추정을 통해 빠르게 답을 도출하는 전략을 말한다. 즉, 완벽한 답이 아니라 좋은 방향을 제시하는 '추정값'을 도출하는 방식이다. 휴리스틱 함수(Heuristic)란 실제 목표까지의 거리를 완벽히 계산하지 않고, 그럴 듯하게 예측하여 비용을 계산하는 함수이다. 휴리스틱 함수는 문제의 특성(노드와 간선의 의미)에 따라 달라지기 때문에 올바른 휴리스틱을 설계하려면 해당 문제에서 '거리란 무엇인가?'를 명확히하고 휴리스틱의 의미를 정의해야한다. A*에서는 노드 n을 거쳐 목적지까지 가는 예상 비용을 기준으로 큐의 우선순위를 관리한다. 하지만 이 예상 비용을 정확하게 계산하려..

위상 정렬 (Topological Sort) 위상 정렬(topological sort)은 DAG(Directed Acyclic ZGraph, 방향 비순환 그래프)에서 정점들을 선행 조건(간선 방향)을 지키며 나열하는 정렬 방식으로 ‘의존 관계를 지키는 실행 순서를 만드는 알고리즘’이다. 위상 정렬은 방향을 따라 나열하는 것이 아닌, 방향을 거스르지 않고 나열하는 것이기 때문에 여러가지 결과가 나올 수있으며, 작업 스케줄링, 컴파일 순서, 렌더링 패스 실행 순서 등 다양한 의존성 문제가 있는 곳에서 활용된다. 방향 그래프의 차수진입 차수 (In-degree) : 외부에서 오는 간선의 수진출 자수 (Out-degree) : 외부로 향하는 간선의 수차수 (degree) : 진입 차수 + 진출 차수 위상 정..

다익스트라(Dijkstra) 최단 경로 알고리즘 다익스트라 알고리즘은 가중치 그래프에서 하나의 정점부터 다른 모든 정점 까지의 최단 경로를 찾는 알고리즘으로, 현재까지 발견된 경로들 중 가장 짧은 거리의 정점부터 차례로 선택하여 그 정점과 인접한 노드들의 최단 거리를 갱신해 나가는 방식으로 동작한다. 다익스트라 알고리즘에서의 최단 거리는 지나온 경로의 가중치를 더해서 거리를 비교하기 때문에 음수 가중치 그래프는 이 알고리즘을 적용할 수 없다. 다익스트라 알고리즘을 활용하기 위해서는 최단 경로를 저장할 '최단 거리 배열(distance array)'과 각 시점에서 가장 가까운 정점을 알아내기 위한 '최소 힙 기반 우선순위 큐(min-heap priority queue)'를 활용한다. 알고리즘은 시작..

그래프(Graph) 그래프(Graph)는 정점(Vertex, Node)과 간선(Edge)의 집합으로 이루어진 자료구조로, 서로 복잡하게 얽혀있는 개체들의 N:M 관계를 표현할 수 있다. 정점(V)은 데이터를 담는 단위를 나타내며 간선(E)은 정점과 정점을 연결하는 관계를 의미한다. 예를들어 그래프로 네트워크망을 표현한다고 하면, 컴퓨터가 정점이 될 것이고 컴퓨터를 연결짓는 네트워크가 간선이 될 것이다. 정점의 차수 (degree) 차수(degree)는 정점에 직접 연결된 간선의 수를 의미한다. 무방향 그래프에서는 정점에 인접한 정점의 수를 말하며 위 사진에서 정점 1의 차수는 2이다. 방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수 (o..

슬라이딩 윈도우(Sliding Window) 알고리즘 투 포인터의 일종으로 윈도우(Start~End 구간)을 한칸씩 이동하며 문제를 해결하는 알고리즘이다. 슬라이딩 윈도우 알고리즘의 두 포인터는 배열 전체를 최대 한번씩만 이동하기 때문에 시간 복잡도는 O(n)이다.윈도우의 크기는 고정일수도 있고 가변일 수도 있다. 고정 윈도우(Fixed Window)윈도우 크기 K가 고정되어있어 K 크기 만큼의 윈도우를 한칸씩 밀며 탐색을 수행한다. End - Start + 1 = K의 관계가 유지되며 보통 슬라이딩 윈도우 라고 하면 고정 윈도우를 의미한다.가변 윈도우(Variable Window조건에 따라 Start와 End가 자유롭게 움직이며 윈도우의 크기가 변할 수 있다. 조건에 만족할 때 까지 end를 늘..

N의 연속된 자연수의 합 찾기 n의 연속된 자연수의 합 찾기 분제는 입력값 N이 주어졌을 때, 1부터 N 사이의 연속된 자연수의 값을 합해 N이 되는 경우의 수를 구하는 문제이다. 예를들어 N = 15가 주어졌다면 1부터 15 사이의 자연수 중, 연속된 값을 합해 15가 되는 경우의 수 4가지(12345, 456, 78)을 구하는 문제이다. 이 문제를 단순히 완전 탐색(Brute Force)으로 경우의 수를 구하려면 2중 루프를 돌아 O(n^2)의 시간 복잡도가 걸린다.for (int start = 1; start N) break; // 넘어가면 중단 }} 투 포인터(Two Pointers) 알고리즘 두 개의 포인터(start, end)를 사용하여 구간을 확장/축소하며 조건을 만족하는 구간..

구간 합 (Query of Range Sum) 구간 합은 “배열 A에서 임의의 구간 [L, R]의 합을 M번 구하라”는 문제를 말한다.A = [5,4,3,2,1]Q1: 2~4 구간의 합은? → 9Q2: 1~5 구간의 합은? → 15 만약 구간합을 구할 때 마다 A[L]~A[R]까지 직접 전부 더한다면 시간 복잡도는 O(n), 쿼리가 m번 주어지면 시간복잡도는 O(n * m)이 될 것이다💦 보통 이런 문제는 시간 제한이 있기 때문에 이렇게 하드한 방식으로 연산을 하면 시간 초과가 된다. 누적합 알고리즘 (Prefix Sum) 구간합 문제를 빠르게 풀기 위해 사용되는 알고리즘으로 각 구간별 합을 보조 배열 S에 미리 저장해두고, [L,R]에 빠르게 대응하는 풀이 방식을 말한다.S[0] = A[0]..

힙 (Heap) 힙(Heap)은 반 정렬상태를 유지하는 완전 이진 트리(complete binary tree)로 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 완전 이진 트리의 속성에 따라 높이가 K일때 K-1 레벨까지 중간에 비어있는 곳 없이 노드가 꽉 차있으며 K레벨은 왼쪽부터 채워진다. 또한 힙은 중복된 값을 허용하여 ‘부모의 키 값이 자식의 키 값보가 크거나 같은’ 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는것이므로 전체를 정렬하지 않고, 큰 값이 상위레벨에 있고 작은 값이 하위레벨에 있다 정도의 느슨한 정렬 상태를 유지한다. 힙은 최대힙과 최소힙으로 분류되는데, 부모 노드의 키 값이 자식 ..