앱등개발자IOS

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

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

BFS문제중에서는 신박한 문제였던 것 같다. 뿐만 아니라, DFS, BFS 또는 union-find 알고리즘으로 각 노드의 parent를 체크하고, Set()자료형을 이용해 마무리할 수도 있는 문제이다. 출제자 의도대로 BFS로 풀이해보았다. 각 노드를 모두 나타낼 수 있도록 n+1크기만큼의 visited배열을 만들어놓은 후, 30 번째 줄부터, 1번 ~ n번 노드를 모두 돌며, 1. visited여부가 false인 노드가 나타나면, 2. 해당 노드의 visited = true로 설정해주고 3. 해당 node를 출발 node로 하여 bfs함수를 호출하여, 연결된 모든 node의 visited를 true로 바꿔준다 4. 이렇게 반복문에서 visited가 false인 node를 만날 때마다 count를 1 ..

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

전형적인 DP문제이다. 한가지 포인트는, dp배열이 하나의 원소만을 갖고있는 것이 아니라, [0,0]과 같이 두개의 원소로 초기화되어있는 것. 해당 칸이 i번째 칸이라면, 앞쪽 인덱스는, i-2번 칸에서 i번 칸으로 진행해왔을 때의 최댓값. 뒷쪽 인덱스는, i-1번 칸에서 i번 칸으로 진행해왔을 때의 최댓값이다. 이렇게 나누어 저장한 이유는, "3개의 연속된 계단"을 밟으면 안되기 때문에, 이를 점화식에서 방지해주기 위함이다.

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

# Swift의 for문 -> for i in 0 ... n 과 같이 0~ n까지를 차례로 접근할 수 있고, for i in 0 .. python: for i in range(0, 10, 2)와 같이 stride를 3번째 매개변수로 넣어줌. -> Swift: for i in stride(from:, to:, by: )로 설정해준다. ( by가 음수이면 거꾸로 접근 가능! ) ( to: ~~ 에 입력한 숫자는 포함하지 않는다는 것을 조심!!! ) # Swift의 배열을 문자열로!! arr = ["a","b","c"] 인 경우, -> python: "".join(arr) => "abc" -> Swift는?..

Swift for Coding Interview 2022. 6. 3. 14:42

아직 Swift로 알고리즘 코드를 작성하면 컴파일에러가 뜨는 경우가 적지 않다.... python에 익숙하다보니 여러모로 쉽지 않지만 이제는 Swift로 아예 갈아타야하는게 맞는 것 같다!! 큰 동전부터 작은 동전 순으로 접근하여 남은 금액과 나눗셈을 하여 몫을 취해 count에 더해준 후, 그 나머지를 다시 남은 금액에 할당해준다. 모든 동전에 대해 진행하면, 잔돈 동전의 "최소" 갯수를 구할 수 있다. ==> 이는 동전의 단위가 서로 약수, 배수 관계에 있기 때문이다! 그렇지 않다면 그리디 알고리즘으로 풀이할 수 없다!!

Swift알고리즘 2022. 6. 3. 14:33

지금 i번째 집을 칠할 때 우리는 무엇을 신경써야할까?? 앞, 뒤? 뒷 집을 무슨 색으로 칠할지는 그 때 가서 생각하자! 현재 집을 초록색으로 칠하고싶다면, 그 최솟값은 앞집을 파랑색으로 칠한 경우, 빨간색으로 칠한 경우 이 두가지 경우중 min값을 선택하여 현재 집을 초록색으로 칠할 때 드는 비용에 합쳐 저장한다. 같은 방식으로 두 번 더 진행하면, 현재 집을 앞 집과 색깔이 겹치지 않으면서, 해당 집을 각각 R, G, B로 칠할 때의 최소 비용을 구할 수 있다. 마지막에 result에서 최솟값을 취해줘야 모든 집을 칠하는 최솟값을 구하게 되는데, 배열의 최소, 최대를 .max(), .min()으로 가져올 때는 항상 Optional()타입으로 가져오므로 !로 언래핑을 해줘야한다!

Swift알고리즘 2022. 6. 2. 00:18

Dynamic Programming!! 문제이다. DP는 혼자 있을 때보다 Dijkstra나 DFS, BFS와 같은 친구들과 섞이는 순간 난이도가 확 올라가는 것 같다. 그런 아이들을 풀이하려면 일단 DP만 쓰는 이런 기본 문제들을 잘 풀어야할 것이다! 항상 초기 값들에 대해서는 index out of range오류가 날 것을 생각하여 출력 후 exit(0) 혹은 python에서는 quit() / exit()을 해주어 종료시켜줘야한다. 이후는 점화식을 세워 반복문을 우리가 필요로하는 n까지 돌려주면 된다! python에서는 상관없지만 dp배열에 저장하며 미리미리 10007로 나눠주지 않으면 overflow가 날 수 있으므로 주의하자!

Swift알고리즘 2022. 6. 1. 23:58

이전에 풀이했던 백준 : 거스름 돈 과 동일한 풀이로 해결할 수 있는 Greedy 기본 문제이다. 버튼을 누르면 늘어나는 시간을 배열에 내림차순으로 담아, 몫을 취하고, 나머지 연산을 해주어 n에 갱신해주면 된다.

Swift알고리즘 2022. 6. 1. 23:31