코드 깎는 개발자

[알고리즘] 이진 탐색 트리 (Binary Search Tree) https://doanhan.tistory.com/49?category=583264 [알고리즘] 이진 트리 (Binary Tree) [알고리즘] 이진 트리 (Binary Tree) 이진트리는 기본적으로 많이 사용되는 비선형 자료구조이다. 기존에 힙에서도 이진트리를 사용했는데 그것은 완전 이진 트리로 배열로 표현이 가능하지만 doanhan.tistory.com 이진 탐색 트리는 특정한 특징을 가지고 있는 이진 트리를 의미한다. - 각 노드에는 중복되지 않는 키가 있다. - 루트 노드의 왼쪽은 루트보다 작은 값이, 오른쪽은 루트보다 큰 값으로 구성되어야 한다. - 서브 트리들도 전부 위와 같은 구성으로 이루어져야 한다. 이진 트리는 전위, 중..

[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체는 체라는 말처럼 무엇인가를 걸러내는 거나 판별하는 것을 의미하는데, 이것은 소수(PrimeNumber)이다. 소수는 2개의 약수(1과 자기 자신)만을 가지고 있는 수이다. 즉, 에라토스테네스의 체는 소수를 대량으로 빠르게 판별할 수 있는 알고리즘입니다. 먼저 일단 소수를 판별하는 방법을 구현해보겠습니다. #include using namespace std; //소수 판별 bool IsPrimeNumber(int x) { for(int i = 2; i < x; i++) { if(x%i ==0) retur false; } return true; } 위는 간단하게 소수를 구하는 방법이다. 하지만 시간복잡도가 O(N)로..

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 피보나치 수열과 같이 한 번 푼것을 여러번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법으로 사용한다. 그리고 다이나믹 프로그래밍은 두가지 가정하에 사용할 수있는데 1) 큰 문제는 작은 문제로 나눌 수 있다. 2) 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 다이나믹 프로그래밍은 큰 문제를 해결하기 위해서 그것을 작게 나누어 해결한 뒤 그것을 이용하여 답을 구하는 것이다. 하지만 이 과정이 분할정복과 다른 점은 메모제이션(Memozation)이 사용된다는 점이다. 이미 계산한 것을 저장하는 것으로 나중에 동일한 계산을 할 때는 저장된 값을 반환하여 사용하..

[알고리즘] 이진 트리 (Binary Tree) 이진트리는 기본적으로 많이 사용되는 비선형 자료구조이다. 기존에 힙에서도 이진트리를 사용했는데 그것은 완전 이진 트리로 배열로 표현이 가능하지만 완전 이진 트리가 아닌 경우는 배열로 표현이 힘들다. 시간 복잡도 이진트리를 탐색 시 계속 1/2로 나뉘어서 계속 탐색하기 때문에 O(log₂N)의 복잡도를 가진다. 이진 트리 탐색 방법 1. 전위 순회 (Preorder Traversal) : 자기 자신 - 왼쪽 자식 - 오른쪽 자식 2. 중위 순회 (Inorder Traversal) : 왼쪽 자식 - 자기 자신 - 오른쪽 자식 3. 후위 순회 (Postorder Traversal) : 왼쪽 자식 - 오른쪽 자식 - 자기 자신 후위 순회는 계산기와 같은 수식에 자..

[알고리즘] 크루스칼 알고리즘 (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..

[알고리즘] 계수 정렬 (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)은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재하..