분류 전체보기
-
합집합 찾기(Union-Find)알고리즘/탐색 2021. 12. 25. 01:16
서로소 집합 알고리즘 : 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별. (1) 자기 자신을 부모로 가진다. (2) A,B가 연결되어 있을 때 더 작은 값을 부모로 합친다 (Union) (3) A,B,C가 연결되어 있을 때 재귀함수를 이용해서 가장 작은 값인 A로 부모를 지정한다.(Union-Find) Find 알고리즘 : 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘. Union-Find는 최소 비용 신장 트리를 만들기 위한 알고리즘인 Kruskal 알고리즘에 주로 사용됨. //부모 노드를 찾는 함수 int getParent(int parent[], int x){ if(parent[x] == x) retu..
-
이분 탐색(binary search)알고리즘/탐색 2021. 12. 25. 01:05
이분 탐색 : 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교하여 원하는 결과를 도출해냄. 배열 내 데이터들이 정렬되어 있어야 사용할 수 있는 알고리즘이며, 입력 데이터가 많거나, 탐색 범위가 넓은 편. 시간복잡도: O(logN) 확인할 때마다 원소의 개수가 절반씩 줄어듦으로써 시간 복잡도는 logN에 비례하는 시간임. #include using namespace std; int binary_search(int arr[], int length, int target) { // 반복적 int start = 0; int end = length-1; int mid; while(start target) { end = mid-1; } else { ..
-
깊이 우선 탐색(DFS)알고리즘/탐색 2021. 12. 25. 00:51
깊이 우선 탐색(Depth First Search) : 탐색을 하는 데 있어 깊은 것을 우선적으로 하여 탐색하는 알고리즘. 스택이 사용되지만, 컴퓨터는 구조적으로 시스템 스택 프레임의 원리를 사용하기때문에 스택을 사용하지 않아도 재귀적으로 구현이 가능함. 시작 노드를 스택에 삽입하고, 방문 처리한다. 스택의 최상단 노드를 확인한다. 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺀다. 2, 3의 과정은 스택이 비어질때까지 반복된다. #include #include using namespace std; int n = 7; int checked[7]; vector arr[8]; void dfs(int x) ..
-
너비 우선 탐색(BFS)알고리즘/탐색 2021. 12. 25. 00:47
너비 우선 탐색(Breadth First Search): 특정 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘. 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함. (ex. 미로찾기) 선입선출의 특성을 가진 큐를 이용하는데 큐는 너비 우선 탐색을 가능하도록 해준다. 시작 노드를 큐에 삽입하면서 방문처리. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입. 2, 3번 과정을 반복하면 시작 노드에서 거리가 가까운 순서대로 출력이 될 것임. #include #include #include using namespace std; int n = 7; int checked[7]; vector arr[8]; void b..
-
스택 & 큐자료구조 2021. 12. 25. 00:42
Stack : 스택은 후입선출의 특성을 가지고 있는 자료구조로, 데이터 입력(푸쉬) 또는 제거(팝)할 때 항상 스택의 최상단(탑)에서만 이뤄진다는 특징이 있음. Ex) 스마트폰 뒤로가기 버튼, 쌓여있는 책 또는 상자, 시스템 스택(함수 호출 시) 스택의 추상 자료형 create() - 최대 크기를 size로 제한한 공백 스택 생성 is_Full() - 스택이 꽉 찼는지 확인 is_Empty() - 스택이 비어있는지 확인 push() - 스택에 요소 추가 pop() - 스택에 요소 제거 peek() - 스택의 최상단 요소 반환 스택의 구현 방식 중 전역변수로 구현하는 경우, 배열과 top 변수를 함수의 매개 변수로 전달할 필요가 없으나, 하나의 프로그램 안에서 여러 개의 스택을 동시에 사용하기가 어렵다. ..
-
계수 정렬알고리즘/정렬 2021. 12. 25. 00:32
계수 정렬: 범위 조건이 있는 경우에 한해 빠른 정렬 알고리즘 크기를 기준으로 개수를 세는 알고리즘이며, 모든 데이터에 한번씩만 접근하면 된다는 점에서 효율적이라 할 수 있음. 그러나, 데이터의 크기가 한정되어 있을 때에 한해서만 사용할 수 있음. 시간 복잡도: O(N) 앞에서 차례대로 데이터를 하나씩 읽어 주기만하면 되므로 N에 비례하는 시간 복잡도를 가진다. #include int main() { int temp; int count[5]; // 범위 기준 : 1~5 int arr[30] = { 1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1 }; for(int i = 0; i
-
힙 정렬알고리즘/정렬 2021. 12. 25. 00:27
heap : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리. 최대 힙 : 부모 노드가 자식 노드의 값보다 더 큰 힙 (최소 힙은 이와 반대) 힙 정렬(오름차순 기준)을 하기 위하여 힙 구조를 가지도록 만들어야 하며, 최대 힙이 아닌 경우 힙 생성 알고리즘을 통해 부모 노드와 부모 노드보다 더 큰 값을 가지는 자식노드를 바꿔주는 과정을 거친다. Heapify algorithm : 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘 처음에 최대 힙 구조를 만든다. 루트 노드와 마지막 원소를 바꿔준 후 집합의 크기를 감소시킨다. 가장 큰 값이 마지막 원소로 바뀌면서, 이 원소를 제외하고 다시 힙 구조를 형성하여 2, 3번의 과정이 반복되면 마지막에 힙 정렬이 ..
-
병합 정렬알고리즘/정렬 2021. 12. 25. 00:18
병합 정렬: 모든 원소들이 하나로 남을때까지 정확하게 절반으로 나눈 후 나중에 합쳐서 정렬하는 알고리즘. Ex) (이미 하나까지 전부 반으로 쪼게진 상태라 가정하고 2의 배수만큼 차례대로 합쳐진다.) 7 6 5 8 3 5 9 1 67 58 35 19 5678 1359 13556789 시간 복잡도: O(N*log N) 너비가 n이고 높이가 log n (정렬이 되어있는 상태에서 데이터를 하나씩 읽어나가 새롭게 정렬을 하므로 n * log n에 비례.) 병합 정렬의 경우 항상 정확히 절반으로 분할되고 정복하는 과정이 반복되므로 최악의 경우에도 O(N*log N)을 보장한다. (퀵 정렬은 편향되게 분할 할 가능성이 있으므로 최악의 경우 O(N^2)) 단점: 기존의 데이터를 담을 추가적인 배열 공간이 필요하여 메..