앱등개발자IOS

이 문제에서 가장 중요하며, 가장 판단하기 어려운 것이 "사전순 정렬"하는 것 이라고 생각한다. 이 문제를 처음 봤을 때, 가장 먼저 떠오른 풀이방법중에 "사전순 정렬하기"가 포함되어있었다면, 당신은 알고리즘 실력자라고 생각한다. 순차적으로 접근해보자. 우리는 각 단어들에 대하여, "본인이 distinct해지는 최소 index를 찾아야한다" 즉, 여기까지 치면 무조건 "나"를 지칭하는거야! 라고 판단할 수 있는 위치(index)를 찾아야하는 것이다. 처음 마주치면, 각 단어들에 대하여 "다른 모든 단어"들과 비교하여 distinct해지는 위치를 찾아야 할 것만 같은 생각이 들기 쉽다. 하지만, 우리는 이 단어들을 '내림차순' 혹은 '오름차순'으로 정렬한다면 양 옆에 붙어있는 단어들과 겹치는 부분만 체크하..

Swift알고리즘 2022. 6. 6. 16:38

바로 전 포스팅인 "촌수계산"과 거의 동일한 문제이다. 촌수계산을 푼 뒤 곧바로 풀었기에 수월하게 풀이했다. 1. 각 노드간의 연결선을 입력받으며, 어디가 윗쪽일지 알 수 없으므로, 일단 간선을 양 방향으로 모두 graph에 입력해주어야한다. 2. 무한 조회를 하면 안되므로, visited 배열에 방문여부를 담아, 한 번 체크한 node는 다시 체크하지 않도록! 3. Root노드인 1부터 아래로 쭉~ 내려가며 새로 나오는 node의 부모는 "현재의 node"라고 parent배열에 저장해준다 끝

Swift알고리즘 2022. 6. 6. 15:46

각 자식의 부모는 하나만 주어진다고 하였으므로, 노드간의 거리를 구하면 되는 문제이다. 친척관계를 구해야하는 두 사람 딱 "한 쌍"이 미리 주어지기 때문에, 딱 그 둘 사이의 거리만 구하면 된다. 여러 쌍의 촌수를 구해야한다면, Floyd-Warshall알고리즘으로 "2차원 배열"에 촌수를 담아 구성할 수 있고, 한 사람에 대하여 다른 여러 사람들과의 촌수를 구해야한다면 "1차원 배열"에 촌수를 담아 구성할 수 있을 것이다. 여기서는 딱 한 쌍에 대해서만 구하면 되므로, dfs혹은 BFS로 풀이가 가능하다. 그래프 문제가 나오면 BFS에 손이 더 많이 갔기에, 이번에는 DFS로 풀이해보았다. 재귀함수를 돌리며,node번호와 함께 촌수( 그냥 cs라고 매개변수 이름을 대충 지었다...)를 보내주며 우리가 ..

Swift알고리즘 2022. 6. 6. 15:29

백트래킹 문제이다. 1. 모음1개 자음2개를 꼭 포함해야한다. 2. 오름차순이어야한다. 위 두가지 조건을 만족하는 문자열을, 주어진 문자들로 조합해 모두 출력하면된다. Array.joinded(separator: "") 로 배열을 문자열로 이어붙여 출력하였다. 위의 2번조건 "오름차순"은 백트래킹에서 "조합"과 동일한 단어라고 받아들이면 된다. "순열"에 오름차순조건을 추가하면 "조합"이 된다!!! dfs함수로 모든 경우를 조합하며, level == l (출력할 문자열의 길이) 이 되었을 때, 모음 1개와 자음2개가 포함되어있는지 체크하는 함수check로 체크 후 print()해주었다.

Swift알고리즘 2022. 6. 3. 21:45

꽤나 까다로운 문제였다.. 일단 문제를 읽어보면, 해당 숫자 이하의 모든 소수(prime number)를 배열에 오름차순으로 모아놓고, 투포인터로 연속된 소수 합이 주어진 숫자 n이 되는 경우를 모두 세주면 된다. 소수 배열을 만드는 것은 "에라토스테네스의 체" 알고리즘을 사용하였는데, 보통 어떤 자연수 n이 prime인지 판별하기 위해서는, 루트n이하의 소수들에 대해서, n을 나누어 떨어지게 할 수 있는지 체크하면된다. 이 경우에는 루트 n이하의 소수들만 배열에 넣어버리면, 연속합을 체크할 수 없다. ex) 23의 경우, 2 3 5 7 11 13 17 19 23의 소수 순열 중, 루트23, 즉 4.~~ 아래의 [ 2, 3 ]만 배열에 넣으면 연속합이 23이 되는 것을 체크할 수 없다. 또한, 주어진 숫..

Swift알고리즘 2022. 6. 3. 20:15

union-find (서로소) 알고리즘과 Kruskal 알고리즘을 사용한 최소스패닝트리 문제이다. Swift는 언제가 값타입이라는 것을 유의해야한다.

Swift알고리즘 2022. 6. 3. 18:35

Floyd-Warshall 알고리즘을 이용해 풀이하였다. 우리가 알고있는 Floyd-Warshall알고리즘은, 모든 node에서 모든 node까지의 최단거리를 구할 수 있는 알고리즘이다. Floyd-Warshall 보통 2차원 배열 (n x n)을 INF로 채워넣은 후, 우리가 알고있는 거리를 배열에 갱신해 넣고, 3중 for문을 돌려 모든 node -> 모든 node 최단거리를 얻어낸다 이 문제에서는, 거리는 우리의 관심 밖이고, a번 node에서 b 번 node로 길이 있는지, b부터 a까지 길이 있는지 여부이다. 따라서 2차원 배열을 0으로 채워넣고, 길이 있는 경우 1로 갱신하도록 알고리즘을 작성하였다. 이렇게 하면 마자막 30번 줄~ 내 앞, 뒤에 몇명이 있는지 셀 때 훨~~ 씬 수월해진다. 기..

Swift알고리즘 2022. 6. 3. 18:09

조금의 판단과 응용이 필요한 이분탐색 문제이다. 먼저 이분탐색을 하는 중, 같은 요소가 여러개인 경우, (배열은 정렬이 되어있다) 맨 왼쪽원소를 찾아주는 Binary Search 함수 1개, 맨 오른쪽 원소를 찾아주는 Binary Search 함수 1개 총 두개의 함수를 구현해준다. 그렇게 check할 모든 숫자에 대하여 맨 왼쪽과 맨오른쪽을 구하고, 갯수를 result문자열에 append해주어 출력해준다. 풀이1) 이분탐색 풀이2) 짧은 풀이

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