앱등개발자IOS

Swift알고리즘 2023. 9. 13. 19:18

removeLast(), append()와 같이 배열의 길이를 조정하는 함수들을 사용해보았고, C언어로 풀이할 때처럼 배열을 최대 크기로 미리 선언해놓고, 그 안의 값을 변경하는 방식으로 풀이해보았는데, 둘 다 실행 시간은 똑같았다!

Swift알고리즘 2023. 9. 13. 12:39

배열을 이용해 체크하며 푼 후, 다른 사람들은 Set을 이용해 많이 풀이한 것 같아 Set자료구조를 활용해서도 풀어보았으나 Swift에서는(다른 언어는 잘 모르겠다) 배열을 사용해 푸는 것이 더 빨랐다!

Swift알고리즘 2023. 9. 13. 11:58

각 Node들의 좌표만 주어지기 때문에, 최소신장트리 알고리즘을 사용하려면, (간선 거리, 해당 간선으로 연결되는 노드 1, 해당 간선으로 연결되는 노드 2) 형태를 Edges 배열에 담아야한다. 우리는 n개의 node좌표만을 받기 때문에, 2중 for문으로 모든 node들 사이의 거리를 측정한다면, n(n-1) / 2로, O(n^2)의 시간복잡도를 가지게 된다..... 메모리 복잡도 또한 비례하게 된다. 하지만, 어차피 최단 거리를 구하는 것이므로, 시간복잡도가 훨씬 적은 "정렬"을 1.x좌표 기준 2. y좌표 기준 3. z좌표 기준 으로 적용하면서, 바로 인접해있는 Node들끼리의 간선만 우리가 취하면 된다.! 이유 ? (a -> b 거리가 3, b -> c 거리가 4일 때, a에서 c로 직통하는 간..

Swift알고리즘 2023. 9. 11. 16:36

Swift알고리즘 2023. 9. 11. 15:45

Swift알고리즘 2023. 9. 11. 15:31

위상정렬 문제이다. 생각보다 헷갈릴 만한 포인트가 많이 들어가있는 문제이다. 1. 같은 숫자가 여러 번 나오는데, 이에 대한 처리를 어떻게 해줘야하는가? 2. 순서를 정하는 것이 불가능한 경우가 어떻게 생기는가?? 먼저 1번의 경우에는, 1 -> 3 2 -> 3 -> 4 2 -> 3 -> 5 과 같이 하나의 점으로 들어오는 경우가 많은 와중에, 2 -> 3 과 같이 동일한 것이 여러 번 나올 때는 나올 때마다 graph[2].append(3)해주면 된다. 이유? 어차피 위상정렬을 수행하면서 2가 queue에서 나오고, 2에서 들어가는 점들에 대한 indegree를 1씩 감소시킬텐데, 그 때 알아서 겹쳐서 제거될 것이기 때문! ( Graph가 set이 아닌 Array 형태이므로 걱정할 것 없음) 2번 같은..

Swift알고리즘 2023. 9. 8. 01:44

Swift알고리즘 2023. 9. 8. 00:50