c 알고리즘 썸네일형 리스트형 너비우선탐색(BFS : Breadth First Search) 너비우선탐색(BFS : Breadth First Search) - 자노드를 탐색하기 전 같은 위치의 노드를 먼저 탐색하는 방식이다. - BFS의 시간 복잡도 및 공간 복잡도는 O(nⁿ)이다. ( 주어진 모든 노드를 저장하기 때문 ) - 무한히 깊은 트리에 효과적이다. [ Fig. 1] BFS 탐색 순서 1. 동작 원리 (1) 시작 노드를 큐(Queue)에 삽입한다. (2) 큐가 비어있다면 수행을 중단한다. (3) 큐에서 노드를 꺼낸다. (4) 꺼내온 노드를 기준으로 인접한 정점 중 탐색하지 않은 노드를 탐색한다. (5) 탐색한 노드를 순차적으로 큐에 삽입한다. (6) (2 - 5) 과정을 반복한다. 2. 함수 구현 #include #define MAX 6 #define VISITED 2 #define A.. 더보기 깊이우선탐색(DFS : Depth First Search) 깊이우선탐색(DFS : Depth First Search) - 해가 존재할 가능성이 있으면 계속해서 같은 방향으로 탐색하는 알고리즘이다. - 스택 구조( 재귀 )를 이용한다. - 진행 중이던 방향이 막혀 있을 경우 이전으로 되돌아가서 위의 과정을 반복한다. - 모든 곳을 방문했을 때 탐색을 종료한다. - 넓은 트리에 효과적이나 목표 노드가 없는 경로에 깊이 빠질 수 있는 단점이 있다. [ Fig. 1 ] DFS 탐색 순서 1. 동작 원리 (1) 현재(초기) 노드를 방문으로 표시한다. (2) 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있는지 탐색한다. (3) (2)의 조건에 맞는 노드를 탐색하면, 해당 노드를 중심으로 (1 - 2) 과정(재귀)을 반복한다. (4) 방문하지 않은 노드가 없을 경우 종.. 더보기 그래프의 행렬 표현법(Representations of graphs) 그래프의 행렬 표현법(Representations of graphs) 1. 방향성이 없는 그래프와 방향성이 있는 그래프 (1) 방향성이 없는 그래프 [ 출저 : Introduction to algorithms 3/E ] 위의 그림을 보면 (a)의 그래프는 5개의 꼭지점과 7개의 선을 가지고 있다. (a)의 그래프를 인접 리스트로 표현해놓은 것이 (b)의 그림이다. 꼭지점 1의 경우 2와 5에 인접해 있고, 꼭지점 2의 경우 모든 다른 꼭지점과 인접해 있다. 이것을 행렬로 표현하면 (c)와 같다. 행은 현재 꼭지점이 되는 것이고, 열은 다른 꼭지점이라고 생각하면 된다. 즉 위의 그림과 무관하게 아래 행렬을 살펴보자. 1 2 3 4 5 1 0 0 1 0 0 2 0 0 1 1 0 3 1 1 0 0 0 4 0 .. 더보기 병합 정렬(Merge Sort) 병합 정렬(Merge-Sort) - 배열의 원소를 완전 분해한 후에 다시 병합하며 정렬하는 방식 - 항상 O(n log n)의 복잡도를 가진다 1. 동작 원리 (1) 주어진 배열을 2개의 파티션으로 나눈다. (2) 하나의 원소가 남을 때까지 (1)의 과정을 재귀적으로 반복한다. (3) 완전 분해한 원소를 다시 병합하며 정렬을 수행한다. 2. 함수 설명 - merge_sort() : 동작원리 (1)과 (2)에 해당하는 기능을 수행한다. - merge() : 동작원리 (3)에 해당하는 기능을 수행한다. #include #include #include #include #define MAX 10 // size of array #define INF 10000 // infinity value void display.. 더보기 힙 정렬(Heap Sort) 힙 정렬(Heap-Sort) - 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬하는 방식 - 일반적으로 O( n log n)의 복잡도를 가진다. ( 퀵 정렬은 최악의 경우 O(n²)의 복잡도를 가지기 때문에 힙 정렬이 선호된다.) 동작 원리 1. 최대(최소) 힙을 구성한다. 자노드를 가진 부노드부터 구성하며, 아래부터 루트까지 순차적으로 구성한다. 2. 루트에 위치한 수와 가장 작은 수를 교환한다. 3. 교환한 수를 제외하고 힙의 특성을 유지시킨다. 4. 위의 2와 3 과정을 반복한다. 함수 설명 - heap_sort() : 동작 원리 "2"의 과정을 수행하는 함수 - build_max_heap() : 동작 원리 "1"의 과정을 수행하는 함수로 기본적인 힙의 구조를 구성한다. - max_heapify().. 더보기 퀵 정렬(Quick Sort) 1. 퀵 정렬(Quick-Sort) - 퀵 정렬의 내부 루프는 대부분 컴퓨터의 아키텍처에서 효율적으로 작동하도록 설계되어 있다. ( 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높기 때문 ) - 일반적으로 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행한다. ( 최악의 경우 O(n²) ) - 정렬을 위해 작은 공간( O(log n) )의 메모리를 필요로 한다. 2. 동작 원리 1. 리스트의 중간 원소를 피벗으로 지정한다. 2. 피벗을 기준으로, 앞에는 피벗보다 값이 작은 원소들을 배치하고 뒤에는 피벗보다 값이 큰 원소들을 배치한다. ( 이렇게 리스트를 나누는 것을 "분할(partition)"이라고 한다. ) 3. 분할된 두 개의 리스트에 대해 재귀적으로 이 과정을 반복한다. #i.. 더보기 이전 1 다음
