최단경로 - 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로 Dijkstra 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 Floyd 모든 정점 ~ 다른 모든 정점까지의 최단 경로 Dijkstra Algorithm - 탐욕적 방법 (greedy method) 이용 - 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산 - 가중치가 음수가 아닐 때 정상적으로 작동 - Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택 - 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요 - O(n²) 시작 정점(v) 선택 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없..

Prim MST Algorithm - 시작 정점에서부터 신장 트리 집합을 확장해가는 알고리즘 - 인접 정점들 중에서 가중치가 최소인 정점을 선택해가면서 트리를 확장 이전 단계에서 만들어진 신장 트리를 확장 - n개의 정점에 대해서 n-1개의 간선을 선택하면 알고리즘 종료 - 배열로 구현 or 최소히프로 구현 - 어떤 정점에서 시작하던간에 똑같은 트리 생성 - O(n²) ※ 각 정점으로부터 거리 distance 배열, 선택된 정점 selected 배열 (모든 정점 distance = INF로 초기화) v의 인접 정점들 distance 업데이트 인접 정점들 중 distance가 가장 낮은 정점(w) 선택 v와 w를 하나의 그룹으로 간주하고 해당 그룹으로부터 distance 다시 업데이트 n-1개 간선 선택할..

신장 트리 (Spanning Tree) - 그래프의 모든 정점들을 포함하는 트리 - 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다 최소 신장 트리 (Minimum Spanning Tree) - 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리 - 모든 정점들을 가장 적은 수의 간선, 비용으로 연결 - n개의 정점들에 대해 반드시 n-1개의 간선만 사용 + 사이클 포함 X ex) 도로 건설, 전기 회로, 통신, 배관,.... Kruskal Algorithm, Prim Algorithm Kruskal MST Algorithm - 탐욕적 방법 (greedy method) 이용 - 간선을 기반으로 하는 알고리즘 - 간선의 개수 e개 → O(|e|log₂|e|) - 매 선택마다 최선의..

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) 간선에 비용/가..

[11장 1번] 아래 그림과 같이 2개의 체크박스와 버튼을 하나 만들어라. "버튼 비활성화" 박스를 선택하면 버튼이 작동하지 못하게 하고, 해제하면 다시 작동하게 하라. "버튼 감추기" 체크박스를 선택하면 버튼이 보이지 않도록 하고 해제하면 버튼이 보이도록 하라. package Java11_1; import javax.swing.*; import java.awt.*; import java.awt.event.ItemEvent; import java.awt.event.ItemListener; public class Java11_1 extends JFrame{ Java11_1(){ super("CheckBox Practice Frame"); setDefaultCloseOperation(JFrame.EXIT_O..