BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 리스트(BFS - 스택 / DFS - 큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; // 그래프 구현 typedef struct graphnode { int vertex; struct graphnode* link; }graphnode; typedef struct graph { int n; graphnode* list[MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_vis..

BFS(stack) VS DFS(queue) BFS : 깊이 우선 탐색 - stack or 순환으로 구현 DFS : 너비 우선 탐색 - queue로 구현 #include #include // 인접 행렬 (BFS-스택 / DFS-큐) #define MAX_VERTEX 50 #define TRUE 1 #define FALSE 0 typedef int element; typedef struct graph { int n; // 정점 개수 int vertex[MAX_VERTEX]; // 정점 저장 배열 int matrix[MAX_VERTEX][MAX_VERTEX]; }graph; int visited[MAX_VERTEX]; void init_visited(int arr[]) { for (int i = 0; i <..

BFS - 너비 우선 탐색 - 원형큐로 구현 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 시작 정점으로부터 거리가 d인 정점들을 모두 방문 (d=1) 그 다음에 거리가 d+1인 정점들을 모두 방문 d+2 / d+3,.... 정점들을 차례대로 방문 거리가 0인 시작 정점(v)을 방문 v로부터 거리가 1인 정점 모두 방문 v로부터 거리가 2인 정점 모두 방문 마지막 정점 방문할 때 까지.,.... 인접 행렬로 구현한 BFS Queue : bfs_mat_queue(graph* g, int v) 큐 생성 v 방문완료 표시 v를 큐에 enqueue 큐에서 dequeue (정점 v dequeue) -- (1) dequeue된 정점 v의 인접 정점(w)들을 방..

DFS - 깊이 우선 탐색 - 인접 행렬(순환/stack), 인접 리스트로 구현 - 어떤 노드를 방문했는지 검사를 무조건 해줘야 한다 (검사를 안해주면 무한 루프에 빠진다) 검사를 위한 배열 int visited[MAX_VERTEX] → dfs 시작할 때, 전부 FALSE로 초기화 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 인접 행렬로 구현한 DFS 1. 순환 : dfs_mat_recur(graph* g, int v) 정점 v에서부터 dfs 시작 v는 방문완료니까 visited배열에 TRUE 표시 v의 인접 정점 w에서 탐색 시작 -- (1) matrix[v][w] == 1 (인접)이고, visited[w] == FALSE (방문 X)이면, 정점..

그래프 탐색 방법 DFS (Depth First Search) : 깊이 우선 탐색 BFS (Breath First Search) : 너비 우선 탐색 DFS ≒ 전위/중위/후위 순회 BFS ≒ 레벨 순회 DFS (Depth First Search) - 깊이 우선 탐색 - 한 방향으로 끝까지 진행 - 더 이상 갈 곳이 없으면, 가장 가까운 곳으로 다시 되돌아가서(backtracking) 해당 지점에서부터 다시 탐색을 시작 ▶ 구현 방법 1. 인접 행렬 2. 인접 리스트 순환 호출 사용 stack 사용 : 인접 정점들을 stack에 저장했다가 꺼내서 다시 탐색 BFS (Breath First Search) - 너비 우선 탐색 - 현재 정점으로부터 가장 가까운 노드를 먼저 방문 - 멀리 떨어져 있는 정점은 나중..

그래프의 표현방법 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 연결 리스트를 사용 인접 리스트 - 각 연결 리스트들의 노드는 인접 정점들을 저장 - 각 연결 리스트들은 헤더 노드를 보유 → 헤더 노드는 배열로 구성 → 배열의 인덱스를 이용해서 각 정점의 연결 리스트에 접근 그래프 인접리스트 구현 #define MAX_VERTEX 50 typedef struct graphnode { int vertex; // 각 노드의 정점 struct graphnode* link; // 정점들간에 연결해주는 link }graphnode; typedef struct graph { int n; // 정점의 개수 graphnode* list[MAX_VERTEX..

그래프의 표현방법 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용 인접 리스트(Adjacency List) : 연결 리스트를 사용 인접 행렬 - 정점의 수 n개에 대해 n×n의 2차원 배열로 구성 - 간선 (i, j)가 그래프에 존재하면 m[i][j] = 1 - 간선 (i, j)가 그래프에 없으면 m[i][j] = 0 - n개의 정점이 존재하면 n²개의 메모리가 필요 → 메모리 낭비가 크다 - 간선이 매우 많은 밀집 그래프에는 적합하다 - 간선이 적은 희소 그래프의 경우에는 메모리 낭비가 크므로 적합하지 않다 무방향 그래프 = 행렬이 대칭으로 구성 그래프 인접행렬 구현 #define MAX_VERTEX 50 typedef struct graph { int n; // 정점의 개수 coun..

그래프 (Graph) G = (V, E) - 정점(Vertex), 간선(Edge)들의 집합으로 구성 - 정점, 간선 모두 데이터 저장 가능 Vertex : V(G) = { 1, 2, 3, 4, 5 } Edge : E(G) = { (1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5) } 그래프의 종류 ▶ 무방향 그래프 (Undirected Graph) 간선을 통해서 양방향으로 갈 수 있다 (A, B), (B, A)는 동일한 간선 ▶ 방향 그래프 (Directed Graph) 일방통행처럼 간선을 통해서 단방향으로만 갈 수 있다 (A, B), (B, A)는 서로 다른 간선 ▶ 가중치 그래프 (Weighted Graph) / 네트워크 (Network) 간선에 비용/가..

머신 스케줄링 - 동일한 기계 m개, 처리해야 하는 작업 n개가 존재 모든 기계를 가동해서 가장 최소의 시간 안에 작업을 모두 끝내는 것 = 머신 스케줄링 - 각 작업마다 완료까지 걸리는 시간이 다름 종료 시간이 최소인 기계를 선택 해당 기계에 작업시간이 최대인 작업을 할당한다 ▶ LPT 알고리즘 - ex) 여러 서버에 작업을 분배 할 경우, 가장 효율이 좋은 최적의 해(근사의 해)를 찾는 알고리즘 - 항상 종료시간이 최소인 기계를 선택 → 최소 히프를 통해서 구현 ----------------------------------------------------------------------------------------------------------- 기계들을 최소 히프에 전부 insert 최소 히프..

히프 정렬 (최대 히프) - n개의 요소를 O(nlog₂n)시간 안에 정렬 - 정렬되지 않은 배열 element a[]에 대하여 배열 a의 data들을 최대 히프에 차례대로 추가 최대 히프에서 data들을 하나씩 꺼내서 배열 a의 맨 뒤쪽부터 저장 배열 a에 대한 히프 정렬 완료 void heap_sort(element arr[], int len) { heapnode* h; h = create(); init_heap(h); for (int i = 0; i = 0; i--) { arr[i] = delete_node(h); } free(h); // 히프 동적 할당 해제 } Full Code..

우선순위 큐 (priority queue) - 일반적인 큐 : FIFO(First In First Out)구조 - 우선순위 큐 : 우선순위가 높은 데이터가 먼저 나간다 시뮬레이션 시스템, 네트워크 트래픽 제어, 작업 스케쥴링, 수치해석계산 등에 사용 자료구조 삭제되는 요소 Stack 가장 늦게 들어온 데이터 (LIFO) Queue 가장 먼저 들어온 데이터 (FIFO) Priority Queue 가장 우선순위가 높은 데이터 (Priority) 구현 방법 - 배열 / 연결리스트 / 히프 표현 방법 삽입 삭제 정렬 안된 배열/연결 리스트 O(1) O(n) 정렬 된 배열/연결 리스트 O(n) O(1) 힙 O(log n) O(log n) - 만약 n이 1000일 경우 O(n) : 1000초 / O(log₂n) :..

이진 탐색 트리 - root 기준으로 왼쪽 → root보다 작은 값 - root 기준으로 오른쪽 → root보다 큰 값 - 중위 순회 → 오름차순으로 정렬된 값 반환 1. 탐색 연산 node == NULL || key == node->key → 해당 node 리턴 key key → node = node->llink를 통해서 왼쪽 서브트리 탐색 key > node->key → node = node->rlink를 통해서 오른쪽 서브트리 탐색 - 순환 탐색 vs 반복 탐색 → 효율성 : 반복 treenode* search_recur(treenode* node, element data) { // 순환 탐색 함수 if (node == NULL || node->data == data) return n..