728x90 그래프2 자료구조 과제 투캅스 저희 교수님은 알고리즘으로 저명하신 분이셔서 자료구조와 알고리즘 수업의 끝판왕이라고 불리십니다. 핵심은 과제의 수와 비율인데요. 한 학기에 약 20개 정도로 쏟아지는 과제를 감당해야합니다. 이번 과제는 투캅스라는 과제로 그래프의 꼭짓점이 주어지고 그래프를 따라 항상 1씩 이동하는 두 로봇의 최종 위치를 결정하는 거였습니다. 로봇은 처음에 마주 보는 방향으로 움직이고 부딪힐 경우 반대 방향으로 이동합니다. 어려웠던 점은 홀수 거리, 짝수 거리가 남았을때의 처리 방법이었는데요. 제가 과제를 잘 이해하지 못해서 헤맸던 거 같습니다. 처리 방식은 다음과 같습니다. 이 부분은 이해하기 쉬웠습니다. 제가 헷갈렸던 점은 이부분인데요. 교수님이 말씀해주시길 로봇은 항상 '1' 만큼 이동하기 때문에 0.5초사이에 0.5.. 2020. 9. 20. 크루스칼 알고리즘(Kruskal algorithm) 크루스칼 알고리즘에 대해 배워보겠습니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그니깐 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 실제로 여러 개의 도시 연결을 위해 도로 건설 최소 비용을 위해 적용되는 알고리즘 입니다. 그래프 용어를 정리해 보겠습니다. 노드 = 정점 = node = 도시 : 그래프에서 동그라미 간선 = 거리 = edge = 비용 : 그래프에서 선 이 그림의 노드 개수는 7개이고 간선의 개수는 11개입니다. 즉 7개의 도시, 11개의 도로인거죠. 크루스칼 알고리즘의 핵심은 다음과 같습니다. 정렬 후 비용이 작은 ( 거리가 짧은) 순서대로 그래프에 포함시키자. 모든 노드를 최소 비용 연결시키는 게 목적이니 모든 노드를 오.. 2020. 6. 4. 이전 1 다음 728x90
