::public/알고리즘10 DFS(깊이 우선 탐색) & BFS(너비 우선 탐색) DFS와 BFS는 모두 *그래프를 탐색할 때 사용한다. *그래프:정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조 하나의 정점에서 시작하여 차례대로 모든 노드들을 순회(방문)하면서 탐색하는 탐색 알고리즘이다. DFS(깊이 우선 탐색) ; 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 모두 순환하여 탐색하는 방법. 모든 노드를 방문하고자 하는 경우나 이전 경로의 정보가 필요한 경우에 사용한다. 최대한 깊이 내려간 뒤에 더 이상 깊이 갈 곳이 없으면 옆으로 이동한다. 스택(stack) 또는 재귀함수로 구현한다. DFS 구현(재귀) 1. 노드를 방문 리스트에 기록 2. 현재 노드에 인접한 노드를 기준으로 반복 3. 노드의 인접 리스트가 비었을 경우 .. 2023. 8. 17. 탐색 *순차 탐색 // 정렬되지 않은 배열 arr의 순차탐색 int sequentialSearch(int arr[], int key, int low, int high) { for (int i = low; i 2019. 9. 6. 기수 정렬(Radix Sort) 버킷 정렬(bucket sort)라고도 함. 먼저 들어간 숫자들이 먼저 나와야함.(queue) 숫자의 자릿수 값을 비교하는 정렬. LSD(least significant digit) ;가장 낮은 자릿수부터 MSD(most significant digit) ;가장 높은 자릿수부터 시간복잡도 k개의 자릿수를 가지기에 O(kn) 이지만 일반적으로 O(n) 로 표현. #include #define BUCKETS 10 // 10진수 #define DIGITS 4 // 4자릿수 테스트 void radizSort(int arr[], int n) { queue que[BUCKETS]; int factor = 1; for (int d = 0; d 2019. 9. 6. BinaryTree 구현. -트리의 용어 루트 노드(root node): 부모가 없는 노드. 트리는 단 하나의 루트 노드를 가짐. 서브 트리(sub tree): 루트 노드를 제외한 나머지 노드들. 링크(link): 루트 노드와 서브트리를 연결하는 선. 간선/에지(edge)라 부름. 형제(sibling): 같은 부모 노드를 가지는 노드. 단말 노드(leaf node): 자식 노드가 없는 노드. 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수. 노드의 깊이(depth): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 링크(간선)의 수. 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합. (루트 = 1레벨) 노드의 차수(degree): 노드가 지닌 가지(간선)의 수. 트리의 차수(degree of .. 2019. 8. 23. 퀵 정렬(Quick Sort) 퀵정렬 과정 a. 피봇 값을 하나 선택한다 b. 피봇 값을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 오도록 Swap 한다 (low(left), high(Right) 가 서로 만날때까지 반복함) c. 피봇 값을 기준으로 분할된 두영역을 다시 분할 정복으로 a. ~ c. 과정을 반복한다 시간복잡도 평균: O(n log2 n) 최악: O(n^2) 이미 정렬되어있는 경우 int partition(int arr[], int left, int right) { // low는 왼쪽에서 오른쪽으로 pivot보다 큰값이면 스탑 // high는 오른쪽에서 왼쪽으로 pivot보다 작은값이면 스탑 int pivot = arr[left]; // 기준 값 int low = left + 1; // 좌측 > 우측 탐색 int .. 2019. 7. 11. 알고리즘 시간 복잡도 - O(1) : 상수형 // 단순 계산(a+b와 같은 연산, 배열에 접근하는 연산) - O(log n) : 로그형 // n 개를 절반으로 계속해서 나눔 - O(n log n) : 선형 - O(n) : 선형로그형 // 1중 for 문 - O(n^2) : 2차형 // 2중 for 문 - O(n^3) : 3차형 // 3중 for 문 - O(2^n) : 지수형 // 크기가 n인 집합의 부분 집합 - O(n!) : 팩토리얼형 // 크기가 n인 수열 *시간 비교 O(1) 2019. 6. 26. 이전 1 2 다음
