programing/Algorithm8 움직이는 오브젝트의 순서 정하고 추월 체크 하기 1. 가장 단순하게... 자신을 기준으로 앞에 있는지 뒤에 있는지를 판단하여 순서를 정함 -> 두 차가 방향이 엇갈릴 경우 누가 앞에 있고 뒤에 있는지 판단하기 힘듦 2. 추월에 대하여 한 차가 다른 차를 추월 할 경우 그 사이에 있는 차를 추월 해야 하므로 앞 뒤로 가장 가까운 차만 체크함 3. 한 프레임 사이에 여러대를 추월할 가능성이 있으므로 추월시 그 다음 차에 대하여 앞 뒤 체크를 계속 함 3. 만약 순서가 이미 정해져 있는데 방향이 엇갈려 있는 경우, 추월하기 위해선 같은 도로에서 같은 방향으로 추월 해야 하므로 추월 체크를 하지 않는다. 4. 시작시 순서가 정해져 있지 않으면... 임의로 정하거나, 코스에 충돌 객체를 놓아서 정하거나... -> 같은 방향을 가리키더라도 S자 코스의 경우 뒷차.. 2016. 12. 1. 허프만 코드 - 길이가 변하는 이진 코드(variable-length binary code) - 전치 코드 > 빈도대로 정렬한 다음 빈도가 클 수록 길이가 짧음 -> 빈도에 대해 최적화가 덜 됨 => 허프만 코드 - 허프만 코드 > 낮은 빈도순으로 정렬한 다음 가장 낮은 빈도부터 이진 트리를 만들어 나감 > 트리가 만들어 질 경우 노드들의 빈도의 합을 가지고 트리와 원소를 같이 정렬하여 다시 가장 낮은 비도 부터 트리를 만들어 나감 > 알고리즘 만들때 우선순위 큐 이용 2015. 6. 5. 비재귀 퀵소트 #include #include void QuickSort(int* array, int n) { int start, end, left, right; int pivot, t; int* pBase; int top = -1; pBase = (int*)malloc(sizeof(int)*(2*n+2)); pBase[++top] = n-1; pBase[++top] = 0; while(top != -1) { start = pBase[top--]; end = pBase[top--]; if(end-start > 0) { pivot = start; left = start + 1; right = end; while(1) { while(array[left] < array[pivot] && left= left && array[.. 2015. 6. 4. 그래프 관련 알고리즘 - 신장 트리 : 순환이 없는 트리 > 깊이 우선 탐색(DFS : Depth-First Search) -> 깊이 우선 신장 트리(Depth First Spanning Tree) > 넓이 우선 탐색(BFS : Breadth-First Search) -> 넓이 우선 신장 트리(Breadth First Spanning Tree) - 최소 신장 트리 : 가중치의 합이 최소인 신장트리 - Kruskal Algorithm > 그래프의 모든 간선을 비용 순으로 정렬한 뒤 낮은 비용을 가지는 순환시키지 않는 간선을 선택 1) 모든 간선을 가중치 값에 따라 오름 차순으로 정렬 2-1) 가장 가중치가 작으면서 순환을 발생시키지 않는 간선 추출, 순환시 해당 간선 제외 2-2) 그래프의 모든 노드가 .. 2015. 6. 4. 이전 1 2 다음