[C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘대시보드

힙이 완전이진트리이기 때문에왼쪽을 먼저 비교하여 진행하게 알고리즘을 만드는것까지는 이해했습니다.그런데 왼쪽을 통과 했을 경우에도 우측을 한번 더 비교하는 이유가 따로 있는건지 궁금합니다.-> less기준 으로 부모가 자식노드보다 크기만 하면 되는것이 아닌가 궁금합니다. 지금 코드로 하게 되면 왼쪽과 오른쪽 둘다 부모노드보다 클 경우 우측이랑 교환을 하게 되는데, 코드가 복잡해져서 굳이 처리를 안하는걸까요? else if 를 사용하지 않는 이유가 있을까요?void pop() { _heap[0] = _heap.back(); _heap.pop_back(); int now = 0; while (true) { int left = now * 2 + 1; int right = now * 2 + 2; if (_heap.size() <= left) break; int next = now; if (_heap[next] < _heap[left]) next = left; else if (_heap.size() > right && _heap[next] < _heap[right]) next = right; if (next == now) break; ::swap(_heap[next], _heap[now]); now = next; } }

안녕하세요.혹시 1단계 빅오 표기법O(1 + N + 4 * N^2 + 1)에서 4 * N^2 에서 4는 이중 포문에 조건식에 해당하는2 * n 때문에 4가 된건가요? 정확히 4의 뜻을 잘 모르겠습니다.

요약1. 왜 참조형을 사용하지 않는지 궁금합니다.2. 일반 참조형을 사용했을때는 왜 컴파일 오류가 발생하는지, const 참조형을 사용하면 컴파일 오류가 사라지는지 궁금합니다.const iterator& 또는 iterator&를 사용하지 않은 이유를 알고싶습니다.내부에서 iterator의 데이터인 _node의 값이 변경되어야 하기 때문에 const를 사용하지 않는건가? 싶어서const를 제외해보았더니, 그냥 참조 &의 경우 li.end()에서 반환하는 iterarotr값을 인자로 받지를 못하는것 같습니다.이것은 왜 그런지 궁금합니다.

T& Pop() { T ret = data[Size - 1]; // _data가 동적배열 _Size--; // 크기 1 줄여서 return ret; // 반환한다 } 에서 T ret = data[Size - 1]; 에서더 이상 유효하지 않은 데이터라Pop()함수의 반환형을 T&같이 주소로는 반환할 수 없고T처럼 복사를 하는 방식으로 반환한다고 하셨는데 T ret = data[Size - 1]; 에서 data가 더이상 유효하지 않은 데이터가 되는 이유가 궁금합니다   

반환할 때 return iterator(node) 이런식인데이러면 임시객체를 생성해서 리턴하니까return 하고 나서 사라지지 않을까요??? 예상은 해봤는데list가 iterator를 하나만 가지기 위함이라고 생각해봤습니다.new를 써서 동적할당으로 하면 함수를 호출할때마다 iterator가 늘어나니까 그럴 수 있다고 생각했는데만약 맞다면임시객체를 리턴할 때 어떤 현상이 일어나는지 알고 싶습니다

한달 후 결제할 생각인데 중간에 끊겨있어서 질문 드려요 ㅠㅍㅠ

이 이후에 바로 ret = max(ret, moveDist + Solve(4)); 계산이 이루어져야 하는 거 아닌가요? 디버깅해보니까 다시 Solve(4)가 호출?되고 캐쉬 값을 반환한 이후에 계산이 되는데 어떻게 작동하는 건가요?이 사진이 첫번째 사진 Solve(4)가 반환된 후 다음코드로 이동한거에요.

안녕하세요 강사님!Stack 강의를 복습하던 도중에 궁금증이 생겨서 질문 드립니다.강의와 직접적으로 관련된 내용이아니라 구글링으로 찾아보고 싶었는데 뭐라고 검색해야할지 잘 모르겠어서 질문을 청합니다.Stack 구현을 헤더파일에 분리해서 구현을 해보던 도중에 (cpp파일은 따로 만들지 않았습니다)강의 초반에 멤버 변수로 vector를 이용해서 만들때는 빌드가 되지 않았는데요( vector는 include해주었습니다)-오류 내용으로는 _container식별자를 찾을수 없다는 내용이였습니다<typename Container>을 추가한 버전으로는 헤더파일을 분리해도 빌드가 잘 됐습니다.위에 버전으로 main함수가 있는 cpp파일에서 코드를 입력할 시에는 돌아갔는데 왜 헤더파일로 분리한 경우 안된것인지, 또 두번째 버전은 왜 빌드가 되었는지가 궁금합니다. 관련해서 공부할 내용이나 서적을 알려주시면 감사하겠습니다!!  

18:50 에 나오는 Pos에 < 연산자는 어디서 사용되는건가요?코드에서 아무리 찾아봐도 < 는 없는데 에러가 나와서 궁금합니다..

vector에 반복문 i를 차례대로 push_back 하고 있는데요! 벡터의 푸쉬백을 들어가보면CONSTEXPR20 void pushback(const Ty& Val)이렇게 복사가 아닌 참조 형태로 되어 있던데for문이 끝나면 i도 사라지닌까 무효한 참조가 되는것 아닌가요?? 왜 가능한지? . ? 궁금합니다..

두가지 질문이 있습니다.Prim으로 맵 생성할 때 best가 왜 필요한 것인지 이해가 잘 되지 않아서 질문 드립니다. 제 생각으로는 트리와 연결된 간선들 중 어차피 가장 작은 가중치를 가지는 간선을 선택할 텐데 그걸 굳이 best로 저장하고 갱신시킬 필요가 있는 것인지...잘 모르겠습니다.또 선택한 정점과 연결된 간선들을 discovered에 넣는 부분에서 굳이 새로 발견한 정점이 있다면 continue해야 하는 이유도 잘 모르겠습니다. 그 위에서 트리에 있었다면 continue하는 부분 만으로 충분하다고 생각되어서요.참고로 두 부분을 빼도 맵은 잘 작동하기에 더욱 이해가 되질 않아 질문합니다!// 어떤 정점이 트리에 포함되어 있나? map<Pos, bool> tree; // 정점의 부모는 누구인가? map<Pos, Pos> parent; // 만들고 있는 트리에 인접한 간선 중, 해당 정점에 닿는 최소 간선의 정보 map<Pos, int32> best; // 다익스트라와 거의 유사함. // 단, 다익스트라의 best는 시작점을 기준으로 한 cost // 프림에서 best는 현재 트리를 기준으로 한 cost for (int32 y = 0; y < _size; y++) { for (int32 x = 0; x < _size; x++) { best[Pos{ y,x }] = INT32_MAX; tree[Pos{ y,x }] = false; } } priority_queue<CostEdge, vector<CostEdge>, greater<CostEdge>> discovered; const Pos startPos = Pos{ 1,1 }; // 랜덤으로 정해도 됨. discovered.push(CostEdge{ startPos, 0 }); parent[startPos] = startPos; best[startPos] = 0; while (discovered.empty() == false) { CostEdge bestEdge = discovered.top(); // 가중치 가장 작은 간선을 선택 discovered.pop(); // 새로 연결된 정점 Pos v = bestEdge.vertex; if (tree[v] == true) // 만약 트리에 v가 이미 있었다면 continue continue; tree[bestEdge.vertex] = true; // 맵에 적용 // 이전 정점(= 새로 연결된 정점의 부모) Pos u = parent[v]; int y = (u._y + v._y) / 2; int x = (u._x + v._x) / 2; _tile[y][x] = TileType::EMPTY; for (const CostEdge& e : edges[bestEdge.vertex]) // 선택한 정점과 연결된 간선들을 discovered에 넣음. { if (tree[e.vertex]) // 새로 발견한 애들이 이미 있었다면 continue continue; if (e.cost > best[e.vertex]) // 다른 경로로 더 좋은 후보가 발견되었으면 continue continue; discovered.push(e); parent[e.vertex] = bestEdge.vertex; best[e.vertex] = bestEdge.cost; } }  

제가 강의 듣기 전에 먼저 풀어보는데 Disjoint Set 클래스를 사용할 때마다 제 맘대로 수정해서 씁니다.물론 Disjoint Set의 union-find 특징은 살려서 쓰긴 하는데 Disjoint Set 쓰이는 강의마다 설명하실 때 Disjoint Set 클래스는 수정을 안하시기에 혹시나 수정하면 안되는 클래스인지 궁금하여 질문 남깁니다. (코딩 테스트같은 곳에 나왔을 때 틀린 답으로 체크될까봐 걱정돼서요...너무 소심한가요...)

player.cpp의 AStar 함수 내에서//초기값 { int32 g = 0; int32 h = 10 * (abs(dest.y - start.y) + abs(dest.x - start.x)); pq.push(PQNode{ g + h, g, start }); best[start.y][start.x] = g + h; parent[start] = start; }이렇게 { } 블록을 설정하고 그 안에서 초기화를 한 이유가 궁금합니다.

안녕하세요 1강에서 List를 구현할 때는 head 포인터 하나만 갖고 노드를 연결했는데 자료구조 편에서구현한 리스트는 head와 tail을 갖고있는데 혹시 어떤 차이가 있는걸까요?추가질문list의 중간 삽입/ 삭제도 iterator를 들고있지 않아 순차접근 하는 경우는 시간 복잡도가 O(N)인가요?

player.h와 board.h에서 pch.h를 사용한다 선언하지 않았는데 POS구조체를 어떻게 사용할 수 있는지 궁금합니다. main에 선언한 pch.h를 지우니 player.h와 board.h에서 pos에 관한 것들이 오류나 났는데, main의 선언과 관련이 있는 걸까요?

삭제하려는 노드의 왼, 오 자식이 모두 있는 경우 꼭 바로 다음 데이터로 교체하는 이유가 있나요? 예를 들어 삭제하려는 노드의 왼, 오 자식과 교체하거나 바로 이전 데이터랑 교체해도 트리 구조에 문제 없지 않나요?Replace 함수는 부모와 자식 사이의 교체만 발생한다고 가정한 함수인가요? 만약 같은 깊이의 서브트리끼리 교체한다고 하면 부모 노드와의 관계가 깨질 것 같아서요

안녕하세요.해당 문제에 대한 원리를 이해하고 싶은데혹시 이런 유형에 대한 수학적 표현이 있을까요?아니면 이런 비슷한 유형 문제를 좀 더 찾아보고싶은데 어떤 알고리즘으로 찾으면 될까요?단순히 DP로 찾아보면 다른 유형들이 나와서연습이 어렵더라구요ㅠ

상당히 길쭉하게 나옵니다.■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

강의 코드대로 중괄호({})로 pos 구조체 변수를 생성, 초기화 하면 항상Pos{ -1, 0 } >> 이 부분에서error C2440: 'initializing': cannot convert from 'initializer list' to 'Pos'note: No constructor could take the source type, or constructor overload resolution was ambiguous에러가 뜹니다.해결 하긴 했는데Pos 구조체 안에서 int32 y = 0; int32 x = 0;로 초기화 시키지 않고 int32 y; int32 x;로 바꾸니까 바로 되더라구요.우선 동작은 잘 되는데 혹시 뭐가 문제인건지 알 수 있을까요? 

제목 그대로 맵이 되게 이상하게 나오는데 이유를 모르겠습니다. 3달 전까지만 해도 잘 나왔는데 다시 복습하려고 틀어보니 이상해져서 질문드립니다.