앱등개발자IOS

특별한 알고리즘이 아닌 "아이디어"와 "구현 능력"이 필요한 스타일의 문제인 것 같다. 첫 번째 코드는 몇 달 전 풀이했던 코드인데, 마이너스가 처음 등장하기 전까지의 모든 숫자들을 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

정수 n이 주어졌을 때, 이를 1,2,3의 합으로 나타내는 경우의 수를 알아내야하는 문제이다. dp로 접근하여 간단하게 풀 수 있는 문제이다. 특히나, 11보다 작은 n만 주어진다고 하였으니, dp의 길이를 11 ( 0번 인덱스 ~ 10번 인덱스)로 잡으면 될 것이다. 먼저 n으로 1,2,3이 주어졌을 때의 경우의 수를 작성해놓고, dp를 위한 반복문을 시작한다. dp는 항상 이전의 정보들을 사용한다. 그 과정에 겹치는 것이 없도록 자신만의 기준을 세우는 것이 중요하다. dp[4]는 어떻게 구할까? #dp[1]의 경우에서 출발해보자. (n)이라는 것은 n길이를 만들 수 있는 모든 경우의 수, 어떤 경우든 상관 없이 모두 적용된다는 뜻이다. 먼저 dp[1]이니 (1)은 만들어져있을 것이다. 우리는 3을 더..

Swift알고리즘 2022. 5. 24. 19:24

시작점으로부터 모든 지점까지의 "최단거리"를 구해야하는 "다익스트라" !!! 가 아닌 "벨만-포드" 알고리즘을 사용하는 기본 문제입니다... 그 이유는 간선에 "음수"가 포함되어있기 때문인데요, 코테에 나오는 알고리즘을 암기하면서 벨만포드는 참 외우기 어려웠습니다.. ( 이유는 잘 모르겠네요.. ) - 자세히 보면 INF를 이용해 1차원 distance배열을 두고 시작하는 것, - 함수의 첫 줄에서 시작점의 distance[start] = 0으로 초기화하는 것 이 두가지는 다익스트라를 구현할 때와 완전히 똑같습니다! 한가지 큰 차이점은 -다익스트라는 보통 "인접 리스트"에 각 node에서 갈 수 있는 node번호를 모아놓는 , "그래프"가 주인공인 알고리즘 이라면, - 벨만-포드는 아래 코드의 7번 줄과..

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