오늘도 삽질

노트정리/알고리즘

최단경로 - 다익스트라 , 플로이드 알고리즘

최단 경로는 어떤 정점 A에서 정점 Z까지의 최단 경로란 A에서 Z까지의 경로 중 간선의 가중치의 합이 가장 작은 경로 입니다. 단일 출발점 최단 경로- 단일 시작점에서 최단 경로 구하기 문제는 임의의 시작점을 1개 정하고 다른 노드들 사이의 최단 경로를 구하는데 사용.- 노드 사이의 거리가 모두 양수인 경우, 가장 널리 사용하는 것 다익스트라 알고리즘 다익스트라 알고리즘- 한 출발점에서 다른 모든 정점으로 최단 경로를 구하는 문제로 가중치를 갖는 간선은 없음. 모든 쌍 최단 경로- 모든 정점쌍 간의 최단 경로를 구하는 방법, 경로의 길이가 음인 사이클이 그래프에 존재하지 않을 것을 가정, 단일 출발점으로하여서 반복적으로 적용해 구할 수 있음.O(|V|s)- 경로의 길이가 음인 사이클이 그래프에 존재 X..

노트정리/알고리즘

최소 신장나무 - 크루스칼 , 프림 알고리즘

최소 신장 나무- 그래프 G의 모든 정점들을 사이클이 생기지 않게 연결하면서 간선에 부여된 가중치의 합이 가장 적게 구성된 나무.- 만드는 방법에는 크루스칼 , 프림 알고리즘이 있다. 신장 나무가중 무방향 그래프에 대하여 신장 나무는 주어진 그래프의 모든 노드들을 포함하는 연결된 부분 그래프로 나무를 형성.신장 나무 중에서 가중치의 합이 가장 작은 신장 나무로 최소 신장 나무도 있음. 크루스칼 알고리즘- 욕심쟁이 방법 적용. 사이클을 만들지 않는 최단 간선을 하나씩 추가해 나감으로 최소 신장 나무를 구하는 방법- 간선을 가중치가 증가하는 순으로 한 번에 하나씩 사이클이 만들어 지지 않도록 추가함.123456789101112Kruskal (Adj(G), T){ /* 입력 : 그래프 g=(v,e)의 인접 리..

노트정리/자료구조

[그래프 알고리즘] 깊이 우선 탐색(DFS) 와 너비 우선 탐색(BFS)

깊이 우선 탐색- 무방향 그래프에서 어떤 정점에 대하여 검색이 끝나면 인접한 정점 중 검색하지 않은 정점을 찾아가 다시 검색하는 방법.무방향 그래프 G(V,E)를 구성하는 V(G)에 속하는 모든 정점들을 방문하는 방법을 그래프의 운행이라 하고, 스택을 이용하는깊이 우선 검색(DFS)과 큐를 이용하는 너비 우선 검색(BFS) 방법이 있다.탐색 과정- DFS는 정점의 방문 시 최근의 주변 정점을 먼저 방문함.- 시간 복잡도 O(| V |^2) DFS 너비 우선 탐색- 무방향성 그래프에서 어떤 정점을 검색하고 그 정점에 인접한 모든 정점들을 검색한 후 이정점에 인접한 모든 정점들을 검색하는 방법으로 큐를 이용.탐색 과정- 무방향 그래프G(V,E)에서 시작하며 정점 V를 방문한 후 V에 인접한 아직 방문하지 않..

노트정리/알고리즘

그래프의 종류와 인접, 행렬 리스트

그래프그래프 G = (V,E) 이다. V : 정점의 집합을 의미하고 E : 간선의 집합을 의미한다. 2차원 배열을 이용하여 인접 행렬이나 연결 리스트 형태의 인접 리스트로 표현이 가능하다. 여러 가지 종류로 나뉘기도 하는데크게 무방향 그래프 , 방향 그래프로 나뉜다. 변이 방향성을 띠지 않는 그래프를 무뱡향 , 방향성을 띠는 그래프를 방향 그래프라고 함.방향 그래프는 보통 그림 보면 화살표 있음. 그래프의 종류인접 - 간선 v,w 가 e(g)에 속한 간선 > 점점 v와 정점 w는 인접부속 - v,w가 인접해 있을 떄, 간선v, w : 정점,v, w에 부속된 것단순 경로 - 경로상에 있는 정점들 중에서 첫 번째 정점과 마지막 정점을 제외한 모든 정점들이 서로 다를때사이클 - 첫 번째 정점과 마지막 정점이 ..