게임 개발 스킬트리

A. 동적 계획법 (Dynamic Programming) 1. Dynamic Programming a. 동적 계획법이란? 🌟 큰 문제를 작은 하위 문제로 나누어 푸는 알고리즘 설계 기법 최적화 문제나 최단 경로 문제와 같이 큰 문제를 작은 부분으로 나누어 해결해야 하는 경우에 사용 ex) 피보나치 수열 계산, 그래프 최단 경로 찾기, 배낭 문제 b. 동적 계획법의 특징 중복 계산 최소화: 동적 계획법은 작은 하위 문제의 해답을 저장하고 재활용하여 중복 계산을 피해 시간 복잡도를 획기적으로 줄임 최적 부분 구조: 큰 문제의 최적 해결 방법이 작은 하위 문제의 최적 해결 방법으로부터 구성될 수 있어야 함. 이를 통해 작은 하위 문제의 해답을 결합하여 전체 문제의 최적 해답을 찾을 수 있음 상향식 접근법: 하..

e. 퀵 정렬 (중요) 1) 퀵 정렬이란? 🌟 평균적으로 매우 빠른 속도를 보이는 정렬 알고리즘 분할 정복(divide and conquer) 기반 재귀적으로 배열을 분할하고 정렬하는 방식으로 동작 👉 분할 정복에 대한 내용은 d. 병합정렬에 작성되어있음 [게임 프로그래머 입문 올인원] STL Algorithms : 기본정렬 (78강) A. STL Algorithms : 기본 정렬 1. 기본 정렬의 기초 a. 기본 정렬이란? 🌟 디폴트 정렬(default sorting), 기본 정렬 알고리즘(default sorting algorithm)을 의미 std::sort 함수를 통해 수행 이 함수는 퀵 정렬(Quick So monamu.tistory.com 💥 최악의 경우 시간 복잡도가 O(n^2)가 될 수있어..

A. 실습 먼저 무슨 게임을 만들건지 먼저 정하기 1. 기본적인 게임 생성해보기 a. 플레이어 생성 b. 몬스터 생성 c. 오브젝트 생성 d. 플레이어 찾기 1) dynamic_cast 1번 플레이어를 찾아주고 플레이어가 없으면 널포인터를 뱉어주는 코드 ➡ 포인터를 어떻게 들고있는지는 딱히 상관이 없고 들고있는 바이트만큼 해제를 함 2) enum 만약 dynamic_cast 사용하기 싫다면 enum을 사용해서 관리 🧡 포인터 문제 ptr의 heap 메모리에 저장되어있는 정보를 가지고 메모리를 해제하게 됨 e. 업데이트 하기 필드에서 업데이트 함수를 생성해서 모든 오브젝트 갱신하기 다음으로 인벤토리 등등을 추가해주면 됨 출처 : https://www.inflearn.com/course/%EA%B2%8C%E..

B. STL Container : hash_map 1. hash_map a. hast_map이란? 🌟 해시 함수를 사용하여 데이터를 저장하는 자료구조 std::unordered_map이라는 클래스 템플릿으로 제공 (hash_map은 옛날 이름) ex) std::unordered_map은 정수형 키와 문자열 값으로 이루어진 해시 맵 map이랑 기능적인 측면에서 다르지 않음 공간을 다 확보해 놓고 맞는 데이터를 꺼내 쓰는 방법 👉 즉, 201, 202호처럼 통을 먼저 구현해놓고 그 통에 값을 쏙쏙 넣어주는 개념! b. hash_map의 특징 키와 값의 쌍으로 데이터를 관리 해시 맵은 키의 순서를 유지하지 않으며, 각각의 키는 유일 해시 테이블을 기반으로 구현 일반적으로 빠른 검색 속도를 제공(시간복잡도 0(..

A. STL Container : map 1. map a. map이란? 🌟 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조 표준 헤더 파일 을 포함하여 사용 ex) std::map은 정수형 키와 문자열 값으로 이루어진 map set이랑 거의 동시에 감 개발 초반이나 매니저를 구현할때 사용 b. map의 특징 키와 값의 쌍으로 데이터를 저장 (키는 유일) 일반적으로 빠른 검색 속도를 제공하는 자료구조 내부적으로 레드-블랙 트리(Red-Black Tree)와 같은 균형 이진 탐색 트리가 사용되어 키의 정렬된 상태를 유지 따라서 시간복잡도는 O(log n) c. map의 기능 키를 기반으로 한 검색, 추가, 삭제, 수정 등의 연산을 제공 데이터의 삽입 시 자동으로 정렬되어 저장 d. map이..

A. 자료구조 개요 1. 자료구조의 기초 a. 자료구조란? 🌟 데이터를 조직화하고 저장하는 방법을 다루는 컴퓨터 과학의 분야 컴퓨터에서 효율적인 데이터 처리와 관련된 연산을 수행하기 위해 사용 💙 데이터? 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하는 모든 값 b. 자료구조의 선택 기준 자료의 처리 시간 자료의 크기 자료의 활용 빈도 자료의 갱신 정도 프로그램의 용이성 c. 자료구조의 특징 1) 조직화(Organization) 자료구조는 데이터를 구조화하여 저장하는 방법을 제공 데이터를 쉽게 관리하고 검색할 수 있도록 함 2) 효율성(Efficiency) 자료구조는 데이터에 대한 효율적인 접근 및 조작을 가능하게 함 적절한 자료구조를 선택함으로써 데이터 처리 작업의 성능을 향상 3) 추상화(Ab..

A. 트리 자료구조 3. 레드 블랙 트리 a. 레드 블랙 트리란? 🌟 각 노드가 레드 또는 블랙의 색상을 가지며 특정한 규칙을 따르는 트리 구조 균형 이진 탐색 트리의 일종 b. 레드 블랙 트리의 규칙 각 노드는 레드 또는 블랙 루트 노드, 모든 리프 노드(NIL)는 블랙 레드 노드의 자식 노드는 모두 블랙 어떤 노드로부터 리프 노드까지의 모든 경로에는 리프 노드를 제외하고 같은 개수의 블랙 노드가 있어야 함 = 블랙 높이 👉 위 내용만 잘 알고있으면 됨 c. 레드 블랙 트리의 특징 위 규칙을 통해 트리가 균형을 유지해 연산의 효율이 높아져 ➡ 탐색, 삽입, 삭제 연산을 O(log n)의 시간복잡도로 보장 레드-블랙 트리는 데이터베이스, 맵 등의 자료구조로 널리 사용 d. 레드 블랙 트리 추가 1) 이상..

A. 분할 정복 알고리즘 1. 이진 탐색 (Binary Search) a. 이진 탐색이란? 🌟 정렬된 배열 또는 리스트에서 특정한 값을 찾는 알고리즘 배열이나 리스트가 정렬되어 있다는 가정하에 작동 b. 진행방식 배열이나 리스트의 중간 요소를 선택하여 찾고자 하는 값과 비교 찾고자 하는 값이 중간 값보다 작으면 중간 값의 왼쪽 반을 대상으로 탐색을 수행 찾고자 하는 값이 중간 값보다 크면 중간 값의 오른쪽 반을 대상으로 탐색을 수행 이렇게 반복하여 탐색 대상이 하나가 될 때까지 이 과정을 반복 + [게임 프로그래머 입문 올인원] 이진 탐색 70강 내용 c. 이진 탐색의 장단점 HTML 삽입 미리보기할 수 없는 소스 1) 선형 탐색에 비해 훨씬 효율적으로 동작 💙 선형 탐색이란? 선형 탐색은 찾고자 하는 ..

A. 트리 자료구조 1. 이진 트리(BT) a. 이진 트리란? 🌟 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조 계층적으로 데이터를 구성하는데 사용 이진 탐색 트리, 힙, AVL트리, 레드블랙 트리 등 다양한 종류의 자료구조 와 알고리즘에서 기본적인 구성 요소 레프트, 라이트 차일드로 만드는게 일반적 (2개뿐이니) b. 이진트리의 규칙 각 노드는 최대 두 개의 자식 노드를 가짐 각 노드는 하나의 부모 노드를 가질 수 있음 각 노드는 데이터를 저장하기 위한 값을 가질 수 있음 이진 트리는 재귀적으로 정의되며, 각 노드의 왼쪽과 오른쪽 서브트리 또한 이진 트리 👉 이진 탐색 알고리즘 선행공부 분할 정복(Divide and Conquer) 알고리즘 1 : 이진 탐색 (Binary Search) A. ..

A. list 1. list의 기본기 (복습) a. size와 capacity size : 리스트의 노드 개수 capacity : 존재하지 않음 b. 데이터 삽입 / 추출의 시간복잡도 🧡 시간복잡도 - 시작 O(1) - 중간 O(1) HTML 삽입 미리보기할 수 없는 소스 list.insert(); ex) li.insert(li.end(), 1); li.insert(li.end(), 2); //insert함수는 iterator를 반환 li::iterator it = li.insert(li.end(), 3); li.insert(li.end(), 3); li.insert(li.end(), 4); //그걸 저장해 지우거나 삽입할 때 사용가능 li.insert(it,100); li.erase(it); d. 임의..