앱등개발자IOS

Greedy 알고리즘 문제이다. 핵심은 rope배열에 오름차순으로 정렬을 하고, 맨 왼쪽에서부터 조회를 해나가면, 조회된 로프가 버틸 수 있는 하중이 해당 상황에서의 "최대 하중"이 되므로, "최대 하중" * 남은 로프 수 ( 남은 로프 수는 n -> n-1 -> n-2...... 1) 위와 같이 진행하며 모든 경우에서 최대치를 구해 return해준다.

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

지난 주 Swift로만 응시해야하는 코딩 인터뷰를 준비하며 한참 Swift로 알고리즘 풀이를 하면서.. Dijkstra를 제외하고는 알고있는 모든 알고리즘에 대하여 Swift로 풀이를 해보고 (Heapq를 지원해주지 않는 Swift...) 어느정도 Swift 알고리즘 풀이도 python으로 풀이하는 것만큼 실력이 올라왔다고 느꼈지만, 며칠 놓아버리니 금방 이것저것 다 잊어버린 것 같다... 이 문제는 기본 Greedy문제인데, python으로 요 며칠 풀이하다 돌아오니, 변수명 앞에 var, let 붙여주는 것이 또 어색하게만 느껴졌다. 배열에 잔돈 단위를 큰 순서로 담아두고, 차례대로 몫을 취해 result에 더하고, 나머지만을 n에 남기는 방식으로 진행했다.

Swift알고리즘 2022. 6. 1. 22:59

특별한 알고리즘이 아닌 "아이디어"와 "구현 능력"이 필요한 스타일의 문제인 것 같다. 첫 번째 코드는 몇 달 전 풀이했던 코드인데, 마이너스가 처음 등장하기 전까지의 모든 숫자들을 result에 더해주고, 마이너스가 등장하고부터는 모든 숫자들을 빼주는 것을 정말 있는 그대로 구현했다. 아래의 코드는 문자열을 먼저 "-"를 기준으로 split하여 String들의 배열로 바꾸어주고, 그렇게 나뉘어진 String들의 배열을 다시 "+"를 기준으로 나누어주는 방식으로 구현하였다. 확실히 카카오 기출문제들을 많이 접하다보니 새로운 아이디어들을 생각해낼 수 있게 된 것 같다.

Swift알고리즘 2022. 5. 25. 18:43

같은 길이의 두 배열이 주어지면, 하나의 배열만 정렬하여 아래 수식의 값을 가장 작게 만들어야하는 문제이다. a배열을 오름차순으로 정렬해둔 후, b배열에서 최댓값을 하나씩 꺼내 a의 가장 작은값과 곱하여 result에 더해주고, 방금 b에서 꺼냈던 최댓값을 b배열에서 제거하는 방식으로 진행하였다.

Swift알고리즘 2022. 5. 25. 18:14

그리디 알고리즘으로 풀 수 있는 매우 간단한 문제이다. 배열을 정렬할 줄 안다면 큰 무리 없이 풀이할 수 있을 것이다.

Swift알고리즘 2022. 5. 25. 18:04

모든 경우를 탐색해야하는 백트래킹 문제이다. python이었다면 dfs()함수를 구현하는 방법 외에도, from itertools import permutations 라는 아주 간편한 친구가 있긴하지만, 우리는 코딩을 좋아(?)하니까 직접 구현을 하면서 공부해보자..^^ 코딩 인터뷰 준비를 하면서 느낀 점이, 알고리즘 풀이는 고등학교 시절 수학 공부와 매우 닮아있는 것 같다. 일단 기본 개념 ( = 알고리즘 원리 + 구현 )만 정확히 알고있으면, 그 형태에서 조그마한 변경을 주어 관련 문제들을 풀어낼 수 있다. 이번 2022 KAKAO 인턴 코딩테스트에서도, 이런저런 알고리즘을 머리와 손에 익혀둔 것을 바탕으로 문제에 맞게 적용하여 풀이한 기억이 있다. 이 문제를 풀면서도, 이전에 포스팅했던 N과 M(1..

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

토마토 시리즈 중 3차원의 토마토 문제이다. 기존의 전형적인 2차원 배열에서 앞,뒤,좌,우를 체크하는 bfs와 동일한 알고리즘을 3차원으로 확장시켜 탐색하는 문제이다. 즉, 앞,뒤,좌,우,상,하 총 6방향을 체크하면 된다. 문제의 포인트 두가지는, - 1. 초기 토마토 모아놓고 시작하기 3차원 배열을 탐색하다가 "익은 토마토" (1)을 만났을 때, 더이상 뻗어나갈 수 없을 때까지 쭉 탐색을 하게되면, a,b토마토가 5일 씩 전파하여 끝날 것을 a토마토 하나만 전파하여 10일이 걸리도록 탐색하는 경우가 생길 수 있으므로, 초기에 전체 배열을 한 번 탐색하여 토마토의 위치를 (queue로 사용할) Array에 모아놓은 후, 하나씩 pop하며 bfs를 진행하면 된다. -2. 초기 토마토 모아놓으며, 배열내 0..

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

어떤 알고리즘을 적용해서 풀이할지 바로 떠오르지 않았던 문제이다. 처음에는 DP를 사용해야하는 것인지 고민했었다. 그렇게 DP로 구현하는 과정을 머리로 떠올려보니, 5에서 출발하여 17까지 ( +1, -1, *2 ) 이 세가지 연산을 적용해가며 도달하는 과정을 떠올려보니 이들 모두를 계속 Check할 boundary에 담아두고 계속 위의 세가지의 연산을 적용해 뻗어나가야했고, 그렇다면 DP가 아닌 queue를 이용한 bfs로 접근하는 것이 좋겠다고 판단했다. 방문했던 숫자는 또 방문할 필요가 없으므로 visited 배열을 선언하여 체크해주었다.

Swift알고리즘 2022. 5. 25. 16:00