게임 개발 기록

Tree + (heap)   트리는 매우 중요한 자료구조 중 하나이다.연결리스트는 노드들이 한 줄로 연결된 선형적인 자료구조인 반면트리는 부모 - 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조이다. 추상적으로 표현하면 연결 리스트처럼 데이터를 저장하고 있는 노드와 노드를 연결하는 에지(또는 링크)로 구성된다.연결 리스트와 차이점은 에지가 부모 - 자식 관계를 표현한다는 점에서 차이가 있다. 트리 용어 부모노드 / 자식노드 : 부모노드는 자식 노드를 위에 있는 노드를 말한다.자식 노드는 1이상의 레벨을 가지는 노드로 부모노드 밑에 있는 노드이다. 조상노드 / 자손노드 : 트리 노드간의 레벨간의 관계가 2이상 차이나는 노드를 말한다.보다 아래면 자손노드 보다 위면 조상노드라고 한다. 루트노드 : 모든..

// 삽입 정렬 { int arr[] = { 1,2,4,5,3,6 }; int size = sizeof(arr) / sizeof(arr[0]); Print(arr, size); int i = 4; int key = arr[i]; int j = i; for (j = i; j > 0 && arr[j-1]>key; j--) { if (arr[j - 1] key; j--) { arr[j] = arr[j - 1]; cout

#include #include #include #include #include #include #include #include #include using namespace std; bool CheckeSorted(int arr[], int size) { if (arr[0]

static int ListNum = -1; class List { public: List* CurPtr = this; List* BeforePtr = nullptr; List* AfterPtr = nullptr; int Index = 0; int Value = 0; bool IsDummy = false; ~List(); }; // 빈 List 생성 void InitialList(); // 원하는 만큼의 수와 해당 값으로의 초기화된 List 생성 void InitialList(int MaxIndex, int Value); // 부분 삭제 void DeleteIList(int iter, List* InDeleteList); // 전체 삭제 void DeleteAllList(); // 삽입 void Push..

연결 리스트란? 필요할 때마다 바구니를 하나씩 마련해서 그곳에 데이터를 저장하고 이들을 배열처럼 서로 연결한다. 라는 개념으로 접근하면 이해하기 쉽다. 바구니 역할이 구조체가 되고, 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다. 그리고 구조체 Node의 변수를 가리켜 '노드'라 한다. 이는 데이터를 담는 바구니보다는 연결이 가능한 개체라는 사실에 중점을 두어 지은 이름이다. 이렇듯 구조체의 정의 하나만 가지고도 연결 리스트의 기본 원리라고 말할 수 있다. 이를 그림으로 표현하면 다음과 같다. 연결 리스트에서의 데이터 삽입 다음 임의 코드로 연결 리스트의 삽입 개념을 잡아보자. Node * head = NULL;// 리스트의 머리를 가리키는 포인터 변수 Node * tail = NULL;// 리스트..

으래 그냥 리스트라고 하면 연결 리스트를 종종 떠올린다. 하지만, 리스트에는 순차 리스트와 연결 리스트가 있다. 순차 리스트는 배열을 기반으로 구현된 리스트이며 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다. 하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일하다고 해서 문제가 될 것은 없다. 물론 각각의 특성의 차이 때문에 ADT에 차이를 두기도 한다. 이는 ADT는 각종 자료구조들의 표준이 아니기 때문이다. 정의하는 사람이나 회사에 따라서, 다시 말해 피룡에 따라서 ADT에도 차이가 난다. 물론 필요에 따라 확장도 가능하다. 하지만 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 ADT가 정의되는 것은 아니다. 리스트 ADT 정의를 위해서 ..

트리 순회 일단 트리가 구성되어 있다면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 잇다. 다양한 순회 방법에 대해 간략히 알아보자. 전위 순회 (preorder traversal) 이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문한다. 여기서 '전위(pre)'는 상위 노드를 하위 노드보다 먼저 방문한다는 뜻이다. 전위 순회는 항상 부모 노드를 방문한 다음 왼쪽 자식 노드, 오른쪽 자식 노드를 차례로 방문한다. 이러한 방식의 순호를 루트 노드에서만 수행하는 것이 아니라 루트 노드 아래의 모든 서브 트리에 대해 적용한다. 중위 순회 (in-order traersal) 중위 순회 방법은 왼쪽 ..

하노이 타워 코드 #include void HanoiTowerMove(int num, char from, char by, char to) { if (num == 1)// 이동할 원반의 수가 1개라면 { printf("원반1을 %c에서 %c로 이동 \n", from, to); } else { HanoiTowerMove(num - 1, from, to, by); printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to); HanoiTowerMove(num - 1, by, from, to); } } int main(void) { // 막대 A의 원반 3개를 막대 B를 경유하여 막대 C로 옮기기 HanoiTowerMove(3, 'A', 'B', 'C'); return 0; }

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고,C언어는 이렇듯 중요한 재귀를 지원하는 언어이다. 재귀함수의 기본적인 이해 재귀함수란 무엇인가?재귀함수란 다음과 같이 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. void Recursive(void){ printf("Recursive call! \n"); Recursive(); // 나 자신을 재호출한다}  위 형태의 함수가 재귀호출이다.그렇다면 재귀 호출은 어떻게 이해해야 할까?  다음 그림과 같은 구조는 매우 단순해 보이지만,그림 내용대로 재귀함수를 이해하는 것이 여간 쉬운 일은 아니다. 그렇다고 위 그림이 재귀호출에 대해서 잘못 설명하고 있다거나 하지는 않는다. 해당 함수는 완료되지 않은 함수를 다시 호출하는 것이 ..

#include int BSearch(int ar[], int len, int target) { int first = 0; int last = len - 1; int mid; int opCount = 0;// 비교연산의 횟수를 기록 while (first