MST Spanning Tree: 최소한 간선을 사용하여 그래프 내 모든 정점을 이은 트리(트리는 사이클이 없다는거 주의) n개의 정점에 n-1개의 간선이 존재하는 그래프는 트리 가중치가 있는 그래프에서 최소 비용을 사용하면 Minimum Spanning Tree Union-Find 특정 원소들을 합칠때 이들이 같은 집합에 포함되어 있는지 확인하거나 두 집합을 합칠때 사용한다. Kruskal Algorithm 최소비용 간선을 선택해나간다. 이때 사이클이 발생하지 않도록 하는데 그 과정에서 Union-Find를 사용하면 사이클이 발생하는지 체크할 수 있다. 간선의 가중치가 작은 것부터 순서대로 보면서 해당 간선 양 끝에 있는 두 노드 x, y에 대해 find(x), find(y)값을 비교하여 일치하지 않는..
Prim Algorithm 크루스칼이 최소비용 간선을 선택해 나간다면, 프림 알고리즘은 최소비용 간선이 있는 정점을 선택해 나간다. 시간복잡도 우선순위 큐 O(ElogV) 인접행렬 O(V^2) 구현 import heapq INF = int(1e9) def prime(start): queue = [] heapq.heappush(queue, (0, start)) distance[start] = 0 while queue: dist, u = heapq.heappop(queue) for v, c in graph[u]: if c < distance[v]: distance[v] = c n, m = map(int, input().split()) # 노드, 간선 개수 start = int(input()) # 출발 노드 ..
🎄 특별한 이진 트리 완전 이진 트리에서 부모 노드가 자식 노드 값보다 같거나 작은(MinHeap)/큰(MaxHeap) 경우를 만족한다. 현재 남아있는 원소들 중 최대값 or 최솟값을 빠르게 계속 얻고 싶은 경우에 유용 heap만드는 데 O(NlogN) 소요 이후 삽입, 삭제 O(logN) 최소값 or 최대값 탐색 O(1)
트리 🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프 ⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다. 이진 트리 🌲 자식 수가 최대 2개인 트리 이진트리 탐색 전위 탐색: 부모 - 좌 - 우 중위 탐색: 좌 - 부모 - 우 후위 탐색: 좌 - 우 - 부모 이진탐색트리 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함 우측 방향에 있는 노드들은 전부 ..
공식문서 누구나 쉽게 이해할 수 있는 Git 입문 git 개념 버전 관리? 파일의 변화를 시간에 따라 기록했다가 필요한 경우 특정 시점의 버전을 다시 꺼내올 수 있는 시스템 중앙집중식 버전 관리(CVCS) 중앙 서버에 문제가 생기면 협업 불가 분산 버전 관리 시스템(DVCS) 로컬 저장소가 원격 저장소의 파일, 히스토리 모두 복제 -> 백업 유리 git 기본 Repository: local - remote 원격 저장소 연결 git clone :원격 저장소 받아오기 git remote add origin 원격저장소주소 upstream 저장소 설정 git remote add upstream 저장소 : 포크한 저장소의 원본 저장소 연결 git remote set-url **upstream** 원격 저장소 확인..
연결 리스트 연결된 데이터를 저장할때 사용합니다. 연결리스트를 구성하는 노드의 구조는 다음과 같습니다. node data link(next) 장점단점 삭제와 삽입 O(1) 길이가 정해지지 않은 데이터를 다룰때 유용 메모리 요구량이 더 크다 원하는 위치 검색할 때 처음부터 다 확인해야한다 배열과 비교 배열연결리스트 삽입/삭제 O(n) O(1) 저장공간 연속한 위치 임의의 위치 탐색 O(1) O(n) 단순 연결 리스트 구현 노드 class Node: def __init__(self, item): self.data = item self.next = None 연결 리스트 class LinkedList: def __init__(self): self.nodeCount = 0 # 노드의 개수 self.head = N..
