앱등개발자IOS

서로소를 확인할 수 있는 union-find알고리즘과 이를 이용하여 "무방향 그래프"에서 최소 스패닝트리, 즉 모든 노드를 포함하지만 싸이클이 발생하지 않는 부분 그래프 중 간선의 비용 합이 최소가 되는 경우를 찾아야하는 기본 "크루스칼" 알고리즘 문제이다. 파이썬으로는 해당 알고리즘을 많이 작성해보았지만, Swift로 처음 구현하려다보니 막히는 부분이 몇 있었다! Swift로 코딩 인터뷰를 수행하려면 알아두어야할 꿀 표현들이 들어있는 문제였다. - 1. 1~n까지 자연수가 오름차순으로 위치한 1차원 배열 초기화! - 2. 2차원 배열 [ (a.0, a.1, a.2), (b.0, b.1, b.2), (c.0, c.1, c.2)]과 같은 형태에서, n번째 원소 기준으로 sort하기 위의 두가지 표현을 py..

Swift알고리즘 2022. 5. 23. 11:32

기본 플로이드 워셜 (Floyd - Warshall)알고리즘 구현 능력을 묻는 문제이다. 한 가지 주의할 점은 동일 경로 간에 여러 버스가 존재할 수 있다고 했으니, m개의 간선들에 대한 정보를 distance 2차원 배열에 저장할 때 해당 경로를 지나갈 때의 최솟값을 배열에 저장할 수 있도록 해야한다 ( 16 ~ 17 째 줄) 그 이외에는 기본 플로이드 워셜 알고리즘대로 n개의 노드를 지나쳐가는 경우에 따라 최단경로 갱신을 진행해준다 ( 20 ~ 30 째 줄) 33 ~ 마지막 줄은 3중 for문( floyd )를 돌며 구한 최단경로를 문제에서 제시한 조건대로 출력해주는 과정이다.

Swift알고리즘 2022. 5. 23. 10:34

전형적인 이분탐색(Binary Search)에서 조금의 응용만 한다면 풀 수 있는 문제이다. 블로그들을 찾아보면 많은 알고리즘이 그렇듯 이분탐색에서 start, end 인덱스를 사용하는 방식이 천차만별인 것 같다. 나는 start와 end를 "아직 후보군에서 탈락하지 않은 것들"의 양 끝을 가리키도록 한다. 따라서 start가 end보다 "커지면"!! ( 같을 때까지는 아직 그 마지막 원소를 탐색해야 하므로.. ) 탐색을 종료하고 None혹은 Never를 return한다. 여기서는 나무를 최소 m만큼 가져갈 수 있게 잘라야하므로, 딱 m을 가져가지 못할 수 있다. 예를 들면, 3만큼의 길이를 가져가야하는데, 길이가 10인 나무만 두 그루 있는 경우, 우리는 4 만큼의 길이를 가져갈 수 밖에 없다. 따라서..

Swift알고리즘 2022. 5. 21. 21:09

# Swift의 입출력 -> python과 같이 print()는 default로 줄바꿈으로 끝낸다. python pring(~~ , end = " ")는 swift에서 print(~~ , terminator: " ")로 print()의 마무리를 설정할 수 있다. -> 위와 같이 입력은 readLine()로 받을 수 있다. Optional로 감싸져 나오므로 언래핑해서 사용해야함을 주의! # Swift의 형변환 readLine()으로 입력받은 Optional 타입을 언래핑 후 Int형으로 형변환 하였다. 형변환 시 Optional로 래핑됨을 주의! # Swift의 배열 생성 (원소 반복) python에서는 arr = [0] * (n+1) 과 같이 1차원 배열에 "0"을 반복하여 생성하고, arr = [[0]..

Swift for Coding Interview 2022. 5. 21. 20:42

주어진 간선들을 인접리스트 형태로 저장하고, dfs 혹은 bfs로 풀 수 있는 기본 형태의 문제. python에서는 from collections import deque 로 덱을 임포트하여 편하게 deque 자료구조를 사용할 수 있었지만, Swift에서는 Queue가 따로 제공되지 않는다! ( 라고 알고있다..) 따라서 q.popleft()하는 과정 없이 q에는 들어오는 원소들을 계속 쌓아두고, 현재 남아있는 원소 중 가장 밑에 있는 것, 즉, popleft()를 했다면 맨 왼쪽에 남아있을 원소의 인덱스를 idx라는 변수로 가리켰다. 처음엔 좀 불편했지만 좀 더 컴공스러운 (?) 방식인 것 같아서 매력 있는 것 같다( ㅎㅎㅎ...) 아무튼 이렇게 bfs로 구현해보았다.

Swift알고리즘 2022. 5. 21. 20:28

2차원 배열을 돌며, 0이 아닌 값을 만날 때마다 dfs를 호출하여 해당 칸과 상,하,좌,우로 이어진 모든 칸을 2로 바꾸어주며, dfs가 호출된 횟수를 세주면 되는 기본 dfs문제이다. 각 단지에 몇개의 집이 이어져있는지 danji배열에 넣어놓고 오름차순으로 출력해야했기 때문에 danji.sort() 함수를 사용했다. 그 외 특이사항 X

Swift알고리즘 2022. 5. 21. 20:10

Swift로 처음 풀이한 백트래킹 문제이다. 백트래킹 기본 - 순열을 구하는 문제이다. visited를 체크하여 뒷쪽 숫자를 먼저 result에 기록한 후에도 그 앞쪽 숫자를 기록할 수 있도록하였다. ex) 1,5,2 이 문제에서는 1~n까지의 자연수를 사용하므로 사실 data배열에 1~n까지의 자연수를 담지 않고, dfs함수의 반복문 속의 index (i )를 사용하면되지만, 정형화된 연속된 자연수가 data로 주어지지 않는 대부분의 경우에서 사용하기 위해 data에 숫자들을 담아 풀이했다!

Swift알고리즘 2022. 5. 21. 16:37

투포인터 기본 문제이다. 배열의 처음과 끝까지 탐색하며 연속된 구간의 합이 m이 되는 경우의 수를 구하면 되는 문제.

Swift알고리즘 2022. 5. 21. 16:16