그냥 게임개발자

이진트리(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) 간선은 정점을 잇는 선을 의미합니다. 경로 또는 관계가 될 수 있습니다. 예를 들어서 어떠한 물건 또는 어떠한 위치로부터 무언가를 통해 이어진다라고 하였을 때, 어떠한 물건, 어떠한 위치는 정점이며, 무언가를 통해 이어진다는 간선이 됩니다. 지하철 노선도를 예로 보여드리겠습니다. 여기서 보면 모든 정점은 하나의 역들이며 그것을 이어주는 것이 간선입니다. 그럼 사람으로도 예를 들어보죠. 지금 왼쪽의 사람과 오른쪽의 사람은 정점이고..

등비수열이란? 한 항과 다음 항의 비율이 같은 수열을 등비수열이라고 합니다. 예를 들어 4, 12, 36, 108 ...이라는 숫자가 있다고 보았을 때 12라는 숫자는 4로 나누었을 때 3이라는 숫자가 나옵니다. 36은 12라는 숫자로 나누었을 때 3이라는 숫자가 나오구요. 그러면 다시 4에서 3을 곱하면 12가나오죠 12에서 3을 곱하면 36이나오죠. 이렇 듯 공통비율을 가진 것들을 등비수열이라고 합니다. 모두 3배씩 증가하기 때문에 3을 공비라 하며, 첫번째 항을 초항이라고 합니다. 그렇다면 공비가 3이고 초항이 4인 등비수열이라고 표현할 수 있습니다. 등비수열에는 2개의 공식이 있습니다. 우리가 위에서 예를 들은 것을 넣어보죠. 만약 더할 숫자가 108까지 4, 12, 36, 108 이렇게 4개라고..

등차수열이란 1부터 n까지의 합을 구하는 공식이다. 시그마라 하죠. 이 등차수열을 예를들어 n = 5라고 치게 되면 5(5 + 1) / 2 = 30 / 2 = 15라는 값이 나온다. 1 + 2 + 3 + 4 + 5 = 15가 나오죠. 정확하죠? 그러면 코드로 확인해봅시다. #include using namespace std; int main() { int n = 5; int ret = 0; // 그냥 for문을 돌려 사용한 등차수열 for (int i = 1; i

에라토스테네스의 체 이분은 아주 대단하신 분이에요. 지구의 크기를 처음으로 계산하신 분이며 소수를 걸러내는 에라토스테네스의 체를 고안한 사람이기도 합니다. 그래서 우리는 에라토스테네스의 체를 배울 건데 소수가 아닌 값들에 대한 bool 배열을 만들어서 소수만을 걸러낼 수 있는 방법이 있습니다. 어우 저게 뭔소리냐. 우리가 아는 소수는 3.141592 뭐 이런거지만 소수 2를 나누었을 때 1과 2밖에 없죠? 3의 약수는요? 3도 똑같죠 1과 3 53의 약수는요? 똑같습니다 1과 53 이런 것들을 소수라고 합니다. #include #include using namespace std; const int MAX = 40; bool che[MAX + 1]; vector Eratosthenes(int max) { ..

모듈러 연산이란 a랑 b라는 숫자가 있을 때 a를 b로 나누었을 때 나머지만 필요할 때가 있습니다. 이러한 경우를 위해 우리는 % 즉 modular를 사용하게 되져 이것을 줄여서mod라고 불리는 연산자인데 a ≡ b mod n과 b ≡ c mod n은 a ≡ c mod n을 의미한다. ≡는 합동관계는 똑같다라는 소리입니다. a mod n 과 b mod n이 같다면 a ≡ b mod n이라는 소리죠. 그렇다면 아래와 같이 설명할 수 있겠죠. [ (a mod n) + (b mod n) ] mod n = (a+b) mod n과 같다라는 이야기입니다. [ (a mod n) - (b mod n) ] mod n = (a-b) mod n [ (a mod n) * (b mod n) ] mod n = (a*b) mod ..