본문 바로가기

컴퓨터/파이썬 공부정리

[Python] 다익스트라(Dijkstra) 알고리즘 구현 INF = 9999 def choose_vertex(dist, found): min = INF minpos = -1 for i in range(len(dist)): if dist[i] < min and found[i] == False: min = dist[i] minpos = i return minpos def shortest_path_dijkstra(vtx, adj, start): vsize = len(vtx) # 정점 수 dist = list(adj[start]) # 시작정점으로부터 최단 경로 거리를 저장 path = [start] * vsize # 바로 이전 정점을 저장. 이전 정점을 따라 시작 정점까지 가는 경로가 최단 경로 found = [False] * vsize # 방문한 정점 표시를 위해 .. 컴퓨터/파이썬 공부정리 2021. 5. 31.
[Python] Prim 알고리즘 구현 INF = 9999 # 가장 큰 가중치(무한대) # 현재 트리에 인접한 정점들 중에서 가장 가까운 정점을 찾는 함수 def getMinVertex(dist, selected): minv = 0 mindist = INF for v in range(len(dist)): if not selected[v] and dist[v] < mindist: mindist = dist[v] minv = v return minv # Prim의 최소 비용 신장 트리 프로그램 def MSTPrim(vertex, adj): vsize = len(vertex) dist = [INF] * vsize selected = [False] * vsize dist[0] = 0 for i in range(vsize): u = getMinVert.. 컴퓨터/파이썬 공부정리 2021. 5. 31.
[Python] Kruskcal 알고리즘 구현 parent = [] # 각 노드의 부모노드 인덱스 set_size = 0 # 전체 집합 개수 def init_set(nSets): global set_size, parent set_size = nSets # 집합의 개수 for i in range(nSets): # 모든 집합에 대해 parent.append(-1) # 각각이 고유의 집합(부모가 -1) def find(id): while (parent[id] >= 0): id = parent[id] return id def union(s1, s2): global set_size parent[s1] = s2 # s1을 s2에 병합시킴 set_size -= 1 # 초기에는 모든 정점이 각각 고유한 집합이다. # 최소 가중치 간선 (u, v)가 선택되면 u와 .. 컴퓨터/파이썬 공부정리 2021. 5. 31.
[Python] 위상 정렬(topological sort) 구현 def topological_sort_AM(vertex, graph): n = len(graph) inDeg = [0] * n # 정점의 진입차수 저장 for i in range(n): for j in range(n): if graph[i][j] > 0: inDeg[i] += 1 vlist = [] # 진입 차수가 0인 정점 리스트틀 만듬 for i in range(n): if inDeg[i] == 0: vlist.append(i) while len(vlist) > 0: v = vlist.pop() print(vertex[v], end=' ') for u in range(n): if v != u and graph[v][u]: inDeg[u] -= 1 # 연결된 정점의 진입 차수 감소 if inDeg[u].. 컴퓨터/파이썬 공부정리 2021. 5. 31.
[Python] avl 트리 구현 class BSTNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None def search_bst(n, key): if n is None: return None elif n.key == key: return n elif n.key < key: return search_bst(n.right, key) else: return search_bst(n.left, key) def search_bst_iter(n, key): while n is not None: if n.key == key: return n elif key < n.key: n = n.left else: n = n... 컴퓨터/파이썬 공부정리 2021. 5. 12.
[Python] 이진 트리 map 구현 class BSTMap: def __init__(self): self.root = None def isEmpty(self): return self.root == None def clear(self): self.root = None def size(self): def count_node(): node = self.root if node is None: return 0 stack = [] stack.append(node) cnt = 0 while stack: cnt += 1 if node.left is not None: stack.append(node.left) if node.right is not None: stack.append(node.right) return cnt return count_node().. 컴퓨터/파이썬 공부정리 2021. 5. 12.
[Python] 이진 트리 구현 from collections import deque class BSTNode: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None def search_bst(n, key): if n is None: return None elif n.key == key: return n elif n.key < key: return search_bst(n.right, key) else: return search_bst(n.left, key) def search_bst_iter(n, key): while n is not None: if n.key == key: return n elif key < .. 컴퓨터/파이썬 공부정리 2021. 5. 12.
[Python] flatten 구현 - non-iterative, recursive function import time def flat(lst): i=0 while i 10: break i += 1 print('\nResult :', sum) print(f'time : {(time.time()-start) * 1000}') while을 통하여 리스트를 하나씩 불러와서 검사합니다. 다만 검사 방법에서 slicing assignment을 이용합니다. list[1:2] 와 list[1]은 같은 인덱스 1에 대한 것이지만 그 결과값은 다릅니다. 예를 들어, list = [1,2,3]에 대하여 list[1:2] = [1]를 의미하지만, list[1] = 1로, slicing assignment를 통해 나타나는 결과는 리스트인 반면, 인덱스로 접근하면 값을 보여줍니다. 따라서 slicing assignment로.. 컴퓨터/파이썬 공부정리 2020. 11. 10.

티스토리툴바