꿈돌이랜드

신장 트리그래프의 모든 정점을 포함하는 트리를 말한다.그래프의 최소 연결 부분 그래프로 사이클이 없다.정점의 개수가 n개면 간선의 개수가 n-1개 이다.최소 신장 트리신장 트리는 신장 트리 중 가중치 합이 최소인 신장 트리를 말한다.예제)도시마다 도로를 짓는데 최소 거리가 되도록 구축집마다 전화망 설치하는데 최소 비용이 되도록 설계 최소 신장 트리 알고리즘대표적으로 크루스칼, 프림 알고리즘이 있다.크루스칼 알고리즘그리디 알고리즘을 이용한다.간선 선택을 기반으로 하는 알고리즘최소 신장 트리가 최소 비용의 간선으로 구성되고, 사이클을 포함하지 않는다는 두 조건에 따라서 매 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.이전 단계에서 만든 신장 트리와는 관계 없이 무조건 최소 간선만을 선택하는 방법..

크루스칼 알고리즘그리디를 사용하여 그래프의 최소 신장 트리를 구하는 알고리즘최소 신장 트리가 1) 최소 가중치의 간선으로 구성, 2) 사이클을 포함하지 않다는 조건으로 각 단계에서 사이클을 이루지 않는 최소 가중치 간선을 선택한다.동작그래프의 간선들을 가중치의 오름차순으로 정렬한다.정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.가장 낮은 가중치를 먼저 선택사이클을 형성하는 간선을 제외해당 간선을 현재의 최소 신장 트리의 집합에 추가한다.주의할 점은 간선을 선택할 때, 해당 간선이 사이클을 생성하는지 그 여부를 확인해야 하는데, 그 여부를 검사하기 위해 유니온 파인드 알고리즘을 이용해야 한다. Disjoint-Set유니온 파인드 알고리즘에 대해 공부하기 전 Disjoint-Set의..

벨만 포드 알고리즘벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘다익스트라 알고리즘과 다르게 음수 가중치가 있는 그래프에서도 최단 거리를 구할 수 있다단, 다익스트라 알고리즘은 시간복잡도가 O(ElogV)인데 비해, O(VE)로 느리다. 다익스트라 알고리즘 vs 벨만-포드 알고리즘다익스트라벨만포드매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 방문하여 한 단계씩 최단 거리를 구해나간다 (그리디)매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다.음수 간선이 있는 경우를 제외하면 최적의 해를 찾을 수 있다음수 간선이 있는 경우에도 최적의 해를 찾을 수 있다.시간복잡도가 O(ELogV)시간복잡도가 O(VE..

https://github.com/apple/swift-nioiOS 앱 내에 로컬 프록시 서버를 구축하기 위해 방법을 찾아보던 도중, 서버 개발을 위한 SwiftNIO라는 애플의 프레임워크를 알 게 되었습니다.사용 방법을 위해 README를 읽고 번역해보았습니다. 오역이 있을 수 있습니다.Swift로 서버를 구축해보고자 하시는 분들께 도움이 되었으면 합니다. SwiftNIO는 유지 관리 가능한 고성능 프로토콜 서버 및 클라이언트의 신속한 개발을 위한 크로스 플랫폼 비동기, 이벤트 드리븐 네트워크 어플리케이션 프레임워크.Netty와 비슷하지만, Swift용으로 작성됨.개요SwiftNIO는 기본적으로 Swift에서 고성능 네트워킹 어플리케이션을 구축하기 위한 도구.특히 thread-per-connect 동시..

LowerBound동작방식구현UpperBound동작방식구현참조LowerBound와 UpperBound는 모두 이진탐색(BinarySearch)을 응용한 알고리즘이다.일반적으로 이진탐색은 찾고자 하는 값이 정확히 없다면 탐색을 실패한다.하지만 LowerBound와 UpperBound는 범위에 초점이 맞춰져 있어, 같은 원소가 여러개 있더라도 사용할 수 있다.개념은 알지만 구현 시 자주 헷갈리므로 정리해보자.LowerBound동작방식LowerBound는 찾고자 하는 값 이상의 값이 처음으로 나타나는 인덱스이다.LowerBound의 동작 방식은 다음과 같다. 초기에 left는 배열의 시작 위치, right는 배열의 길이로 세팅한다right가 배열의 끝 위치가 아니라, 길이로 처음에 셋팅한다는 점에 유의하자중간..

How to add reactive-ness to Clean Swift - Clean SwiftI answered different forms of this same questions many times in emails, comments, and my mentorship program. I understand why people ask this question. They’ve seen MVVM, ReactiveCocoa, RxSwift, and want to see if Clean Swift can handle this model-view update automatically. My answer is always the same. You don’t need it. You don’t need...http..