shortest_path에 대해 질문드립니다.
286
작성한 질문수 11
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
shortest path문제 풀때 다익스트라로 풀거나, 크루스칼로 풀거나 똑같은건가요??
아니면 문제에서 다익스트라로 풀어야 하는지, 크루스칼로 풀어야하는지 힌트가 있나요???
답변 2
0
안녕하세요^^
다익스트라와 크루스칼은 조금 차이가 있습니다.
다익스트라 알고리즘은 그래프의 한 정점에서 다른 모든 정점으로의 최단거리 또는 최소비용을 구하는 알고리즘 이고, 그루스칼은 그래프에서 모든 정점이 연결되어 있는 최소비용의 트리를 찾는 알고리즘입니다.
문제에서 힌트라기 보다는 출발지와 도착지가 주어지고 출발지에서 도착지로 가는 최소비용을 구하라고 하면 다익스트라로 판단하고, 그래프가 주어지고 모든 정점이 연결되기 위한 최소비용을 물어보면 크루스칼을 쓰는 정도로만 알고 있으면 됩니다. 그리고 실제 관련된 많은 문제를 풀어보면서 경험으로 얻는 것도 많습니다.
0
안녕하세요, 인프런 AI 인턴이에요.
shortest path는 가장 짧은 경로를 찾는 문제입니다.
다익스트라 알고리즘과 크루스칼 알고리즘은 모두 shortest path 문제를 해결하는 알고리즘 중 하나입니다.
하지만 다익스트라 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 문제에 특화되어 있고, 크루스칼 알고리즘은 최소 신장 트리를 구하는 문제에 특화되어 있습니다.
따라서 둘 중에 어떤 알고리즘을 사용해야 할지는 문제의 조건에 따라 다릅니다.
문제에서 힌트를 제공하는 경우도 있겠지만, 그렇지 않은 경우는 다양한 알고리즘을 생각해보면서 어떤 알고리즘이 문제를 가장 효율적으로 해결할 수 있는지 생각해보시면 됩니다.
추가적으로, 이전 질문이나 관련 자료를 검색하여 참고하시는 것도 좋은 방법입니다.
자세한 설명은 지식공유자에게 문의해보시면 더욱 상세한 답변을 받을 수 있을 것 같습니다.
좋은 학습 되시길 바랍니다. 감사합니다.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
33
1
갑자기 채점 사이트가 바뀌었어요
0
34
1
문제 리스트 페이지
0
29
1
채점 사이트 관련 질문드립니다
0
24
1
봉우리 문제 질문입니다
0
84
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
65
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
72
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
67
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
85
2
6-7 강의에서
0
48
1
6-6. 장난꾸러기 질문 있습니다.
0
45
1
강의 수강후 코딩테스트
0
111
1
answer 변수 사용 여부
0
46
1
2중 for문
1
85
2
2-11. 임시반장정하기 (Runtime Error)
0
63
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
70
1
이런 풀이는 어떨까요
0
44
1
자바 스트림 방식의 효율성 질문 드립니다.
0
57
1
알고리즘 자료 구조들..
0
63
1
StringBuilder vs BufferdWriter
0
48
1
원더랜드(프림)
0
50
1
이런 코드는 어떤가요?
0
61
1
bfs 풀이
0
57
1
병합정렬
0
57
1