앱등개발자IOS

어떻게 풀어야할까 그 알고리즘을 생각하는데 꽤 오래걸린 문제이다. 다익스트라? Floyd-Warshall? 모두 가능해보였다. 결국 플로이드 워셜 알고리즘으로 풀이를 했지만, 메모리가 128MB이기 떄문에 메모리 초과가 뜨고 말았다. 풀이를 검색해보니, 다익스트라 혹은 이분탐색 + BFS 형태 , 즉 Parametric Search형태의 문제였다. 아래는 이분탐색 + BFS 방식으로 풀이한 코드이다. 이분탐색 방식으로 우리가 옮길 짐의 무게를 차례로 탐색한다. => 그떄그떄의 무게를 bfs함수에 전달하여, 해당 무게의 짐을 옮길때 다리를 건너 도착지까지 갈 수 있는지를 Bool 형태로 return해준다.

Swift알고리즘 2022. 9. 4. 20:12

투포인터의 시간복잡도는 어떻게 될까. 생각해보니 투포인터의 시간복잡도에 대해서 크게 생각해본 적이 없는 것 같았다. 이 문제를 처음 접하고 완전탐색으로 풀이했고, 당연히 시간초과가 떴다. 투포인터는 주어진 배열이 정렬되어있을 때, 정렬되지 않았을 때 모두 사용하는 경우가 있다. 여기서는 시간복잡도를 최소화하기 위해,그리고 문제 특성상 두 포인터를 양 끝에 두고 가운데로 좁혀들어와야한다. 예를 들어 -99 -97 -50 -15 14 51 103 과 같이 배열이 주어져있고, 합이 0에 가까워지는 쌍을 찾는다고 생각해보자. 이때 0,1번 인덱스에 start,와 end 포인터를 두고 탐색한다면, 우리는 end가 103에 도착해 (-99, 103)쌍을 처음이자 마지막으로 얻게 될 것이다. 하지만 양 끝에서 출발할..

Swift알고리즘 2022. 9. 4. 16:15

이 문제는 2차원 탐색문제이다. bfs로 간단하게 풀 수 있는 문제인데, 총 두가지 방법으로 풀어보았다. 1. 2차원 배열을 Bool형태로 만들어, 입력되는 직사각형에 해당하는 칸들을 true로 갱신 2. 2차원 배열을 Int형태로 만들어, 입력이 매우 많은 경우를 대비하여 누적합 방식으로 직사각형 영역을 갱신 배열의 가로, 세로, 직사각형 갯수가 모두 100 이하로 설정되어있어, 누적합을 사용해도 시간을 줄어드는 것을 확인할 수는 없었다. 먼저 1번. Bool타입의 2차원 배열을 사용한 방식이다. 직사각형의 대각선 양 끝 두개의 꼭짓점이 들어올 때마다, 17~19번 줄과 같이 2중 for문을 통해, 직사각형에 해당하는 칸들을 true로 갱신해준다. 이는 입력이 이 문제처럼 작은 경우에는 괜찮지만, 입력..

카테고리 없음 2022. 8. 28. 18:09

4중 for문으로는 시간제한을 절대 통과할 수 없다. Dictionary 자료형의 해시 기능을 활용하여 시간을 통과해보았다.

Swift알고리즘 2022. 8. 27. 23:48

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

0번 인덱스를 1번 인덱스에 더하고, 0+1번 인덱스를 2번 인덱스에 더하고, 0+1+2번 인덱스를 3번 인덱스에 더하고.... 를 반복하여 누적합 배열을 만들어놓은 뒤, a b와 같은 인풋, 즉 a번째 idx부터 b번째 idx까지의 합을 구해야할 때, arr[b - 1] - arr[a -2]로 뺄셈 한번으로 답을 도출해낼 수 있다.

카테고리 없음 2022. 8. 22. 16:23

문제풀이 Point : 1. Point 타입은( h, x, y, 익게되는 날 )로 총 4개의 Int로 이루어진 튜플이다. 2. 초기 0의 수를 세 zeros에 저장해두고, 초기 익은 토마토의 좌표를 tomato에 저장해둔다.

카테고리 없음 2022. 8. 22. 15:41

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

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