잊기싫어 메모장 잊기싫어 메모장

https://leetcode.com/problems/path-with-maximum-probability/submissions/ Path with Maximum Probability - 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 로직 설명: (다른 문제에서 설명함) 접근방법 시작점에서 각node로 갈 최고 확률을 나타내는 dist 다음에 탐색 할 정보를 담고있는 queue 각 노드가 연결된 정보를 나타내는 adjList 위 내용들을 주어진 매개변수로 초기화..

https://programmers.co.kr/learn/courses/30/lessons/49189 일단, 틀렸다. 듣기로는 BFS일 때, 잘 풀리는 문제라고 한다. 실제로 간선 간 거리가 1로 지정되어 있기 때문인듯. 하지만 더 풀어보지 않는 이유는 dijkstra는 제대로 구현되었다고 생각했기때문! 마지막 3개의 testCase가 dijkstra의 반례인듯. 코드 더보기 class programmers_다익스트라_가장먼노드 { var map : [[Int]] = .init() var minimumLength: [Int] = .init() // (node, length) var queue : [(Int,Int)] = .init() { didSet { queue.sort() { $0.1 < $1.1 }..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 접근 방법 모든 node 사이의 최소 요금 정보가 필요. >>> 플로이드 알고리즘 ..

https://programmers.co.kr/learn/courses/30/lessons/12978 접근 방법 1번 마을에서 2...N번 마을까지, 갈 수 있는지 여부를 재귀를 사용하여 확인한다. -> 1차 코드 반복적으로 탐색하는 경로가 생기므로 효율이 떨어짐을 인식. 1번 마을에서 k 이하까지, 탐색 가능한 모든 경로를 탐색하여, 방문한 마을을 기록한다. -> 2차 코드. 아무리 용을써도 해결 할 수 없는 반례가 있었다.... Dijkstra 알고리즘 사용... 아래는 코드의 실행순서에 따른 설명이다. 매개변수 road를 사용하여 2차원 배열 map을 그린다. 이 떄, i행, j열의 원소 : i번 마을에서 j번 마을로 이동시간. 간선이 없는 경우는 -1로 둔다. 1번 마을에서 출발한다. var di..