게임 개발 스킬트리

A. vector 강의 내용이 너무 뒤죽박죽이여서 목차를 잡을 수 없음 강사님의 질문과 대답이 다른 경우가 많아;; 강의 흐름대로 목차를 잡음 1. vector의 기본기 (복습) a. size와 capacity의 차이점 🌟 실제 사용하는 공간 / 할당된 공간 reserve를 먼저 사용하는 이유? ➡ 이사비용, 메모리 파편을 아낌 capacity까지 줄이고 싶다면 빈 벡터로 스왑 : 사용 안함(이론적인 것) b. 데이터 삽입, 추출, 임의 접근의 시간복잡도 push_back() : 가장 고전적으로 데이터를 삽입하는 방법 🧡 시간복잡도 - 시작 : O(n) - 중간 : O(n) - 끝 : O(1) - 첫 데이터 가져오기 front() : O(1) - 마지막 데이터 가져오기 back() : O(1) - 임의 ..

B. 함수 객체 1. 함수 객체의 기본 a. 함수 객체란? 🌟 함수처럼 작동하는 객체 함수처럼 호출될 수 있고, 상태를 유지할 수 있음 주로 함수 포인터의 한계를 극복하거나 유연한 동작을 제공하기 위해 사용 c++에서 자주 사용 b. 함수 객체의 구조 구조는 일반 클래스나 스트럭트의 구조와 다를게 없음 HTML 삽입 미리보기할 수 없는 소스 #include // 함수 객체 클래스 정의 class MyFunctionObject { public: // 호출 연산자 정의 void operator()(int x) const { std::cout

A. 함수 포인터 1. 함수 포인터 기초 먼저 함수 객체를 이해하려면 함수 포인터에 대한 내용을 알아야 함 더보기 저번에 우선순위 q를 사용해 데이터를 꺼낼 때 정렬시 사용한 대소비교 객체가 무엇인지 (less, greater) 공부를 했었음 이 less, greater에 대한 공부임!! a. 함수 포인터란? 🌟 함수를 가리키는 포인터 int, double과 같은 자료구조들 뿐만 아니라 함수 자체도 포인터로 들고 있을 수 있음 다른 데이터 유형과 마찬가지로 메모리에 위치, 함수의 메모리 구조를 저장 👍 함수를 실행하는 시점을 뒤로 미룰 수 있다는게 장점 실행하는 시점을 뒤로 미룰 수 있다 ➡ 다양한 요청을 순서대로 처리한다 b. 함수 포인터 사용 1) 어떤 함수 작성 2) 함수 타입(FuncType) 생..

A. A* 1. A* 알고리즘 a. A*란? 🌟 주어진 시작 지점에서 목표 지점까지의 최적 경로를 찾는 데 사용 그래프 검색 및 경로 탐색 알고리즘의 일종 출구의 개념을 알아 출구로 갈수록 가산점이 있음 그래프 내에서 가장 짧은 경로를 찾는 데 사용되며, 다양한 문제 도메인에서 널리 사용 우선순위 큐를 사용하여 구현 b. A*의 두가지 개념 비용 기능 (Cost function): 각 노드에 대해 시작 지점부터의 비용을 나타내는 함수. 즉, 입구에서부터의 비용 휴리스틱 (Heuristic): 각 노드에서 목표 지점까지의 추정 비용을 나타내는 함수. 휴리스틱은 종종 "거리" 또는 "비용"을 기반으로 함. 즉, 출구에서부터의 비용 c. 알고리즘 이 비용 기능과 휴리스틱을 사용하여 각 노드의 "평가 함수"를 ..

A. 다익스트라 1. 다익스트라 알고리즘 a. 다익스트라란? 🌟 그래프 내의 한 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘 너비 우선 탐색(BFS)과 유사하지만, 모든 간선의 가중치가 양수일 때에만 사용 가능 각 정점마다 최단 경로를 저장하는 배열을 유지하면서 탐색을 진행 b. 알고리즘 초기에는 출발점에서 각 정점까지의 거리를 무한대로 설정하고, 출발점의 거리를 0으로 설정 그런 다음 출발점부터 시작하여 인접한 정점들로의 거리를 갱신하고, 이러한 과정을 반복하여 최단 경로를 찾음 👉 즉, 발견한 후보중에 베스트 케이스를 골라서 실행 c. 시간복잡도 시간 복잡도는 일반적으로 O(V^2) , V는 정점의 수 우선순위 큐를 사용하여 최소 거리를 갖는 정점을 빠르게 찾을 경우 시..

A. Maze Project 1. BFS기반 길찾기 a. CalculatePath_BFS BFS는 너비만 먼저 생각해서 왔다 갔다 하니까 비효율적으로 움직임 목적지라는 개념이 없는것이 치명적인 단점! 즉, 시작점을 기준으로 이 맵에 대한 전체적인 서칭을 하는 개념이지 최단거리에 최적화 되어있는 코드는 아님 출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum [게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows ..

A. 그래프를 Vertex 구조체로만 만들지 않는 이유 1. 그래프를 Vertex로 그려보자 그래프를 구현할 때 트리와 같이 노드를 나타내는 Vertex 구조체를 사용할 수 있음 a. 구현할 이미지 b. Vertex로 생성한 그래프 트리랑 비슷하게 Vertex로 정점을 만들고 정점에서 다른 간선들에 대한 정보를 들고 있는 모습으로 생성 c. 간선 정보를 물어본다면 연결관계를 물어본다면 위와같은 모습이 될것 👉 그래프는 간선간의 데이터가 중요하기 때문에 위와 같이 관리한다면 더 많은 자원이 필요하게 됨 d. 간선 위주의 데이터 형식 그래프의 경우, 각 노드가 자신과 연결된 다른 노드들의 정보를 가지고 이들 간의 관계는 그래프 자료구조에 따라 다르게 표현하기 때문에 🌟 그래프를 구현할 때는 보통 Vertex..

A. 그래프와 알고리즘 1. DFS a. DFS란? 🌟 Depth First Search, 깊이를 우선으로 파고 들어가는 검색방법 b. DFS 생성하기 1) 인접 리스트 재귀함수로 생성가능 = 스택을 이용 2) 인접 행렬 c. 모든 정점을 둘러보기 위 코드를 실행해보면 5번 정점에 대한 데이터는 얻을 수 없음 (데이터 방향이 단방향) 따라서 모든 정점에 대한 반복문을 돌려주면 모든 정점을 둘러볼 수 있음 d. 시간복잡도(BFS랑 똑같음) 1) 인접 리스트일 경우 모든 정점마다 한번씩 함수에 호출 (v) + 간선의 총 개수 (e) 간선의 총 개수는 e지만 모든 정점들이 연결되어 있으면 자체가 v제곱이 될 수 있음 따라서 간선이 드문드문 연결되어있는 데이터에 적합함!! 2) 인접 행렬일경우 정점마다 한번씩 ..

C. 비선형 자료구조 4. 그래프 기초 트리랑 유사하지만 범위가 더 넓다 (트리가 그래프의 일종) a. 그래프의 개념 🌟 현실 세계의 사물이나 추상적인 개념간의 연결관계를 표현 정점(Vertex) : 데이터를 표현 (사물, 개념 등) 간선(Edge) : 정점들을 연결하는데 사용 👉 내용은 어렵지 않지만 내용을 분석하는게 중요함 b.그래프 종류 간선에 추가적인 정보를 넣어서 그래프의 종류를 표현할 수 있음 가중치 그래프 : 지하철 노선도 방향 그래프 : 도로망(일방 통행 포함), 사랑의 짝짓기 💙 게임에서 그래프를 이용해야 하는 상황 * 길찾기 * 서버에서 락을걸어 멀티스레드를 관리할 때 데드락 체크 * 도로망 * 가족관계도 등 👉 즉, 이론을 알면 구현할 수 있는게 너무 많기 때문에 꼭 공부해야 함 c...

C. 비선형 자료구조 3. 힙 트리 👉 힙 트리를 공부하기 전 미리 이진트리를 공부 [게임 프로그래머 입문 올인원] 이진 트리와 탐색 (70강) 이진 트리(BT) / 이진 탐색 트리(BST) 🌟 이진 트리 : 노드를 최대 2개의 자식으로 가지는 트리 🌟 이진 탐색 트리 : 노드를 최대 2개의 자식으로 가지는 트리 레프트, 라이트 차일드로 만드는게 일 monamu.tistory.com a. 힙 트리 (Heap Tree) 란? 🌟 힙(Heap)이라는 완전 이진트리(Complete Binary Tree)의 형태를 가지며 일정한 조건을 만족하는 자료구조 데이터 구조 중 하나 힙의 특성에 따라 가장 높은(또는 낮은) 우선순위를 가진 노드가 항상 루트 노드에 위치 💥 자료구조에서 힙은 메모리의 힙이 아니고 우선순위..