본문 바로가기

분류 전체보기96

GCD (Grand Central Dispatch) iOS의 중요한 개념 중 하나인 GCD!! GCD가 뭘까요? GCD는 Grand Central Dispatch 의 줄임말입니다. GCD에 대해 자세하게 알아보기 전에 왜 GCD가 나오게 됐는지, 그 배경부터 살펴보겠습니다. 멀티 코어 프로세서에서는 프로그램의 동작을 멀티 프로세서에게 어떻게 잘 배분하는지가 중요합니다. GCD 이전에는 멀티 스레딩을 위해 Thread와 OperationQueue 등의 클래스를 사용했다고 하는데요, Thread는 복잡할 뿐만 아니라 임계 구역 (Critical Section) 등을 이용한 Lock을 관리하기 까다로웠습니다. 그리고 OperationQueue는 GCD에 비해 무겁고 Boilerplate Code들이 많이 필요한 문제가 있었죠. 그래서 Apple은 GCD를 내놓.. 2021. 3. 23.
플로이드 와샬 (Floyd Warshall) 플로이드 와샬 역시 벨만 포드나 다익스트라와 같은 최단 경로 찾기 알고리즘입니다. 다만, 1:N 최단 경로를 찾는 벨만 포드와 다익스트라와 달리, 플로이드 와샬은 N:N 사이의 최단 경로를 찾습니다. 그렇기 때문에 비용을 저장하는 배열로 이중 배열을 사용하게 됩니다. 순환만 발생하지 않는다면 음수 가중치도 가능하며, 기본적으로 동적계획법으로 접근하게 됩니다. 플로이드 와샬은 가능한 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단거리를 확인하기 때문에, 시간복잡도는 O(N^3)이 나옵니다. 역시 n:n 경로라 그런가 다른 알고리즘들보다 시간이 많이 걸리네요ㅎ.. 먼저 플로이드 와샬을 구현하기 위해서 좀 복잡하지만 아래와 같은 그래프를 사용하겠습니다. 그래도 보는사람 쉽게 보시라고 제가 색도 다르.. 2021. 3. 23.
다익스트라 (Dijkstra) 오늘은 최단거리 구하는 알고리즘 중 다익스트라 알고리즘에 대해 알아보려 합니다. 학교에서 갓 2학년에 되었을 때 알고리즘 수업시간에 다익스트라를 배웠었는데요, 사실 1학년 말에도 과 학회 선배들이 다익스트라를 알려줬었습니다. 하지만 저는 이것만큼 거부감드는게 없었어요ㅠㅠ 그냥 다익스트라 라는 단어 자체가 너무 어려워 보였던 것 같습니다. 하지만 이제와서 다시보니 왜 이렇게 간단한 개념을 이해조차 못했는지.. 이렇게 보니 저도 그 때보다 성장하긴 했나봐요ㅎㅎ.. 다익스트라는 V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점 (S) 에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (1:N) 입니다. 벨만-포드 알고리즘과 달리 음의 가중치를 가지지 않아, 각 정점을 최대 한.. 2021. 3. 9.
벨만-포드 (Bellman-Ford) 오늘은 최단 경로를 찾는 대표적인 기법 중 하나인 벨만-포드 알고리즘을 알아보려 합니다. 벨만-포드는 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점 S 에서부터 다른 정점까지의 최단경로 (1:N) 를 구하는 알고리즘입니다. 다익스트라와 달리 음의 가중치를 가진 간선을 가질 수 있고, 때문에 음의 사이클의 존재 여부를 확인해주어야 합니다. 최단거리를 구하기 위해 최대 (V-1)번 E개의 모든 간선을 확인하고, 음의 사이클을 확인하기 위해 한 번 더 E개의 간선을 확인합니다. 따라서 벨만-포드 알고리즘은 O(VE)의 시간복잡도를 가지게 됩니다. 구체적인 벨만-포드 Swift 코드를 보기 전에, 벨만-포드 알고리즘의 구현을 슈도 코드(Pseudo Code)로 먼저 보겠습니다. 슈도 코드.. 2021. 3. 8.
크루스칼 (Kruskal) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다. 크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다. 그럼 크루스칼을 한 번 구현해볼까요? 크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다. Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다. Step 2. 가장 위의 간선(비용이 가장 적.. 2021. 3. 4.
Disjoint-Set / Union-Find (디스조인트 셋, 유니온 파인드) 저는 예전에 디스조인트 셋이 유니온 파인드인지 몰라서 엥? 디스조인트 셋? 이건 뭐랭 했었는데 알고보니 같은 말이었네요ㅋㅋㅋ 그래서 말이죠, 오늘은 크루스칼에서도 사용되는 Disjoint Set을 알아볼게요. Disjoint Set의 원리는 서로소 집합과 연관되어 생각하면 됩니다. 새로운 집합을 추가하거나, 기존의 집합과 합치거나, 집합에 어떤 원소가 들어있는지 찾는 연산을 거의 선형시간에 가깝게 수행하는 자료구조라고 할 수 있죠. Disjoint Set이 Union-Find라고도 불리는 이유는, Disjoint Set을 구성하는데에 union과 find라는 함수? 개념? 을 사용하기 때문입니다. find를 통해서 a라는 요소가 b라는 요소와 같은 집합인지(연결되어 있는지) 를 확인 할 수 있고, uni.. 2021. 3. 3.
XCTest tips and tricks that can level up your Swift testing iOS에서의 Unit Test를 위해 XCTest에 대해 알아보던 중 XCtest tips and tricks that can level up your Swift testing 이라는 블로그를 보게 되었습니다. XCTest에 대한 내용과 참고 게시물의 내용을 함께 번역 및 정리해보면 좋을 것 같았습니다. 중간중간 제가 이해가지 않는 tip들은 직접 예시코드를 작성해보면서 이해해보려고 노력해봤는데, 아직까지는 좀 더 학습이 필요한 것 같아요 :) 그럼 먼저 XCTest가 무엇인지부터 알아볼까요? What is XCTest? 먼저 애플에서는 XCTest에 대해 이렇게 말하고 있습니다. Create and run unit tests, performance tests, and UI tests for your X.. 2021. 3. 3.
Frame과 Bounds iOS 개발을 하다보면 거의 무조건 접하는 것 중 하나가 바로 frame과 bounds입니다. 저는 사실 frame과 bounds가 어떤 차이가 있는지 잘 모르고 사용했는데, 모르고 사용하니까 너무 답답하더라구요. 네, 그래서 알아봤습니다! 먼저 Frame과 Bounds가 애플에서는 뭐라고 정의되고 있는지 한 번 볼게요. Frame The frame rectangle, which describes the view's location and size in its superview's coordinate system. 👉Frame은 SuperView(상위뷰)의 좌표 시스템 안에서의 View의 위치와 사이즈를 나타냅니다. Bounds The bounds rectangle, which describes the .. 2021. 2. 26.
Lower / Upper Bound Binary Search (이분 탐색) 가 '원하는 값 x를 찾는 과정' 이라면, Lower Bound는 '원하는 값 x 이상이 처음 나오는 위치를 찾는 과정' 입니다. 마찬가지로 Upper Bound는 '원하는 값 x를 초과한 값이 처음 나오는 위치를 찾는 과정' 입니다. 따라서 Lower Bound와 Upper Bound를 이해하기 전에 Binary Search (이분 탐색) 에 대해 먼저 이해하고 오셔야 합니다❗️❗️ Lower Bound 의 계산 과정은 이분 탐색과 다를 바가 없습니다. 1. 탐색할 리스트는 정렬되어 있어야 한다. 2. start와 end, mid 변수로 이분탐색을 시작한다. 3. mid의 값이 number보다 작을 때 start를 mid+1로 설정한다. 4. mid의 값이 num.. 2021. 2. 26.
투 포인터 (+ 백준 2003) 오늘은 투 포인터라는 개념을 알아보겠습니다! 투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다. 사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤.. 2021. 2. 25.
Linked List (링크드리스트) 링크드 리스트는 이름과 같이 하나하나의 요소가 연결되어 리스트를 이루는 구조입니다. 그리고 보통 싱글 링크드 리스트 (Single Linked List)와 더블 링크드 리스트 (Double Linked List)로 나뉩니다. 링크드 리스트를 사용하게 되면, 새로운 요소를 넣을 때 그 요소와 원래의 요소들을 연결하기 때문에 미리 데이터 공간을 할당할 필요가 없어집니다. 하지만 연결을 위한 별도 데이터 공간이 필요하기 때문에 저장공간 효율이 높지는 않습니다. 중간 데이터를 삭제할 때도 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하죠. 하지만 만약 데이터를 얼마나 집어넣을지 모르는 상태라면 링크드리스트를 사용해보는 게 좋습니다. 애초에 많은 데이터 공간을 할당하고 시작하는 것보다 리스트에 추가해.. 2021. 2. 24.
PriorityQueue (우선순위 큐) Priority Queue (우선순위 큐)는 말 그대로 사용자가 지정한 조건에 따라 우선순위가 정해집니다. 일반적인 Queue는 단지 데이터가 들어오는 순서에 따라 FIFO(First In First Out) 구조를 따르게 되는데, Priority Queue는 우선순위가 높은 데이터부터 pop됩니다. PriorityQueue는 우선순위에 따라 Heap(힙) 자료구조로 데이터를 저장하게 되기 때문에 삽입과 삭제의 시간복잡도는 O(log n)으로 매우 빠른 시간을 자랑합니다. 제가 이 Priority Queue (우선순위 큐)를 Swift로 직접 구현하기 위해 이전 게시물에서 Heap(힙) 자료구조를 공부했었습니다!! Queue도.. Stack도.. PriorityQueue도 없는 Swift는... 사용하려.. 2021. 2. 19.

티스토리툴바