코드 깎는 개발자

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 다음 노드들을 모두 한번씩 들르는 최소 경로를 알아보자! 비용이 짧은 순서대로 그래프에 포함시키자!! 일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에 모든 비용의 정보를 오름차순으로 정렬한 뒤에 비용이 작은 것부터 차근 차근 그래프에 포함시키면 된다. 단 사이클을 형성하는 경우는 포함에서 제외한다. 소스코드 구현 (C++) #include #include #include using namespace std; int GetParent(int parent[], int x) { if (paren..

[알고리즘] 합집합 찾기 (Union Find) 대표적인 그래프 알고리즘이며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판변하는 알고리즘이다. 숫자들을 설정하고 깊이 우선 탐색하는 프로그램을 작성하자! 부모를 합칠 때 일반적으로 더 작은 값으로 합치며 이것을 합침(Union)이라고 하며 노드를 선택해서 그 노드가 같은 합침에 속해있는지를 찾는 알고리즘이다. 소스코드 구현 (C++) #include using namespace std; //부모 찾기 int GetParent(int parent[], int x) { if (parent[x] == x) return x; return pare..

[알고리즘] 깊이 우선 탐색 (DFS) 깊이 우선 탐색(Depth First Search, DFS)는 BFS와 마찬가지로 맹목적으로 각 노드를 탐색할 때 주로 사용된다. BFS와는 다르게 보다 깊은 것을 우선적으로 탐색을 하며 LIFO의 구조를 가진 스택이 사용된다. 하지만 스택을 사용하지 않아도 구현이 가능하며 이것은 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다. 다음 숫자들을 깊이 우선 탐색하는 프로그램을 작성하자! 1. 스택의 최상단 노드를 확인 후 방문처리를 한다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않는 인접 노드가 없으면 스택에서 최상단 노드를 뺀다. 소스코드 구현 (C++) #include #include us..

[알고리즘] 너비 우선 탐색 (BFS) 너비 우선 탐색(Breadth First Search, BFS)은 맹목적 탐색을 하고자 할때, 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용하며 먼저 들어온 것을 먼저 처리해준다는 점에서 큐를 이용한다. 다음 숫자들을 너비 우선 탐색하는 프로그램을 작성하자! 1. 큐에서 하나의 노드를 꺼낸 후 방문 처리를 한다. 2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 소스코드 구현 (C++) #include #include #include using namespace std; void BFS(vector* arr, int start) { int size..

[알고리즘] 큐(Queue) FIFO(First In First Out) 먼저 들어온 것이 먼저 나가는 구조로 스택과는 반대되는 개념의 자료구조이다. 다음 숫자들을 삽입/삭제 해보자 7, 3, 2, 삭제 , 5, 삭제 소스코드 구현 (C++ / STL) #include #include using namespace std; int main() { queue q; q.push(7); q.push(3); q.push(2); q.pop(); q.push(5); q.pop(); while (!q.empty()) { cout

[게임수학] 삼각함수 삼각함수 직각삼각형을 구성하는 세 변에서 두 변을 뽑아 각각의 비례관계를 나타낸것을 삼각비라고 하며 대표적으로는 사인(Sine), 코사인(Cosine), 탄젠트(Tangent)가 있다. 위 직각삼각형을 데카르트 좌표계상에 배치를 하고 사잇각의 범위를 실수 전체로 확장을 한 대응관계를 삼각함수(Trigonometric Function)이라고 한다. 만약 반지름 r = 빗변 = c = 1, 높이 = b, 밑변 = a 일때, sinθ = 높이 / 빗변 = b / c = b /1 = b cosθ = 밑변 / 빗변 = a / c = a / 1 = a 즉, 삼각함수 a² + b² = c² 에 대입하면 cos²θ + sin²θ = 1 이다. 삼각함수의 성질 반지름이 1인 원에서 만약 회전을 하지..

[알고리즘] 스택 (Stack) LIFO(Last In First Out) 나중에 들어온 것이 먼저 나가는 구조로 FIFO의 큐와는 반대되는 개념을 가지고 있다. 소스코드 구현 (C++ / STL) #include #include using namespace std; int main() { stack s; s.push(3); s.push(4); s.pop(); s.push(3); s.push(1); s.pop(); s.push(3); s.push(2); s.pop(); while (!s.empty()) { cout

[게임수학] 벡터 벡터 (Vector) 공간을 만들려면 직선을 벗어나 넓은 평면으로 무대를 확장해야한다. 평면에서 시각적으로 의미있는 물체를 생성하기 위해서는 평면을 구성하는 원소가 필요하며 이 원소를 벡터라고한다. 데카르트 좌표계 데카르트 좌표계의 한 원소는 동일하게 순서쌍으로 표현하며 (x, y), 이것을 좌표라고 부른다. 스칼라와 벡터 평면의 좌표 (x, y)는 두 실수 x와 y를 결합해 만들어지기 때문에 좌표의 연산은 실수가 지니는 연산의 성질을 바탕으로 설계돼야 한다. 두개 이상의 실수를 곱집합으로 묶어 형성된 집합을 공리적 집합론의 관점에서 규정한 것을 벡터 공간(Vector Space)라 하며, 벡터 공간의 원소를 벡터(Vector)라고 한다. 공리적 집합론의 관점에서는 특정한 수의 집합을 ..

[알고리즘] 계수 정렬 (Counting Sort) 특정한 범위 내에 속해있다면 O(NlogN)의 기존 정렬들보다 빠른 O(N)의 시간복잡도를 가질수 있는 알고리즘으로 단순하게 크기를 기준으로 세는 알고리즘이다. 크기를 기준으로 갯수를 세보자!!! 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자! 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 위의 숫자들은 5이하의 숫자라는 범위안에 들어가 있다. 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 0 0 0 0 0 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 0 0 0 0 1 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 1 2 3 4 5 1 0 0 ..

[알고리즘] 힙 정렬 (Heap Sort) 힙정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 따라서 힙(Heap)에 대해서 알아봐야하는데 또 힙을 알기 위해서는 선행적으로 이진 트리(Binary Tree)를 알고 있는 것이 좋다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말한다. 즉, 이진트리는 모든 노드의 자식이 2개 이하인 노드를 가지고 있는 구조이다. 그리고 데이터 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근 차근 들어가는 구조의 이진트리를 완전 이진 트리 고한다. 힙(Heap)은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재하..