Algorithm15 [MST/Union-Find]최소 신장 트리와 크루스칼 알고리즘 최소 신장 트리 (Minimum Spanning Tree, MST) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하면서, 사이클을 형성하지 않는 트리/그래프 를 말합니다. 그리고 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리를 말합니다. 즉, 신장 트리를 최소한의 값으로 구성하는 경우를 뜻합니다. 최소 신장 트리를 구하는 2가지 대표적인 알고리즘이 있는데 프림과 크루스칼 알고리즘입니다. 프림 알고리즘은 노드(정점)를 기준으로 최소 신장 트리를 구하는 다익스트라 알고리즘과 유사한 구조의 bfs 알고리즘 입니다. 크루스칼 알고리즘은 간선을 기준으로 최소 신장 트리를 구하는 유니온 파인드를 활용하는 알고리즘입니다. 크루스칼 알고리즘 우선 주어진 그래.. 2023. 11. 26. 2023 현대모비스 예선 - 상담원 인원 https://school.programmers.co.kr/learn/courses/30/lessons/214288 현대 모비스 경진대회 예선 문제가 떠서 그 중 1번 문제를 풀어보았다. 2번은 20점 나옴... 디버깅(?)은 보류 중이다ㅠ 나의 풀이 문제 유형은 구현인 것 같다. 브루트 포스와 정렬을 활용하는? 탑다운 디피? 를 이용해서 각 상담 유형의 멘토수 별 대기 시간을 2차원 배열에 저장했다. 최소 힙😍을 이용해서 최단 대기시간 상담원을 바로 탐색할 수 있도록 했다. 브루트 포스 + dfs 를 이용해서 모든 케이스의 대기 시간 조합을 구현한다. 기존 최소 시간을 초과해버리는 경우는 백트래킹하도록 한다. # 상담 유형 k # 멘토 수 n # 요청 from collections import defa.. 2023. 9. 29. 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. 이전 1 2 3 4 다음