코달

보호되어 있는 글입니다.

개념다익스트라 알고리즘과 거의 비슷하다.다른 점은 간선을 추가하는 방식이다. 다익스트라가 출발점을 기준으로 간선의 가중치를 계산했다면, 프림은 연결된 정점 그룹을 기준으로 계산한다. 우선 정점 하나 정점 그룹에 추가한다. 정점 그룹에 연결된 간선들을 간선 후보로 둔다.간선 후보들 중 정점 그룹 내 다른 정점 과 연결되지 않은 가장 가중치가 낮은 간선을 추가한다.그 간선에 연결된 새로운 정점을 정점그룹에 추가한다.모든 정점이 연결될 때까지 2~5를 반복한다.

개념스패닝 트리 (간선의 수 최소. 사이클이 생기면 안됨). 를 만드는 알고리즘그리디 알고리즘. 길이(가중치)가 가장 작은 간선부터 연결함. 근데 그러다 보면 사이클이 생길 수 있음.사이클을 피하는 알고리즘 필요. 방법 : 사이클 피하기간선이 연결된 노드들을 그룹으로 묶고 같은 그룹끼리 연결하는 간선은 피하는 것, Disjoint Set을 활용함. 우선 간선후보들을 가중치 순으로 정렬함간선 후보목록을 순회하며 가중치가 가장 작은 간선후보부터 사이클 검사를 함(Disjoint Set을 사용해 간선에 연결된 두 정점이 같은 팀인지 확인함). 참고 DisjointSet: https://ddukddaksudal.tistory.com/54같은 팀이면 다음 간선 후보로 넘기고 다른 팀이면 간선을 추가함(연결함). ..

개념Union Find 라고 하기도 한다. 트리 구조를 이용한 상호 배타적 집합의 표현 팀끼리 합쳐지는 상황.어떤 팀(팀 1)이 다른 팀(팀 2) 밑으로 들어가는 상황. 두 팀원들의 팀 ID를 같게 만들어야 함. 보통은 유저 배열을 모두 돌면서 그 유저가 팀1 소속이면 팀 ID를 팀 2로 만들어주는 방법을 생각했을 것이다.그러나 모든 유저 배열을 순회하는 것은 비효율 적이다. 이럴 경우 Disjoint Set을 사용하면 좋다. 우선 모든 유저의 팀 ID를 자신의 인덱스로 초기화한다.어떤 유저(1) 가 다른 유저(2)의 밑으로 들어가면 유저 1의 팀 ID를 2로 만든다. 유저 1의 인덱스는 여전히 1이다. 팀 ID만 2가 된 것이다.이 상태에서 유저 2 팀이 유저 4를 팀원으로 가진 유저 3팀의 밑으로 ..

테이블 : 원하느ㅏㄴ 키 값을 상수시간 에 찾을 수 있음. hash_map, unorderd_map, dictionary가 이것임. 해쉬그냥 vector, 배열과 차이는 index가 아닌 key로 값을 찾을 수 있다는 점임. 충돌문제 해결선형 조사법 : key +1 > key +2 -> ...이차 조사법 : key + 2 -> key +4 -> ...체이닝 : 통 속의 통. vector> . map vs hash_map (C++11 표준 unoreded_map) map : RedBlack tree hash_map : unorderd map, (C# dictionary)

레드블랙트리 란?레드블랙트리는 이진 탐색 트리의 노드가 편향적으로 배치되어 트리의 균형이 맞지 않을 수 있다는 단점을 보완한 균형 이진 트리이다. 즉 이진 탐색 트리에 데이터를 삽입하고 균형을 맞추는 알고리즘 가동시키는 자료구조라고 할 수 있다. 레드블랙트리는 아래와 같은 특성을 가진다. 이러한 특성을 만족하면 자동적으로 균형이 맞춰지게 된다. 노드는 레드 혹은 블랙루트노드는 블랙리프노드(NIL)는 블랙레드노드의 자식은 모두 블랙. 블랙노드만이 레드노드의 부모가 될 수있음.어떤 노드부터 리프노드에 도달하는 경로는 리프노드를 제외하고 모두 같은 블랙노드 수를 가진다.이런 특성을 맞추기 위해서는 노드 삽입, 삭제 시 추가적인 알고리즘이 적용되어야 한다.이 알고리즘을 따라 코드를 구현하는 작업은 어렵지 않으..

DFS : 깊이우선 탐색 BFS : 넓이 우선 탐색 다익스트라 : 모든 노드로 가는 최소 거리, 경로 A* : 목적지를 향해 가기. 다익스트라와 비슷하지만 가중치를 계산할 때 목적지와 얼마나 가까운지를 계산하게 됨.Open List : Close List에 연결된 노드, 가중치 값 계속 업데이트Close List : 처리 완료된 노드F(최종 점수) = G(시작점에서 해당 좌표까지 이동하는데 드는 비용) + H(목적지에서 얼마나 가까운지, 휴리스틱)

디퍼드(Deffered) 렌더링 : 포워드 렌더링. 셰이더에서 계산한 중간 과정 정보를 저장해두고 재사용함. 색상, 노말, 깊이 등 정보를 Render Target에 저장해놓고 최종적으로 FS(Lighting) 적용함. Render Target 은 사실상 텍스쳐와 같다. 화면에 그려질 내용이 텍스쳐에 담기는 것이다. 이 렌더 타겟들을 그룹으로 나누어 묶는다. Renter Target Group으로 만든다. SwapChain 그룹, 글로벌 그룹(포지션, 노말, 컬러) 등.

직교투영 이란 카메라가 물체를 찍을 때 원근법을 무시하고 멀리 있든 가까이 있든 같은 크기로 화면에 출력하도록 하는 방식이다. 일반 물체들을 촬용하는 원근 투영 방법과는 대비되는 방식이다. 이러한 특징때문에 UI 요소들을 촬용하는 용도로 주로 쓰인다. 일반 물체들은 원근투영 카메라로 촬영하고, UI는 직교투영 카메라로 촬영한 뒤, 한 화면에 두 카메라가 촬영한 영상을 합쳐서 출력하게 된다. 그런데 일반 물체와 UI를 어떻게 구분할까? 답은 '레이어' 다. 카메라마다 촬영할 레이어를 지정하고, 물체마다 자신이 어떤 레이어인지 지정해두는 식이다. 카메라에 int32 CullingMask를 지정해서 어떤 레이어를 찍을지 지정한다.

필요성 : 기존의 오일러 회전 방식의 문제점 짐벌락 현상 때문. 여러 회전축의 회전이 결합되면 생기는 문제이다. 설명하자면 어떤 축이 회전함에 따라 다른 축이 변화하게 되는데, 이 때문에 두 축의 방향이 겹치는 순간 하나의 축이 소실되어버리는 현상이 나타난다. 세 개의 축을 회전시킬 때 두 번쨰로 회전시키는 축이 이 문제를 일으킨다. 사원수 : 사원수는 놀랍게도 복소수를 이용해 회전을 한다. 두 복소수를 곱하면 복소수를 극좌표계로 표현했을 때 각도를 더한 벡터가 나온다. 삼차원 벡터 회전 공식 : 벡터 V를 a 축으로 Th 만큼 회전시킨 벡터 V' = v*cosTh + (v . a)*a*(1-cosTh) + (a x v)sinTh 쿼터니언 q는 xi + yj +zk + w의 형태 또는 Vect(x,y,z..