게임 개발 스킬트리

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

A. STL 1. STL 개요 a. STL이란 🌟 표준 C++ 라이브러리 (Standard Template Library) 프로그램에 필요한 자료구조와 알고리즘을 Template로 제공하는 라이브러리 프로그래머가 쉽고 효율적으로 흐로그램을 작성할 수 있게 도움 b. STL의 구성요소 1) 컨테이너 Container : 데이터를 저장하는 자료구조. 벡터, 리스트, 맵, 큐, 스택 등 제공 시퀀스 컨테이너 : 선형 자료구조 연관 컨테이너 : 비선형 자료구조 2) 반복자 Iterator : 컨테이너의 요소를 반복하는데 사용. 접근을 추상화 해 일관된 방법으로 처리 3) 알고리즘 Algorithm : 정렬, 검색, 변환 등 다양한 작업을 수행하는 함수를 제공. 컨테이너와 반복자를 대상으로 작동 4) Functi..

A. 00:05 “공부시간 세계 1등” 한국의 공부법은 황당하다 1. 강의 내용 메모 a. 빈약한 기억 일반인들의 기본적인 기억의 내용과 재료들이 상당히 빈약하다 시험은 어떤 식으로 되어있는가 팩트 X , 기억을 논리적으로 조합해서 결과를 측정함 즉, 단순한 기억을 물어보는 시험이 아님 시험을 안치게 되면 응용할 문제가 없음 일반인의 입장에서는 필요한 지식은 기억, 팩트, 사실들이 중요하다 5의 법칙 : 어떤 상황에서도 5가지 이상의 팩트를 모르고 있다 = 다섯 개 이상에 대해서 일반 상식이 확장이 안됨 👉 기본에 대해 암기하지 않으면 그 사회가 뭘 중요하게 생각하는 지 모르게 됨 b. 기억이 왜 중요한가 기억 = 감정 기억이 풍부하면 감정이 풍부해짐 (ex. 강아지) 공유된 기억이 없으면 감정이 안생김..

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) 인접 행렬일경우 정점마다 한번씩 ..