앱등개발자IOS

typealias Point를 3개의 Int를 가진 튜플 형태로 만들어 (x좌표, y좌표, 벽을 부순적 있는지 여부 0/1 ) 를 나타내도록 하였다. 어떤 칸 a, b에 1. 10개의 칸을 지나며 벽을 1번 부수고 도착한 경우 2. 20개의 칸을 지나며 벽을 0번 부수고 도착한 경우 두가지 경우가 있다고 생각해보자 bfs로 진행하므로, 1번 경우를 우리는 queue에서 먼저 꺼내게 될 것이다. 우리가 visited라는 2차원 배열에 각 칸을 지난적 있는지 여부를 표시해왔다고 가정해보자. 2번 경우를 뽑았을 때, 이미 visited[a][b] == true 로 표시되어있을 것이다. --> 그렇다면 우리는 2번 경우를 무시해도 되는 것일까? 절대 안된다. a,b 칸에서 벽을 하나 더 뚫을 경우 10번만에 도..

Swift알고리즘 2022. 8. 23. 16:08

아래와 같이 각 알파벳의 아스키 코드를 사용하여 visited를 체크하여 백트래킹을 진행, level 매개변수로 최대 길이를 알아내는 알고리즘을 실행하는 경우 시간초과 판정을 받았다. 아래와 같이 Set을 사용하여 visited를 체크해도 시간초과가 되는 것은 같았다.. 수많은 시도 후, 결국 비트마스킹으로 지나간 알파벳을 체크하니 시간초과를 피할 수 있었다.

Swift알고리즘 2022. 8. 22. 02:10

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. 색약이 아닌경우 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