그냥 게임개발자

이진트리(BT, Binary Tree) 이진트리 BinaryTree라고도 부릅니다. 이지트리란 각각의 노드의 자식노드 수가 2개 이하로 구성되어 있는 트리를 의미하며 아래와 같이 구분합니다. 왼쪽부터 시작해서 정이진트리, 완전 이진트리, 변질 이진트리, 포화 이진트리, 균형 이진트리라고 합니다. 정이진 트리(Full Binary Tree) 자식 노드가 0 또는 2개인 이진트리를 말합니다. 완전 이진트리(Complete Binary Tree) 왼쪽에서부터 채워져있는 이진 트리를 의미합니다. 마지막 레벨(위 사진은 레벨3 or 2)을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있는 것을 의미합니다. 변질 이진 트리(Degenerate Binary Tree) 자식 노드가 ..

트리 말그대로 나뭇가지를 생각하면 쉬운데요. 이게 트리라고 하는 건데 왜 나뭇가지라고 생각하기 편하면요. 제가 그려봤어요 나뭇가지 같죠? 그래서 tree라고 부르는 것 같아요. 뭐 암튼 트리(Tree) 트리란 자식노드와 부모노드로 이루어진 계층적인 구조를 가지면서 무방향 그래프의 일종이며 사이클이 없는 자료구조형입니다. 부모노드와 자식노드는 뭐냐면 N을 기준으로 보자면 H가 부모노드가 되며 O는 자식노드가 됩니다. 근데 저번 포스팅에 양방향 그래프와 단방향 그래프를 배웠는데 이거는 무방향 그래프죠? 방향 그래프는 direct graph라고 불리며 무방향 그래프는 undirected graph라고 불립니다. 무방향은 말 그대로 방향이 없습니다. 트리를 설명할 때는 보통 무방향 그래프로 설명을 합니다. tr..

이번에는 indegree와 outdegree를 배울건데요. degree라는 뜻은 차수라는 뜻입니다. 차수(degree) 한 정점에 연결되어 있는 간선의 개수를 의미합니다. 그림을 보니 좀 쉽죠? 들어오는 차수의 개수가 indegree 나가는 것이 outdegree입니다. 그렇다면 아래는 어떨까요? v1의 indegree는 3개이며 outdegree는 4개입니다. v2의 indegree는 4개이며 outdegree는 3개입니다. 이해가기 쉽죠? 가중치 가중치란 정점과 정점사이에 드는 비용을 뜻하는데요. 예를 들어 v1에서 v2까지 가는 비용이 한칸이라면 v1에서 v2까지의 가중치는 한칸입니다. 그렇다면 저 위의 사진을 보았을 때 v1에서 v2까지 가는 비용이 4칸이니 가중치는 4칸이 되겠네요. 저번 정점과..

그래프 이론의 기초를 배우려고 합니다. 기초중의 기초중에 정점과 간선이 있는데 정점(Vertex) 정점은 노드라고도 불리기도 하고 그래프를 형성하는 기본 단위중 하나입니다. 정점은 분할할 수 없는 객체이어야 하며 점으로 표현되는 위치, 물건 등이 될 수 있습니다. 간선(Edge) 간선은 정점을 잇는 선을 의미합니다. 경로 또는 관계가 될 수 있습니다. 예를 들어서 어떠한 물건 또는 어떠한 위치로부터 무언가를 통해 이어진다라고 하였을 때, 어떠한 물건, 어떠한 위치는 정점이며, 무언가를 통해 이어진다는 간선이 됩니다. 지하철 노선도를 예로 보여드리겠습니다. 여기서 보면 모든 정점은 하나의 역들이며 그것을 이어주는 것이 간선입니다. 그럼 사람으로도 예를 들어보죠. 지금 왼쪽의 사람과 오른쪽의 사람은 정점이고..

배열의 이름 = 주소값이라는 소리를 어디선가 들어볼 수 있을 것이다. 이것을 Array to Pointer decay라고 한다. int a[N]라는 N개의 크기를 가진 변수가 있다. int *c = a; 이렇게 담을 수 있다? int[]와 int는 서로 다른 타입이다... 근데 담을 수 있다. ??? ㅇㅇ 담을 수 있어요 그래서 Array to Pointer decay라는 것이다. 포인터는 배열의 이름을 담을 수 있다...! 어떠한 Type[N]이 Type*로 담을 수 있다는 것이다. 이렇게 담을 때 int* c = a;일 때! a의 크기는 decay! 크기가 부식이 된다는 것이다! 그리고 a는 배열의 첫번째 주소가 바인딩이 된다. 이게 Array to Pointer decay라는 현상이다. 포인터의 배..

예를 들어 int / float를 계산하게되면 어떤 타입으로 변환이 되어 나올까? 바로 float다. 이렇게 타입이 변환이 되는 것을 암시적 형변환이라고 하는데 우선순위는 아래와 같다. 1 long double 2 double 3 float 4 unsigned long long 5 long long 6 unsinged long 7 long 8 unsigned int 9 int(lowest) 이 때문에 vector의 size()를 기반으로 음수가 나올 수 있는 연산을 할 때 주의해야 한다. vector의 size()라는 메서드는 unsgined int를 반환한다. 예를 들어 v.size()값이 8이면 v.size() - 10 이렇게 연산을 할 때 결과값은 음수가 나와야 하지만 unsigned int와 in..

저번에는 재귀함수로 순열을 만들었다. 이번에는 반복문을 통해 순열을 만들어보자. 일단 코드를 봐보자. 사실 반복문은 쉽다. #include #include using namespace std; int main() { vector ret = {1, 2, 3}; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 3; ++k) { if (i == j || j == k || k == i) continue; cout

조합이란? 순열 글을 포스팅 할 때 순서있는 건 순열 순서 상관 없이 조합 이라고 했다. 조합에는 순서가 없다. 그저 몇명을 뽑아서 갈 것인가를 쓸 때 조합을 쓴다. 순서따윈 상관없고 오로지 몇명을 '다양하게'뽑을 때 사용하는 것 공식을 먼저 보자 예를 들어 5개 중에 3개를 순서 상관없이 뽑는다면 공식에 사용되는 건 이렇다 5C3 그럼 결국 이것을 대입해보면 5! / 3!(5-3)!이다. 그럼 결국 풀어서 설명하자면 5 * 4 * 3 * 2 * 1 --------------------- 3 * 2 * 1 * 2 * 1 이렇게 표현이 되겠다. 그렇다면 5 * 4 * 3 * 2 * 1 --------------------- 3 * 2 * 1 * 2 * 1 뺄 것들을 빼면 5 * 4 / 2가 되어 20 / ..