Algorithm/LeetCode14 [LeetCode] 778. Swim in Rising Water (Swift, Python) Swim in Rising Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 우선수위 큐를 활용한 bfs로 해결할 수 있는 문제이다. [0][0]에서 시작해서 [n-1][n-1]로 갈 때까지의 최소 시간을 구해야 한다. 큐에 담을 때 time 값을 해당 좌표의 grid 값을 담아두는데 큐에서 값을 꺼낼 때 time 값이 가장 작은 것을 가져와야 하므로 우선순위 큐를 활용한다. 큐에 있는 값들 중 가장 작은 time을 가진 원소를 꺼내면서 res의.. 2021. 11. 30. [LeetCode] 841. Keys and Rooms (Swift, Python) Keys and Rooms - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 0번 방부터 탐색하는 dfs를 사용하면 된다. visited 배열을 만들어서 n번 방에 들어갈 수 있는지를 체크한다. 각 방에 들어갈 때마다 방에 있는 열쇠들을 for문을 통해서 아직 방문하지 않은 방의 열쇠일 경우 dfs 함수를 재귀적으로 호출해서 visited 여부를 바꿔준다. 코드 [Swift] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .. 2021. 11. 29. [LeetCode] 64. Minimum Path Sum (Swift, Python) Minimum Path Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 (0, 0)에서 출발하여 (m-1, n-1)까지 갈 때 grid에 적혀 있는 숫자의 합이 최솟값이 되는 경우를 찾는 문제. 간단하게 bfs를 사용해서 문제를 풀었는데 다른 사람들의 속도를 보니 dp를 활용하여 문제를 해결할 수 있는 것 같다. 추후에 dp에 대해서 공부할 때 다시 한 번 풀어봐야겠다. 코드 [Swift] 1 2 3 4 5 6 7 8 9 10 11 12 13 14.. 2021. 11. 16. [LeetCode] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (swift, python) Find the City With the Smallest Number of Neighbors at a Threshold Distance - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 각 도시에서 distanceThreshold 이하의 거리를 갖고 있는 도시의 개수를 카운트 해야 한다. 즉, '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 해당한다. 그렇기 때문에 최단 경로 알고리즘에서 플로이드 워셜 알고리즘을 사용해서 풀 수.. 2021. 11. 12. [LeetCode] 743. Network Delay Time (swift, python) Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 다익스트라 알고리즘을 활용해서 풀 수 있는 문제. 시작점 k에서 모든 노드까지의 최단거리를 구해준다. distance 배열에 k에서 각 노드 까지의 최단거리가 구해진다. 문제에서 모든 노드에 신호를 보내기까지 걸리는 시간을 구하라 했으므로 distance 배열에서 가장 큰 값(걸리는 시간이 가장 큰 경우)이 문제의 답이 된다. 만약 k에서 시작해서 도달할 수 없는 노드가 있.. 2021. 11. 3. [LeetCode] 207. Course Schedule (swift, python) Course Schedule - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 위상정렬을 활용해서 해결할 수 있는 문제. 각각의 강의마다 선수 강의의 수를 저장하는 indegree 배열과 해당 강의를 듣고 나서 들을수 있는 후속 강의들을 저장하는 graph 배열을 만들어준다. 예제와 같이 [[1, 0]]과 같이 주어질 경우 각각의 배열에는 다음과 같이 저장된다. [0] : [1] → 0번 강의를 들어야 1번 강의를 들을 수 있다. [1] : [] → 1번 .. 2021. 10. 15. 이전 1 2 3 다음
