전체 글 (34) 썸네일형 리스트형 DFS 구현 (재귀, 스택) 그래프는 이 블로그에서 가져온 그림을 참고했다. 1. 재귀 함수를 이용한 방식 #include #include #include // To measure execution time #define SIZE 9 using namespace std; void DFS(vector _graph[], bool _visit[], int _startIndex) { if (_visit[_startIndex]) return; _visit[_startIndex] = true; cout Stack과 Queue의 차이 차이 스택은 선입후출(FILO/LIFO), 큐는 선입선출(FIFO)이다. 용도 스택 : DFS 알고리즘, 퀵 소트 큐 : BFS 알고리즘(특히 A*) 그 외에는 게임 개발하는 동안 사용한 적이 없는 것같다.. 단점 스택 : 스택 오버플로우를 주의해야한다. 큐 : 큐에 빈 메모리가 남아 있어도 rear가 배열의 끝에 도달했을 경우 꽉 차있는것으로 판단할 수 있다. A* 알고리즘 설명 A* 는 BFS 방식을 이용해 최단 경로를 구하는 알고리즘이다. 공식 F = G + H G는 시작점으로부터 해당 노드까지의 이동 비용, H는 해당 노드로부터 도착지까지의 예상 이동 비용이다. (휴리스틱에 대한 설명) 단점 맵의 크기가 커지면 Open Queue와 Closed Queue에 수 많은 노드들이 들어갈 수 있어서 메모리를 많이 차지하게 된다. 또한 시작점부터 도착지까지의 경로가 존재하지 않는 경우 모든 노드를 검색하므로 비효율적이다. + 맵을 어떤 자료구조로 구현하는게 좋을까 생각해봤는데 굳이 노드를 더 추가할 계획이 아니라면 배열을 사용해 인덱스 접근으로 탐색하는게 좋을 것 같다. - vector : 나중에 노드를 추가하는 경우가 아니라면 굳이? - list : 인덱스가 없어서.. 인접한 노드.. A* 알고리즘에서 어떤 휴리스틱 함수를 사용해야할까 내가 만든 길찾기에서는 그냥 피타고라스 정리로 휴리스틱을 사용했는데 검색해보니 다양한 방법들이 있다는 것을 알게 되었다. A* 의 성능에는 휴리스틱이 많은 영향을 끼치므로 좋은 휴리스틱을 사용해야한다. 휴리스틱 정확도가 낮을 수록 최단거리를 얻을 수 있지만 A*의 전체 속도가 느려지고, 휴리스틱 정확도가 높을 수록 A*의 전체 속도가 빨라지지만 최단거리를 포기해야한다. (출처) 따라서 속도와 정확도의 균형이 중요하다. 두 점 좌표 a(x1, y1, z1), b(x2, y2, z2)이고 a와 b의 휴리스틱 거리값이 distance라고 친다. 1. 맨하탄 방식 distance= fabs(x2 - x1) + fabs(y2 - y1) 목표까지 도달하는 가로와 세로의 길이만을 고려한다. 장애물은 고려하지 않는다... 데이터를 찾을 때 hash와 array 어떤게 더 빠를까 인덱스를 아는 경우와모든 데이터를 순차적으로 접근하는 경우에는 array가 빠르다. array와 hash 모두 O(1)이지만 array는 hash function을 거치지 않기 때문에 hash보다 더 빠르다. key를 찾는 경우에는 hash가 빠르다. hash의 경우 O(1)이지만 array는 key 값의 개념이 없어 순차탐색하므로 O(N)이 된다. hash를 사용하는 경우 1. 많은 자료를 저장하고, 검색 속도가 빨라야하는 경우 2. 너무 빈번하게 자료를 삽입, 삭제하지 않는 경우 해쉬는 테이블에 자료를 저장할때 키값을 해시 함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장하는 자료구조이다. 버킷 번호에 자료를 넣기 때문에 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정하다. Key 값 → 해쉬 함수에 대입 → 버킷 번호 출력 장점 : 많은 자료를 저장하고 있어도 검색이 빠름, 단점 : 적은 자료를 저장하는 경우 메모리 낭비와 검색 시 오버헤드가 발생함 많은 양의 자료를 저장하는 경우 해쉬를 사용하고, 적은 양이라면 리스트가 벡터가 낫다. 참고 https://gamdekong.tistory.com/73 마우스 스와이프 구현 로직 private Vector3 m_firstPosition; private Vector3 m_lastPosition; private float m_angle; private float swipeResist = 1f; private void OnMouseDown() { m_firstPosition = Camera.main.ScreenToWorldPoint(Input.mousePosition); } private void OnMouseUp() { m_lastPosition = Camera.main.ScreenToWorldPoint(Input.mousePosition); CalculateAngle(); } private void CalculateAngle() { if (Mathf.Abs(m_lastPositio.. NULL과 nullptr의 차이 C++11 이전 버전에서는 컴파일러가 NULL을 포인터가 아니라 0과 동일하게 여김 따라서 포인터에 NULL을 할당한다면 포인터가 아니라 상수(0)로 취급받을 수 있기 때문에 nullptr로 초기화하는 것을 권장함 출처 : http://xdf0183.blogspot.com/2017/08/c-11-null-nullptr.html 이전 1 2 3 4 5 다음
