MOONSUN

이전 글에서도 그렇고, Dynamic Programming 문제를 해결할 때의 핵심은 "점화식"을 찾는 것이었다. 하지만 DP 문제를 풀다 보면점화식은 맞는 것 같은데 시간 초과가 나거나, 배열 크기를 키우면 메모리가 터지고,경우의 수를 세려다 숫자가 감당할 수 없이 커지는 문제를 맞이하게 된다. 문제는 점화식이 아니라, 불필요한 정보까지 상태로 들고 가고 있다는 점이다. 이번 글에서는 “모든 경우를 그대로 저장하면 왜 안 되는지”를 출발점으로,미래 계산에 꼭 필요한 정보만 남기는 상태 압축과 그 상태에서 자연스럽게 점화식을 도출하는 과정을 정리해보고자 한다. 1. 1차원 DP와 2차원 DP 1차원 DP : 결과를 정의하는 데 정보가 하나면 충분한 경우2차원 DP : 결과를 정의하려면 두 가지 정보가..

지금까지 QuadTree와 BVH 에 대해서 각각 알아보았는데,그럼 각각은 어떤 차이점이 있고, 또 각각은 어디에서 사용하면 되는건지 정리해보고자 한다. Quad/Octree는 공간을 기준으로 나눈다.BVH는 객체(AABB)를 기준으로 묶는다. 구분Quad/OctreeBVH분할 기준공간을 일정 규칙으로 고정 분할객체(primitive)의 분포에 따라 적응적 분할트리 생성 방식공간 기반객체 기반노드 크기고정된 공간 분할 규칙 기반객체들의 AABB의 합집합노드 수공간 크기·해상도에 영향객체 배치에 따라 동적으로 결정 1. 장점 BVH의 장점 1. 객체 밀도에 따라 자동 적응비어 있는 공간을 거의 생성하지 않음객체 밀집 지역만 세분화 → 트리 깊이가 효율적 2. Ray Tracing 에 매우 유리각 노..

앞 글에서 동적 프로그래밍에 대해 알아보았었다. 이번 글에서는 동적 프로그래밍을 활용해서정수 N을 1로 만드는 최소 연산 횟수 문제를 간단하게 구현해보도록 하자! 0. 문제 정의정수 N이 주어졌을 때, 다음 세 연산만을 사용하여 N을 1로 만드는 최소 연산 횟수를 구하는 문제를 해결해보자. N이 3으로 나누어 떨어지면 → N = N / 3N이 2로 나누어 떨어지면 → N = N / 2항상 가능 → N = N - 1목표는 연산 횟수를 최소화하는 것 !! 핵심 포인트: 여러 선택지 중에서 최소 횟수를 선택해야 하는 최적화 문제 이 문제는 중복되는 계산이 많기 때문에 동적 계획법(DP)이 적합한 문제다. DP를 적용하면 작은 문제부터 큰 문제까지 최적해를 점차 만들어 나갈 수 있다. DP 방식은 두 ..

복잡해 보이는 문제도 작은 문제로 나누어 효율적으로 해결하는 방법이 있다.바로 동적 프로그래밍(Dynamic Programming, DP)이다.DP는 문제를 여러 개의 작은 부분 문제로 분해하고,이 부분 문제들의 결과를 저장해 재사용함으로써 중복 계산을 제거하는 알고리즘 기법이다.일반적인 재귀나 완전 탐색으로는 시간 제한을 넘길 수 있는 문제들도, DP를 사용하면 빠르게 해결할 수 있기 때문에 알고리즘 분야에서 매우 중요한 개념이다.이 글에서는 동적 프로그래밍의 개념에 대해 알아보고, 예시 코드 구현까지 작성해 보도록 하자. 0. Dynamic Programming(DP : 동적 프로그래밍)동적 프로그래밍(Dynamic Programming, DP)은큰 문제를 작은 부분 문제(Subproblem)로 ..

이전에 BVH (Bounding Volume Hierarchy) 에 대해서 간단하게 정리 해봤었는데,이번에는 BVH를 구현할 때, 오브젝트가 움직였을 때 트리를 어떻게 다시 맞춰서 업데이트할 것인지에 대한 방법에 대해서 알아보고자 한다. 0. BVH의 트리 품질 (Tree Quality) BVH는 오브젝트들의 AABB를 이용해 트리(계층적 경계 볼륨)를 만드는 구조이다.문제는 오브젝트가 움직이면, 트리의 품질이 떨어지기 때문에 ‘트리를 어떻게 갱신할 것인가’ 가 중요해진다. 여기서 갱신 방식이 정적(Static) 과 동적(Dynamic) 으로 나뉜다. 0-1. “오브젝트가 움직이면 트리의 품질이 떨어진다”는 말은BVH가 더 이상 ‘빠르게 충돌 검사/레이 테스트를 해 줄 수 없는 구조가 되어간다는 뜻...

게임에서는 수천 개의 모델, 총알, 파티클 등.. 많은 오브젝트가 동시에 존재한다. 모든 오브젝트를 매 프레임마다 전부 검사한다면....?CPU는 순식간에 과부화가 될 것이다. 그래서 등장한 개념이AABB (Axis-Aligned Bounding Box) 트리 기반의 공간 분할 및 계층적 충돌 검사이다. 00. AABB 트리가 필요한 이유? 앞에서 언급 했듯, 수많은 오브젝트들을 전부 일일이 교차 검사(intersection test) 하거나 카메라 시야에 있는지(culling) 검사한다면?CPU는 순식간에 과부화 그래서 "필요 없는 건 아예 검사하지 말자" -> 공간을 분리하거나, 객체를 묶는 트리 구조를 사용한다. 이게 바로 QuadTree 또는 BVH(Bounding Volume Hier..

이전 글에서 위상정렬(Topological Sort), Task Graph, 그리고 Kahn 알고리즘을 통해작업 간 의존성을 관리하는 방법을 살펴보았다. 이번 글에서는 이러한 Task Graph를 WinAPI를 사용해멀티 스레드 환경에서 병렬로 실행하도록 작성한 예제를 정리해보도록 하겠다.즉, 동시성(Concurrency)을 고려해 여러 Worker Thread가 독립적인 작업을 동시에 수행하도록 구현하고,Critical Section과 Event를 활용해 스레드 간 안전하게 작업 큐를 관리하는 방법까지 살펴보도록 하겠다. 0. 스레드 생성과 라이프 사이클스레드는 프로그램에서 독립적으로 실행되는 흐름으로, 다음 5가지 상태를 가진다.생성 (Created): 스레드 객체 생성, 아직 실행 전준비 (R..

작업 간의 순서(의존성)을 체계적으로 관리하기 위해서 위상 정렬(Topological Sort) 이라는 개념이 사용된다. 위상 정렬의 간단한 개념은 앞에서 그래프에 대해 설명하면서 언급이 되었긴 하지만, 이번 글에서는 위상 정렬의 기본 개념부터실제로 구현할 때 자주 사용되는 칸 알고리즘(Kahn’s Algorithm) 과 이를 응용한 Task Graph 구조까지 알아보도록 하겠다. 1. 그래프의 위상정렬 (Topological Sort) 이란?방향 그래프(Directed Graph) 에서 모든 간선의 방향을 거스르지 않고 정점(노드)을 나열하는 것 즉, u → v 가 있다면 u가 반드시 v보다 먼저 나와야 한다는 것. 결과적으로, 정점들의 “선형 순서(Linear Ordering)” 를 만드는 과정..

A* 알고리즘은 최단 경로 탐색 알고리즘으로,다익스트라(Dijkstra) 알고리즘의 장점에 휴리스틱(Heuristic) 개념을 결합한 형태이다. A* 이름의 뜻은A : 탐색 알고리즘,* : 최적(Optimal), 최선(Best) 버전즉, A*는 “최적의 탐색 알고리즘(Optimal Graph Search Algorithm)” 이라는 의미를 담고 있다. 00. 다익스트라 알고리즘다익스트라는 현재까지의 누적 거리(비용)를 기준으로 비용이 가장 작은 노드부터 탐색해 나간다. 각 노드의 누적 거리 + 다음 노드로의 이동 비용을 계산해 비용이 가장 작은 노드를 우선적으로 방문우선순위 큐(Priority Queue)에 저장하고,목적지에 도달하면 즉시 탐색을 종료할 수 있다.이 방식은 최적의 해를 찾지만..

앞에서 다익스트라 알고리즘에 대해서 알아보았다. 이번에는 다익스트라 알고리즘을 활용할 수 있는 백준 문제 11779번을 풀어보도록 하겠다! 백준 11779번 : 최소비용 구하기2 문제n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다.우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라.항상 시작점에서 도착점으로의 경로가 존재한다. 입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다.그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정..