[Munsik] MUNSIK BLOG [Munsik]

n, m = 5, 14inf = float("inf")dist = [[], [inf, 0, 2, 3, 1, 10], [inf, inf, 0, inf, 2, inf], [inf, 8, inf, 0, 1, 1], [inf, inf, inf, inf, 0, 3], [inf, 7, 4, inf, inf, 0] ]for k in range(1, n+1): for i in range(1, n+1): for j in range(1, n+1): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j]..

Prim 알고리즘import heapqn = 3adj = [[], [(1,2), (3,3)], [(1,1), (2,3)], [(2, 2), (3,1)] ]# Prim 알고리즘visited = [False] * (n+1)queue = list()queue.append((0, 1))answer = 0while queue: cost, node = heapq.heappop(queue) if visited[node]: continue visited[node] = True answer += cost for next_cost, next_node in adj[node]: if not visited[next_node]: ..

def DFS(v): visited[v] = True print(v, end = " ") for node in adj[v]: if not visited[node]: DFS(node)n = 5adj = [[], [2,3], [1,4,5], [1,4], [2,3], [2] ]visited = [False] * (n+1)print("DFS 탐색 순서 : ", end = "")DFS(1)from collections import dequedef BFS(s): visited[s] = True queue = deque() queue.append(s) while queue: ..

위와 같은 그래프를 노드 1부터 시작해서 최단 거리를 구하는 다익스트라 알고리즘을 구현하면 다음과 같다.import heapqdef dijkstra(arr, start): D = [float("inf")] * (n+1) D[start] = 0 queue = [(0, start)] while queue: # D값이 가장 작은 노드를 고른다 now_dist, now_node = heapq.heappop(queue) if now_dist > D[now_node]: continue # 현재 선택한 노드와 인접한 노드들을 읽는다 for node, weight in arr[now_node]: ..

다음은 위와 같은 구조의 이진 트리를 생성하고, 전위/중위/후위 순회를 수행하는 코드이다.class Node: def __init__(self, key): self.key = key self.left = None self.right = Noneclass BinaryTree: def __init__(self): self.root = None def insert(self, key): if self.root is None: self.root = Node(key) return queue = [self.root] while queue: temp ..

개요이진 탐색 트리(Binary Search Tree, BST)는 모든 노드가 다음 조건을 만족해야 한다.왼쪽 서브트리 노드의 key값은 자신의 노드 key값보다 작아야 한다.오른쪽 서브트리 노드의 key값은 자신의 노드 key값보다 커야 한다. 위의 BST를 중위 순회로 스캔하면 다음과 같이 노드의 key값을 오름차순으로 얻을 수 있다.1 → 4 → 5 → 6 → 7 → 9 → 11 → 12 → 13 → 14 → 15 → 18BST의 특징구조가 단순하다.중위 순회의 DFS를 통해 노드값을 오름차순으로 얻을 수 있다.이진 탐색과 비슷한 방식으로 매우 빠른 검색이 가능하다.노드를 삽입하기가 쉽다.코드 구현코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.class..

코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.# 1. 퀵 정렬def qsort(arr, left, right): pl = left pr = right pivot = arr[(left+right)//2] while pl pivot: pr -= 1 if pl 📝 메모개인적으로 합병 정렬의 경우 여기서 구현한 코드가 더 이해하기 쉽다.

코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.class FixedQueue: def __init__(self, capacity): self.no = 0 self.front = 0 self.rear = 0 self.capacity = capacity self.que = [None] * capacity def __len__(self): return self.no def is_empty(self): return self.no = self.capacity def enque(self, x): if self.is_full(): ..

코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.class FixedStack: def __init__(self, maxlen = 256): self.capacity = maxlen self.__stk = [] def __len__(self): return len(self.__stk) def is_empty(self): return not self.__stk def is_full(self): return len(self.__stk) == self.__stk.maxlen def push(self, value): if self.is_full(): rais..

개요해시법(Hashing)은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것이다.키를 특정한 값으로 나눈 값을 해시값(Hash value)라고 하며, 해시값은 데이터에 접근할 때 기준이 된다.키를 해시값으로 변환하는 과정을 해시 함수(Hash function)이라고 하고, 해시 테이블에서 만들어진 원소를 버킷(bucket)이라 한다.해시 충돌(Hash collision)은 키와 해시값의 다대일(n:1) 관계에 의해 저장할 버킷이 중복되는 현상이다.해시법에서 충돌이 발생할 경우 다음 2가지 방법으로 대처할 수 있다.체인법 : 해시값이 같은 원소를 연결 리스트로 관리함오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복함코드 구현코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 ..