25강 - 다익스트라 알고리즘(Dijkstra Algorithm) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #25 ]

25강 - 다익스트라 알고리즘(Dijkstra Algorithm) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #25 ] 강의 동영상입니다. 이번 시간에는 다익스트라 최단 경로 찾기 알고리즘에 대해 공부하는 시간을 가집니다.

[@dongbinna]

이번 강좌 '다익스트라 알고리즘'의 강의 노트입니다. blog.naver.com/ndb796/221234424646

[@younghoseo1782]

2년째 매번 까먹어서 맨날 이거들으러 옵니다 설명 굳

[@Kevinyo1538]

날고 기는 사람의 4년전 레벨이 이정도니... 매일 정말 열심히 공부해야겠습니다

[@한수빈-i2o]

책봐도 이해가 안갔는데 강의 보니까 이해가 가네요. 쉽게 설명해주셔서 감사합니다. 앞으로도 많이 올려주셨으면 좋겠어요

[@rabe486]

안녕하세요. 강의를 보면서 질문이 있습니다. 영상 22:16분에서 우선순위 큐를 만든 후, 처음에 우선순위 큐에 시작 노드와 그에 따른 가중치 값을 넣는 코드가 없는데, 이것은 상관 없는 것인가요??. 보통 시작 노드 1부터 시작해서 먼저, 우선순위 큐에 (Start, 0)을 우선순위에 넣는 코드가 빠진 것 같아요. 혼란이 옵니다?!

[@hoyun293]

영상이랑 블로그 코드랑 다르네요 블로그가서 보세요 한참 쳐다봤네요 저도

[@이홍준-r6z]

설명진짜잘하시네요 한번에 이해됬습니다!!!

[@타스-g6z]

다익스트라ㅈㄴ어렵네 또봐야겠다

[@navyfielda]

Heap을 사용한 코드의 오류를 발견해서 댓글 남깁니다. STL에서 제공하는 우선순위 큐와 pair를 사용할 때 인덱스값을 second에, 가중치를 first에 넣어야 의도하신 대로 값이 적용됩니다.

[@user-iz5zq4qz3x]

저도 이부분 때문에 헷갈렷네요

[@user-zq7xe5cu4q]

priority_queue 처음 배우는데 검색한 것과 반대로 사용하셔서 정말 애먹었네요 ㅠㅠ

[@alphaOrderly]

혹시 가능하시다면 dijikstra의 start 정점에서 연결된 간선들을 순회하는 부분에서 나오는 for (int i = 0; i < number - 2; i++) 에서 V-2를 썼는지 알려주실수 있으실까요? 제 생각엔 start를 제외한 간선들이기 때문에 1을 빼서 number-1까지 해야한다고 생각해서 일단 여기에 나오는대로 해보고, 값을 바꿔서 한번 더 해봤는데 코드업 기준으로는 둘다 맞다고 나와서 말입니다. 알려주시면 감사하겠습니다. 언제나 잘 보고 있습니다 언제 한번 만날 기회가 생길수 있도록 열심히 노력하겠습니다!

[@user-zq7xe5cu4q]

3년 전 댓글이라 이미 깨달으셨겠지만 저도 궁금했던 부분이라 답글 남깁니다. 처음 시작노드와 마지막 노드에 대해서는 반복문을 순회할 필요가 없기 때문에 빼준 것 같습니당

[@alphaOrderly]

@@user-zq7xe5cu4q 저때는 컴퓨터 전공 지망생이였는데 지금은 전공생이라 잘 아네여 ㄹㅇ ㅋㅋㅋㅋ 감사합니다. 나중에 돌려봐야겠어요

[@midascha1242]

number - 2의 이유에 대해서 고민을 많이 해봤는데, for (int i = 0; i < number - 2 ; i++)의 의미는 노드 첫번째부터 마지막 노드까지 순차적으로 검색해 보겠다는 것이 아니라, 전체 노드중에서 그때 그때 최소 노드가 뭔가를 찾는 것이기 때문에 제 생각에는 start 노드인 1을 나머지 5개가 순간순간 최소값을 가진 노드가 뭔가를 찾는게 맞을거 같은 생각이 됩니다. 그래서 number - 1 이 더 맞을거 같습니다. 혹시 아니라고 생각하시는 분들이 계시면 댓글 부탁드립니다. ^^

[@intremez1981]

저도 고민해봤는데요. 방문한 노드는 이미 최단경로임이 확정되었으니, 마지막으로 남은 노드에서 최단경로를 갱신해주는 경우가 발생하지 않으므로, 굳이 방문해보지 않아도 되고 따라서 처음방문노드와 마지막 방문 노드를 제외하여 number-2 라고 보시면 될것 같습니다.

[@Tak_h]

@@intremez1981 마지막 남은 노드가 최단 경로를 갱신해주는 경우가 없다고 어떻게 알죠?? 영상에서 처음 풀어볼 때 6번까지 다 돌리지 않나요? 잘 이해가 안되네요 ㅠㅠ

[@intremez1981]

​@@Tak_h 이해하시고 나면 그게 모순이라는 걸 아실거에요. 다익스트라 알고리즘을 관찰해 보시면 어떤 노드에서 갱신을 다 해주고 다음 노드를 방문할 때, 남은 노드들 중에서 최소비용을 가지는 노드를 선택합니다. 마지막으로 남은 노드가 마지막인 이유는 그 노드를 방문하기 위한 가중치가 다른 노드들보다 더 크기 때문입니다. 마지막 남은 노드를 L이라고 해보죠. 만약 L에서 또다른 정점 X의 최단경로를 갱신할 수 있다면 (시작점에서 X로 가는 최단경로) = (시작점에서 L까지 가기위한 비용) + (L에서 X로의 비용) 이죠. 하지만 (시작점에서 L까지 가기 위한 비용)은 기존의 (시작점에서 X까지의 비용)보다 이미 큽니다. L을 방문하기 전에 X를 방문했을테니까요. L에서 X로 가는 비용이 음수가 아닌 이상, X로 가는 최단경로의 값은 갱신될 수 없습니다. 하지만 이미 다익스트라 알고리즘을 적용하기 위해서 "양의 가중치를 갖는 간선"들로 구성된 그래프를 전제했으므로, 마지막 남은 노드가 최단경로를 갱신할 수 없습니다. 위에 표현해놓은 식이 글자가 너무 많아서 헷갈리시면 이렇게도 이해하실 수 있어요. X < L 인 두 양수 X, L 에 대해서 X > L + k 인 양수 k는 존재하지 않습니다.

[@donaldlee247]

갓경잡이 시절..🔥🔥🔥

[@lIlIlIlIIll]

노드들 사이 선에 있는 비용값 숫자들은 어떻게 나온건가요?

[@kchlos1007]

저거는 가중치라고 해서 그냥 주어지는거에요! 거리나 비용처럼요

[@태관호-p4k]

안녕하세요 네트워크플로우와 다익스트라 알고리즘 보려고 하는데 동빈나님의 블로그에 직접들어가서 해당 내용을 보면서 시청하고 싶습니다. 혹시 블로그 URL을 남겨주실 수 있으시나요??

[@dongbinna]

방금 댓글로 고정해놓았습니다! blog.naver.com/ndb796/221234424646 입니다.

[@태관호-p4k]

소마에 인프런 강사까지... 필요한 내용이 있으면 자주 찾아보는 편입니다. 좋은 정보와 자료 감사합니다~~

[@김성찬-b4h]

안녕하세요 다익스트라 알고리즘 강의 정말 감사합니다. 강의를 보면서 한가지 궁금한 것이 생겨서 댓글로 질문드립니다.priority queue를 통해서 다익스트라 알고리즘을 구현하는 것에서 priority queue 안에 pair 형태로 데이터를 넣을 때 자동으로 second 값을 기준으로 힙 구조를 이루게 되는 것입니까?

[@dongbinna]

저도 그게 궁금합니다. 지금 보니 직관적으로 first를 기준으로 정렬이 되야 정상인 것 같은데... 이렇게 소스코드를 작성해도 BOJ에서 만점 처리를 받는다는 것이 의아하네요.

[@김성찬-b4h]

그렇군요. 답변 감사합니다!

[@hoyun293]

;;;

[@hoyun293]

설명이랑 개념이 맞지않는 부분이 있었는데.. 여기였군요...

[@hoyun293]

제가 알기로는 pair의 first부분으로 먼저 정렬한뒤 second부분으로 정렬합니다.

[@Joon-m3f]

두번째 for문에서 순회를 number-2까지 하는 이유가 궁금합니다!

[@반도-b6p]

@jy c 마지막은 왜 빼나요?

[@user-st3de6mb2g]

@@반도-b6p 먼가 저기 위의 예에는 마지막꺼를 빼도 상관없지만 만약에 7번노드가 있다고 가정하고 6번노드랑만 연결되어 있으면 잘못되었다고 생각해여!!

[@이혁희-q5e]

저는 number가 어디서 튀어나왔는지 모르겟네요.

[@룰루루룰-n5o]

맨위에 넘버=6으로 초기화핶네요

[@손찬혁-e8n]

인접리스트를 이용한 코드의 시간복잡도가 왜 nlogn이 되는지 설명해주실수 있나요?

[@user-kl6qt5gk6m]

다익스트라 함수의 for문에서 왜 하필 number-2인건가요??

[@HJ-gg3kf]

반복을 하는 횟수가 처음 시작하는 노드와 마지막에 남게 되는 노드는 샐 필요가 없기 때문이라고 생각합니다

[@woojaepaek0318]

인트로 소리가 너무 커요

[@김정원-s5r]

동빈나 님! 다익스트라와 크루스칼랑 쓸수 있는 경우가 다른거요? 최단경로를 찾는것은 똑같은데 정확한 차이는 잘모르겠습니다. 플로이드( 모든 정점에서 모든 정점) 다익스트라 ( 특정 출발점 -> 모든 정점) 크루스칼( 최단 간선 -> 최종 최단 거리 ) 결국 다 최종적으로 짧은 거리를 찾는건데 언제언제 쓰는지 예를 좀 알려주실수 있을까요?

[@dsseo5921]

다익은 한 정점에서 다른 정점으로 이동하는 최단거리를 구하는거고 크루스칼은 사이클없이 모든 노드가 최소비용으로 연결되어 있는 거라 다르다고 볼수있습니다.

[@김정원-s5r]

@@dsseo5921 네? ㅋㅋㅋㅋ2년전 질문에..

[@김정원-s5r]

@@dsseo5921 감사합니다 ㅋㅋㅋ

[@dsseo5921]

아 ㅋㅋㅋ2년전이구낰ㅋㅋㅈㅅ 합니다. 지금은 현직 개발자이시겠네옄ㅋㅋㅋ

[@HeesubShin]

영상은 잘 봤습니다만.... 한국어에서 “값을”, “값이” 라고 쓰여진 것은 [갑슬], [갑시] 라고 발음해야 합니다. 간혹 [가블], [가비] 라고 잘못발음하는 경우가 더러있지만, 세상에 [가플], [가피] 라고 발음하는건 살다살다 첨 보네요. 영상이 올라온지 2년은 훨씬 더 된거 같은데, 아직도 그렇게 발음하고 있나요???

[@dongbinna]

발음 지적 감사합니다!! 앞으로는 유의해서 강의 촬영하겠습니다. 최근 강의에서는 '값을' → [갑쓸]이라고 정확히 발음하고 있습니다!

[@193오]

그런걸로 신경쓰면 어떻게 살고있음?

[@youngseojeon]

ㅋㅋㅋㅋㅋㅋㅋㅋ

[@신하우스]

태클걸게 없어서 이런걸 태클 걸고 있냐 그럼 사투리 쓰는 사람들은 표준어 사용 안하고 발음 다르니까 그 사람들한테도 다 발음 왜 그따구냐 하시지?? 별 시덥잖은걸로 까고 있어 ㅋㅋ

[@youngheechoi4]

정보는no3로간다

[@jong-hoshin5431]

강의 잘 봤습니다. 정말 쉽게 설명하세요. 그런데 '값' 발음이 거슬리네요. 값을[갑슬]이라고 발음해야하는데 계속 '돈을 갚다' 할때 갚을[가플]이라고 발음하니 뭔가 웃겨요ㅎㅎ

[@DDDDOo]

걍봐라

[@vv720]

재밌는게 뭐냐면 까먹었다

[@ryanc7840]

목소리가 너무 느끼해요 일부러 그러시는건가요

[@dongbinna]

(찡긋)

[@ryanc7840]

ㅋㅋㅋㅋ 귀여우셔라 ㅋㅋㅋ

[@빡구-h4w]

@@dongbinna zzzzz

[@이재명은준우승합니다]

이선균 목소리