다익스트라3 백준 20183번 골목 대장 호석 - 효율성 2 (Python) .. 우당탕탕 시행착오들.. 1. 문제 조건- N개의 교차로와 M개의 골목 (교차로 : 노드 / 골목 : 간선)- 각 간선의 가중치가 그 골목의 요금- 소지한 돈보다 많은 비용이 나오면 그 경로로는 갈 수 없음- 수치심은 경로 상에서 가장 많이 낸 돈의 금액, 최소한의 수치심을 얻어야 함- 수치심을 줄일 수록 많은 돈이 필요하고 수치심이 높을 수록 적은 돈이 필요함 - 입력 - 범위1 1 1 1 1 2. 아이디어 및 시행착오시행착오 1. 다익스트라로 경로를 이동하되, 이동한 경로의 총합으로 최소비용을 계산하는 것이 아니라, max 배열을 두고 max배열을 갱신하면서 다익스트라를 돌리려고 했다. (가지고 있는 돈보다 경로를 지나온 합이 작을 때만 갱신하도록 dist배열도 관리를 하긴 한다.) 특정 노드에 왔을 때, 그 노드까지 .. 2024. 8. 18. (컴퓨터와 네트워크) 네트워크 계층 - 라우터 알고리즘(Link State, Distance Vector) 본 게시물은 이석복 교수님의 네트워크 강의를 수강하며 작성한 강의노트와 추가 공부한 내용을 바탕으로 작성하였습니다.참고 강의 및 사이트KOCW컴퓨터ㆍ통신 >컴퓨터공학 강의학기 2015년 2학기 수강 확인증 발급 안내 수강" data-og-host="www.kocw.net" data-og-source-url="http://www.kocw.net/home/enrolment/enrolmentInfo.do?cid=6166c077e545b736" data-og-url="http://www.kocw.net/home/enrolment/enrolmentInfo.do?cid=6166c077e545b736" data-og-image=""> KOCW한양대학교 이석복 강의 내용 및 목표 인터넷을 동작시키는 컴퓨터네트워크 프로.. 2024. 2. 25. (알고리즘) 다익스트라 (JAVA , for문 활용 & PriorityQueue 활용 방식 비교) 1) 개념 한 정점(노드)에서 다른 정점(노드)까지의 최단 경로를 구하는 알고리즘 도착 정점 뿐만 아니라 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있음 탐욕기법을 사용한 알고리즘으로 MST 프림 알고리즘과 유사 2) 알고리즘 단계 D : 거리 계산을 위한 배열 U : 경로 배열 출발 노드(a)를 선택 후 a와 연결된 정점들에 대해 배열(D) 값을 가중치로 업데이트한다. >> 다른 정점들은 아직 도달할 수 없는 정점이므로 배열 값 무한대인 상태(배열 초기값을 무한대로 설정해두기)이다. D배열 중 거리가 가장 작으면서 U에 없는 정점(b) 선택한다. a에서 b를 경유해서 갈 수 있는 정점 후보를 보고 그 때 가중치 값을 D에 UPDATE(D[b] +a[b][c])하고 D에 .. 2023. 7. 5. 이전 1 다음
