Algorithm/알고리즘4 [MST/Union-Find]최소 신장 트리와 크루스칼 알고리즘 최소 신장 트리 (Minimum Spanning Tree, MST) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하면서, 사이클을 형성하지 않는 트리/그래프 를 말합니다. 그리고 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리를 말합니다. 즉, 신장 트리를 최소한의 값으로 구성하는 경우를 뜻합니다. 최소 신장 트리를 구하는 2가지 대표적인 알고리즘이 있는데 프림과 크루스칼 알고리즘입니다. 프림 알고리즘은 노드(정점)를 기준으로 최소 신장 트리를 구하는 다익스트라 알고리즘과 유사한 구조의 bfs 알고리즘 입니다. 크루스칼 알고리즘은 간선을 기준으로 최소 신장 트리를 구하는 유니온 파인드를 활용하는 알고리즘입니다. 크루스칼 알고리즘 우선 주어진 그래.. 2023. 11. 26. Set 과 복사/깊은복사 생각해보기 나의 해석🤔 set은 해쉬 가능한 요소를 담을 수 있다는 점이 있다. 그러니까 set 자체로 고유한 값만 담게 된다. 변경이 가능한 값은 담지 않는다. 즉, 튜플은 담아도 리스트는 담지 않는다. deepcopy()를 굳이 실행할 이유가 없다는 것이다. 왜냐하면 셋의 요소들은 항상 불변하기 때문이다! 참고 [Python] set에서 deepcopy의 실효성 (AIFFEL 12/30 일기) deepcopy() 메소드가 동작은 된다고 한다. 아마, 특정 인터페이스 혹은 부모 클래스를 구현, 상속하고 있어서 deepcopy() 메소드도 구현을 해둔 게 아닐까?! 2023. 9. 2. bisect 정렬키 설정하기(부제: bisect 최고) bisect 정렬키 설정 python 10 이전 KeyWrapper 를 정의해서 쓰는 복잡한 방법이 존재한다. 아직 디자인 패턴에 대한 이해가 얕다보니 명확하게 와닿는 건 아니지만 래퍼(프록시)를 씌워서 키를 bisect에게 보여주고, 이를 이용해 정렬을 수행하되 실제 아이템 요소를 보여줄 때는 키가 아닌 실제 데이터 값을 보여주도록 만든 것 같다. from bisect import bisect_left, insort_left class KeyWrapper: def __init__(self, iterable, key): self.it = iterable self.key = key def __getitem__(self, i): return self.key(self.it[i]) def __len__(self.. 2023. 9. 2. 위상정렬(topology sort) 위상 정렬 이란? 정렬 알고리즘의 일종으로 방향 그래프의 모든 노드들을 간선의 방향을 거스르지 않으며, 순서대로 나열하는 것을 말한다. 이 때, 우리에게 주어지는 방향 그래프는 사이클을 형성하지 않는 단방향 비순환 그래프(DAG, Directed Acyclic Graph) 일 것이다. 위상 정렬 구현 위상 정렬을 구현하기 위해서 모든 노드의 진입 차수를 나타내는 배열과 큐 자료구조를 활용한다. 참고로 스택을 활용할 수도 있다고 한다. 구현 로직을 살펴보면 bfs 형태인 것 같다. 진입 차수 레벨에 따라서 큐에 다음 방문 노드를 저장해둔다. 반복문을 통해서 큐에 존재하는 노드를 하나씩 꺼내어 결과 배열에 삽입한다. 그래프 탐색을 통해 방문한 노드로부터 다음에 방문하게 될 노드들을 찾아, 이들의 진입 차수를.. 2023. 7. 8. 이전 1 다음