Programming 기초/Python
-
[Python 자료구조 #가중치 그래프3] 최단 경로 알고리즘 - Dijkstra, FloydProgramming 기초/Python 2023. 5. 30. 23:09
* 최단 경로(shortest path) 최단 경로 문제는 가중치 그래프에서 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 간선의 가중치를 시간으로 하면 "최단시간 경로", 거리로 하면 "최단거리 경로"가 된다. 인접 행렬에서 두 정점 사이의 간선이 없으면 None이 아니라 무한대 값(INF)을 저장한다. 간선의 가중치는 반드시 양수이다. * Dijkstra의 최단 경로 알고리즘 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 만약 그래프의 모든 정점들 사이의 최단 경로를 구하려고 한다면 Dijkstra 알고리즘을 정점의 수만큼 반복하여 실행하면 된다. 하나의 정점에서 출발하여 모든 정점까지의 최단 경로를 찾는데 O(n^2)..
-
[Python 자료구조 #가중치 그래프2] 최소비용 신장 트리 - Kruskal의 MST 알고리즘, Prim의 MST 알고리즘Programming 기초/Python 2023. 5. 29. 18:12
* 최소비용 신장 트리(MST: minimum spanning tree) 통신망 도로망 유통망 등은 대개 길이, 구축비용, 전송 시간 등의 가중치를 간선에 할당한 가중치 그래프로 표현할 수 있다. 이러한 망을 가장 적은 비용으로 구축하는 문제를 생각해 보자. 조건은 다음과 같다. 그래프의 모든 정점들은 연결되어야 한다. 연결에 필요한 간선의 가중치 합(비용)이 최소가 되어야 한다. 사이클은 두 정점을 연결하는 두 가지 경로를 제공하므로 비용 측면에서 바람직하지 않다. 따라서 사이클이 없이 (n-1)개의 간선만을 사용해야 한다. → 결과적으로 '신장 트리' 최소비용 신장 트리는 그래프의 여러 가능한 신장 트리들 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소비용 신장 트리를 구하는 방..
-
[Python 자료구조 #가중치 그래프1] 인접행렬/인접리스트를 이용한 가중치 그래프 표현Programming 기초/Python 2023. 5. 27. 23:28
* 가중치 그래프(weighted graph) 간선에 비용이나 가중치가 할당된 그래프. 수학적으로 G = (V, E, w)와 같이 표현된다. V(G)는 그래프 G의 정점들의 집합 E(G)는 그래프 G의 간선들의 집합 w(e)는 간선 e의 강도(weight)로 비용(cost) 또는 길이(length)라고도 부른다. 어떤 가중치 그래프의 경로를 p = (v_0, v_1, ..., V_k)라고 한다면, 경로의 길이(또는 강도) w(p)는 다음과 같이 경로상의 모든 간선의 길이 합으로 표현된다. * 인접 행렬을 이용한 가중치 그래프 표현 ▶ 간선이 없느 것을 표기하는 방법 1. 무한대(INF) 2. None ▶ 인접 행렬에서의 가중치의 합 계산 # 인접 행렬에서의 가중치의 합 계산 # def weightSum(..
-
[Python 자료구조 #그래프3] 신장 트리Programming 기초/Python 2023. 5. 27. 20:13
* 신장 트리(spanning tree) 그래프내의 모든 정점을 포함하는 트리이다. 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 하고, 그래프의 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다. 하나의 같은 그래프에 다양한 신장 트리가 가능하다. 신장 트리는 깊이우선이나 너비우선 탐색 도중에 사용된 간선들만 모으면 된다. # 너비우선탐색 함수 bfs를 수정한 코드 # 탐색 도중에 추가되는 간선을 순서대로 출력한 코드 import collections def bfsST(graph, start): visited = set([start])# 맨 처음에는 start만 방문한 정점임 queue = collections.deque([start])# 파이썬 컬렉션의 덱 생성(큐로 사용) ..
-
[Python 자료구조 #그래프2] 그래프의 탐색(DFS, BFS), 연결 성분 검사Programming 기초/Python 2023. 5. 27. 14:15
* 그래프의 탐색 - 깊이 우선 탐색 깊이 우선 탐색(Depth First Search, DFS)은 스택을 이용한 미로 탐색과 유사하다.(이전 포스팅 참고) 탐색 과정에 이미 방문한 정점을 관리하는 집(또는 리스트)가 필요한데, 이를 visited라 하면 맨 처음에는 visited가 공집합이어야 한다. 가장 최근에 만났던 갈림길로 되돌아가야 하므로 스택을 사용하여 구현할 수 있지만, 순환의 형태로 구현하는 것이 더 직관적이다. 그래프가 인접리스트로 표현되어 있으면 O(n + e) 이고(n은 노드 수 e는 간선 수), 인접 행렬로 표시되어 있다면 O(n^2)이다. # 인접 리스트 방식으로 표현된 그래프를 활용한 dfs. 인접행렬을 이용하면 달라짐 # 매개 변수로 그래프, 시작 정점, 그리고 visited를..
-
[Python 자료구조 #탐색트리3] AVL트리, AVL트리를 이용한 맵Programming 기초/Python 2023. 5. 26. 19:36
* 심화 학습 : 균형이진탐색트리 - AVL 트리 AVL 트리는 Adelson-Velskii와 Landis에 의해 제안된 트리이다. AVL트리는 항상 균형 트리를 보장하기 때문에 탐색과 삽입, 삭제 연산에서 항상 O(log_2 n)의 처리시간을 보장한다. AVL 트리를 정의하기 위해서는 균형인수를 정의해야 한다. 어떤 노드의 균형 인수(balance factor)는 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차로 정의된다. AVL 트리는 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리 정의 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색 트리이다. 즉 모든 노드의 균형 인수는 0이나 ±1이 되어야 한다. * AVL 트리..
-
[Python 자료구조 #탐색트리2] 이진탐색트리를 이용한 맵Programming 기초/Python 2023. 5. 26. 18:05
* 이진탐색트리를 이용한 맵 ↓BSTNode(), inorder(), count_node(),search_bst()함수 코드참고.(이전 블로그 글 참고) 더보기 class BSTNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None def inorder(n): # 중위 순회 함수 if n is not None: inorder(n.left) # 왼쪽 서브트리 처리 print(n.key, end=" ") # 루트노드 처리(화면 출력) inorder(n.right) def count_node(n): if n is None: return 0 else: return 1 + cou..
-
[Python 자료구조 #탐색트리1] 이진탐색트리(BST)Programming 기초/Python 2023. 5. 26. 15:53
* 이진탐색트리(BST, Binary Search Tree) 효율적인 탐색을 위한 이진트리 기반의 자료구조이다.(이진탐색트리는 이진트리의 한 종류이다.) 트리의 연산들을 보다 단순하게 설계하기 위해 이진탐색트리에서는 보통 중복을 허용하지 않는다. 그렇지만, 필요하다면 중복된 키를 허용할 수도 있다. 이진탐색트리의 모든 노드들을 중위 순회로 방문하면 오름차순으로 노드를 방문하게 된다. 따라서 어느 정도 정렬된 상태를 유지하고 있다고 볼 수 있다. 이진탐색트리는 탐색을 위한 자료구조이므로 노드의 데이터는 하나의 엔트리, (탐색키, 키에 대한 값)의 형태가 되어야 한다. ● 모든 노드는 유일한 키를 갖는다. ● 왼쪽 서브트리의 키들은 루트의 키보다 작다. ● 오른쪽 서브트리의 키들은 ..