앱등개발자IOS

본격적으로 Swift로만! 알고리즘 테스트에 임하기 위해 (python 빠이빠이...) 이전에 python으로는 해결해 본 적 있는 문제들을 Swift로 풀이하며 포스팅해보려고 한다. 카카오에서는 확실히 다양한 자료형을 사용하도록 유도하는데, 딕셔너리 선언과 사용이 아직은 익숙하지 않았다. 그래도 로직이라는 것은 똑같으니 크게 어렵지는 않게 구현할 수 있었다. 두가지 자료형만 만들어낸다면, 그 뒤로는 어렵지 않다. - dict라는 딕셔너리에는, key에 모든 Id를 담아, 자신을 신고한 사람들의 id를 모두 담는다 ( 중복 제거를위해 Set자료형으로 ) - id_sequence에는 우리가 "muzi"라는 id가 id_list에서 몇 번째 index에 위치해있는지 바로 알고싶을 때 사용할 수 있도록, id..

Swift알고리즘 2022. 6. 18. 17:13

이진탐색( Binary Search )의 확장판인 Parametric Search로 해결해야하는 문제이다. Parametric Search를 생각해내는 것 뿐만 아니라, 그 내부 구현까지 매우 난이도가 높은 문제라고 생각한다. 배열에 존재할 수 있는 1 ~ n * n까지의 수 범위에서 이분탐색하며, 현재 mid에 위치하는 숫자에 i 대하여, (i를 포함함에 주의) i 이하의 숫자가 배열에 몇 개 존재하는지 its_order()함수에서 return해준다. 주의해야 할 점이 두가지 있다!! 1. n = 3인데, i = 7인 경우와 같이 없는 숫자가 매개변수로 전해지는 경우 2. k = 7인데, 1 2 2 3 3 4 6 6 9 과 같이 its_order()의 리턴값이 7은 절대 나올 수 없는 경우 ( 같은 숫..

Swift알고리즘 2022. 6. 17. 20:44

꽤나 까다로운.... Swift로 풀이하기는 더더욱 까다로운 문제였다. Swift의 함수는 매개변수로 배열이든 뭐든 다 값 타입으로 전달하기 때문에, inout 처리해주어 참조타입으로 넘겨주는 것을 조심해야한다. 또한 union함수에서 a, b가 아닌 그들의 부모node인 a_p와 b_p를 사용해 갱신해줘야하는 것도 잊지 말아야한다!!( 이 부분을 실수해 헤맸다..) 이외에 pow()함수를 사용해 제곱, 루트 값을 도출해내는 것, Comparable 프로토콜을 준수하지 않는 Tuple의 배열을 클로저로서 sort()해주는 것 정도가 이 문제를 Swift로 풀이하는데 중요한 Point인 것 같다.

카테고리 없음 2022. 6. 17. 19:08

FLoyd- Warshall 알고리즘 (3중 for문)을 사용해 해결한 문제이다. 확실히 반복문을 돌리는 데 python은 약할 수 밖에 없는 것 같다.... 문제의 테스트케이스를 보면, 본인에서 본인으로 가는 경로를 나타내는 대각선 위치에 대하여, 결과가 0일 때가 있고, 1일 때가 있음을 확인할 수 있다. + (대각선은 무조건 0이라고 문제에 명시되어있다) 이는 자기자신에서 다른 node들을 통해 자기 자신으로 돌아올 수 있는 경로가 존재하는 경우에 1로 나타냄을 눈치채야한다!! 보통 필자는 Floyd알고리즘을 구현하며 i == k, j == i or j == k인 경우 continue를 처리해주지만, 이 문제에서는 i번 노드에서 i번 노드로 가는 경우도 체크해주어야하므로 3중 for문을 full로 ..

Swift알고리즘 2022. 6. 17. 18:28

이전에 포스팅했던 적 있는 간단한 DFS 혹은 BFS 문제입니다. 조금 다른 풀이방식으로 구현을 했기에 다시 한 번 포스팅을 하게되었습니다.. 기존 알고리즘 풀이는 항상 Python으로 진행하다가, IOS개발자로서 본격적으로 코딩 인터뷰를 대비하게 되며 Swift로 알고리즘을 구현하게 되었고, 처음 BFS를 구현해보면서 배운 방법은 - BFS의 queue의 맨 앞 원소를 "Pop"하지 않고, 현재 맨 앞을 나타내는 Index를 정수 변수로 두어 q.count > Index인 동안만 while문을 돌리는 것이었습니다. 이는 실행시간 면에서는 더 빠를 것입니다 ( Array의 원소를 없애는 과정이 생략되었으므로 ) 하지만 많은 데이터를 q에 담아야하는 경우에는 메모리 초과가 날 수 있겠죠.... 이러한 생각..

Swift알고리즘 2022. 6. 17. 17:58

기본적인 투포인터 문제이며, start, end가 같이 출발하여 같은 방향으로 진행하는 문제는 아니고, start와 end가 양 끝에서 시작하여 만나는 순간 종료하는 투포인터 문제이다. 두개의 용액을 선택하는 경우 중, 합이 가장 0에 가까워지는 경우를 찾아야하는데, 이미 용액들은 정렬되어 나오기 때문에 start = 0 end = data.count - 1로 두고 시작하면 된다! while 문의 종료조건은 start == end가 되는 순간이다.

Swift알고리즘 2022. 6. 17. 00:02

2차원 공간에서 누적합 문제를 풀어보았다면 해결할 수 있었던 문제이다. 유사한 문제를 풀어본 경험이 없다면 이와같은 아이디어를 떠올리기는 쉽지 않을 것 같다. 필자도 처음 이 문제를 접했을 때는 정확도만 해결했고, 모든 TC에서 시간초과 판정을 받았다. 아래의 블로그에서 누적합 풀이방식과 그림을 참고하여 Swift로 작성해 시간을 통과할 수 있었다. 아래의 방식으로, 매 번 직사각형의 모든 범위에 값을 갱신하지 않고, 직사각형의 꼭짓점 "네 곳" ( 오른쪽 변의 두 모서리는 한 칸 더 확장하여 위치함)만 갱신해준 후, 마지막에 26~ 30번 코드와 같이 가로로 전파 31~36 코드와 같이 세로로 전파 해준다. 이후 2차원 배열을 모두 탐색하며 1보다 크게 되는 칸의 수만 센다. 그림 출처: https:/..

Swift알고리즘 2022. 6. 11. 21:27

이 문제는 처음 마주쳤을 때, 결국 모든 node로부터 다른 node까지의 최장 거리를 구하고, 그 중에서 최장거리를 구해야하므로, Floyd-Warshall 알고리즘을 사용할까?? 생각했었다. 그러나 2차원 배열로 지도가 주어졌고, 가로,세로 길이가 50 이하이므로, bfs로 모든 점들에 대하여 최장거리를 구하고, 그들 중 또 최장거리를 뽑아 답으로 return하는 편이 낫다고 생각했다.

Swift알고리즘 2022. 6. 7. 23:27