앱등개발자IOS

순열과 조합 4탄! 중복조합 문제입니다. 경우의 수가 중복순열만큼은 아니라서 그런지 매 result마다 print를 해주어도 시간초과는 나지 않네요.. 이전에 어떤 자연수까지 result에 포함되었는지를 begin 파라미터로 전달하여, begin부터 마지막 자연수(n)까지 ( 중복이 가능하니까! ) 다시 for문을 돌리며 다음 자리에 채워나가는 식으로 구현하였습니다.

Swift알고리즘 2022. 5. 24. 18:02

순열과 조합!! 시리즈 중 2번째 문제이다. 이 문제는 조합! 즉 combinations를 구현하면 되는 문제이다. 순열은 1 3 2, 1 2 3 을 다른 것으로 count하지만, 조합은 이 둘 뿐 아니라 1 2 3, 1 3 2, 3 2 1, 3 1 2, 2 1 3, 2 3 1 여섯가지 모두를 같은 것으로 봐야한다. 해결법은 간단하다 "오름차순"으로 뽑기만 하면 이 모든게 "하나"로 count된다! 따라서, data배열의 앞쪽부터 차례로 지나가며, 지나온 곳은 더 result에 넣지 않는 방식으로 오름차순 result만들 만들어 print해주면 된다!

Swift알고리즘 2022. 5. 24. 17:25

위상정렬의 기본 문제! 위상정렬은 기본적으로 deque을 이용한다. First-In-First-Out 파이썬에서는 from collections import deque를 통해 가져온 deque로 append, popleft()를 사용할 수 있었으나, Swift에서는 기본적으로 제공해주는 deque가 없기 때문에, Array에 원소들을 넣으며, 현재 popleft하고( 했다 치고 ..) 맨 아래 바닥에 있는 원소가 누구인지 가리키는 idx 변수를 사용한다. while 문 종료조건은 Array.count > idx가 깨지는 순간이다! Array의 count는 1에서, idx는 0에서 시작하므로, 새로 q에 들어온 원소의 수가 pop 한 원소 수보다 크거나 같으면 while문은 계속 돌아가게 된다!! ( py..

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

서로소를 확인할 수 있는 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

주어진 간선들을 인접리스트 형태로 저장하고, 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