꿈돌이랜드

수료는 12월에 했지만 여러 바쁜 개인 사정과 취준으로 인해 이제야 후기를 작성한다. 멤버십 일정 멤버십 초반 8주간은 미션 기반 프로젝트를 수행하고, 6주간은 팀 프로젝트로 이루어진다. 미션 주간 미션은 2주에 1개 미션씩 공개되며, 미션이 공개된 차주는 전주에 공개된 미션의 추가적인 구현 요구사항이 공개된다. 이 초반 8주간의 미션 기반 프로젝트는 정말 재밌었다. 가장 기억에 남는 미션은 아이패드 드로잉 앱을 만드는 미션이었는데, 뷰 계층과 좌표 시스템 개념과 객체지향 개념 등을 함께 동원하여 미션을 완성해 나갔다. 특히 설계가 중요했던 미션이었는데, 추가적으로 미션이 진행되며, 확장성있는 구조를 짜는 방법을 계속해서 고민해야했다. 그리고 ViewController의 비대함을 줄이기 위한 여러가지 방..

프림 알고리즘프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 MST를 구하는 알고리즘동작임의의 정점을 선택해서 비어있는 T 트리에 포함시킨다.T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.이 때, 1에서 찾은 간선도 같이 T에 포함된다.모든 노드가 T에 포함될 때 까지, 1, 2를 반복한다. 아래는 그림으로 설명된 것입니다.임의의 정점을 선택해서 빈 T에 포함시킨다.예를 들어 1을 선택합니다.T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 것을 찾는다. 1-3과 1-2 중, 가중치가 더 작은 간선은 가중치가 4인 1-3을..

운영체제컴퓨터 하드웨어를 관리하는 소프트웨어CPU, 메모리 및 입출력 장치 등의 자원들을 프로그램에 적절하게 할당해야 하는 책임거의 모든 코드가 운영체제 위에서 실행되므로 운영체제 작동방식에 대한 지식은 적절하고 효율적이며 안전한 프로그래밍에 중요하기 때문일반적으로 운영체제에는 각 장치 컨트롤러마다 장치 드라이버가 존재드라이버는 장치 컨트롤러의 작동을 잘 알고 있고 나머지 운영체제에 장치에 대한 일관된 인터페이스를 제공인터럽트장치 컨트롤러가 장치 드라이버에 작업을 완료했다는 사실을 알리는 방법하드웨어는 어느 순간이든 시스템 버스를 통해 CPU에 신호를 보내 인터럽트를 발생시킬 수 있음CPU가 인터럽트 되면, 하던 일을 중단하고 즉시 고정된 위치로 실행을 옮기고 ISR(인터럽트 서비스 루틴)을 실행실행이 ..

신장 트리그래프의 모든 정점을 포함하는 트리를 말한다.그래프의 최소 연결 부분 그래프로 사이클이 없다.정점의 개수가 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가 배열의 끝 위치가 아니라, 길이로 처음에 셋팅한다는 점에 유의하자중간..