앱등개발자IOS

기본적인 BFS를 구현하여 해결하는 2차원 배열 탐색 문제이다. 특별히 다른점은 없으나, 가로, 세로로 인접한 칸만을 탐색하는 것이 아닌, 대각선까지 탐색한다는 것이 특징이다. * visited배열로 기 탐색여부를 체크하지 않고, 탐색해야하는 2차원 배열을 inout형태로 &를 사용해 매개변수로 전달하여 직접 수정하며 체크하였다.

카테고리 없음 2022. 8. 22. 00:53

bfs와 dfs를 종합적으로 사용해야하는 문제였다. 꽤나 어렵고 오래 걸리는 문제였다. 순한맛 삼성전자 코딩테스트 문제라고 할 수 있을 것 같다. 1. dfs(백트래킹) 형태로 2차원 배열을 순차 탐색하며 3개의 벽을 순열 형태로 세워, 3개의 벽이 세워질 때마다 해당 2차원 배열의 주소를 매개변수로 넘겨줍니다. ( 3개의 벽이 세워졌는지의 여부는 level이라는 매개변수로 check합니다) 2. 그렇게 dfs에서 3개의 벽이 세워질 때마다 bfs()함수가 호출되고, 그 때의 2차원 배열에서 VIRUS 전파를 실행하고, 안전영역의 수를 return해준다. 각 이미지 아랫쪽에 문제풀이의 핵심 아이디어를 작성해보았다. Point 1. virus의 위치를 미리 담아놓는다. -> 우리는 아랫쪽에서 백트래킹을 통..

Swift알고리즘 2022. 8. 20. 20:57

전형적인 투포인터 기본 문제

Swift알고리즘 2022. 8. 20. 02:29

1. Int배열 받기 readLine()!.split(separator: " ").map{Int(String($0))!} 2. String으로 입력 받기 readLine()!.split(separator: " ").map{String($0)} 3. Character로 입력받기 readLine()!.split(separator: " ").map{Character(String($0))} -> 꼭 String으로 변환 후 Character로 변환해야한다. ( Substring상태에서는 Character로 변환 불가 )

Swift for Coding Interview 2022. 8. 19. 16:52

총 두가지의 경우로 탐색을 해야하는 문제이다. 1. 색약이 아닌경우 2. 색약인 경우 Swift로 풀이할 때는, 2차원 좌표를 Point라는 별칭 type으로 관리한다. typealias Point = (Int, Int) visited배열을 두고, 2중 for문을 돌리며 visited가 false인 칸을 만날 때마다 bfs(_ start: Point)를 호출한다. 이때, 색약이 아닌경우는 arr[start.0][start.1] == arr[now_x][now_y]로 비교하면 되지만, 색약인 경우는 R과 G를 같은 색으로 봐야한다. 2차원 배열 전체를 돌며 R을 G로/ 혹은 G를 R로 바꾸어 똑같이 탐색하는 방법도 있지만, 그보다는 ["R": 0, "G": 0, "B": 1]과 같은 Dictionary를 ..

Swift알고리즘 2022. 8. 19. 16:09

전형적인 이분탐색 문제에서 한 단계를 더 거치도록 만들어진 문제이다. 잘라낼 랜선의 길이를 이분탐색하며 해당 값을 get_lan()함수에 넣어 출력된 값이 문제에 주어진 조건을 만족하는지 기록하며 풀이해나가야한다. Parametric Search라고 할 수 있을 것 같다. 위처럼 python으로 어렵지 않게 해결했지만, Swift로 풀이하면서는 알 수 없는 이유로 계속 틀렸다.. 두가지 이유가 있었다. 1. 틀렸습니다. 를 유발한 원인 2. 런타임 에러 를 유발한 원인 1.17번 줄 ( 이분탐색의 end 포인터 시작점 ) 이 부분을 처음에는 data.min()!으로 작성하였었다. 그러면 안되는 예시는 아래와 같다. 극단적인 예를 들어, 3 3 / 200 / 100 / 1 이 입력으로 주어졌을 때, 답은 ..

Swift알고리즘 2022. 8. 17. 14:10

Swift알고리즘 2022. 8. 15. 13:27

알고리즘 문제를 풀다보면 남들은 쉽게 푸는문제가 이상하게 안 풀릴 때가 있다. 이 문제가 나에게는 그런 문제였던 것 같다. 몇달 전 아래처럼 시간초과를 해결하지 못하고 포기했던 문제가 "실패"라고 떠있는 것을 보고 다시 풀어보았는데, 간단히 풀이할 수 있었다. 알고리즘 문제는 다시 풀 때마다 새로운 방식으로 풀게 되는 것 같아 신기할 따름이다.. 코드는 아래와 같다 1. 주어진 숫자 배열을 오름차순으로 정렬하고, 2. start, end 두 개의 포인터를 양 끝에서 좁혀가며 탐색하는 방식이다. 끝..

Swift알고리즘 2022. 8. 15. 02:23