반응형 2017/06/027 [알고리즘] 최단경로(Shortest Path Problem) - 1 최단경로(Shortest Path Problem) - 1 이번시간에는 그래프 알고리즘 중에서 가장중요하고 유명한 최단 경로에 대해 알아보자최단 경로는 이름 그대로 가장 짧은 경로를 찾는 것이다.먼저 최단경로 문제에서는 가중치를 가진 그래프가 주어진다.사실 최단 경로에서는 방향/무방향이 무의미하다. 따라서 방향 그래프를 예시로 설명을 진행한다. 경로의 길이를 정의해야하는데, 길이는 그 경로상에 있는 모든 가중치들의 합이다.따라서 최단 경로는 U에서 V로가는 가장 짧은 길이를 말한다.그러므로 이렇게 U에서 V까지의 최단 경로를 ∂(U,V)라고 정의한다.최단 경로 문제의 목적은 ∂(U,V)를 구하는 것이다. 최단 경로의 문제의 유형에 따라 구분을 할수 있다.먼저 하나의 출발 노드로부터 모든 노드의 최단 경로를.. 2017. 6. 2. [알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 4 최소비용신장트리(Minimum Spanning Tree) - 4 이번에는 두번째 MST인 프림의 알고리즘에 대해 알아보자프림의 알고리즘도 마찬가지로 안전한 엣지를 하나씩 추가함으로 완성되는데안전한 엣지를 찾는 방법이 크루스칼의 알고리즘과 다르다. 프림의 알고리즘에서는 먼저 출발점인 노드를 선택해야한다.그리고 그 출발점인 노드에서부터 점점 몸집을 키우기 시작한다.즉, 출발 노드에서 인접한 노드를 선택하고, 여기서 나가는 엣지를 하나 선택하고, 이를 반복한다.크루스칼에서는 떨어진 노드들을 선택했는데 프림의 알고리즘은 인접한 노드를 선택하는것이 차이점이다. 이 때, 어떤 엣지를 선택하느냐에 대한 방법을 알아봐야하는데,매 단계에서 트리에 포함되어진 노드와 포함되지 않은 노드 사이에 가중치가 가장 작은 엣지를 선.. 2017. 6. 2. [알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 3 최소비용신장트리(Minimum Spanning Tree) - 3 저번 시간에 이어 크루스칼의 알고리즘을 계속 진행한다.크루스칼의 알고리즘을 위해서는 원소 u가 속해있는 집합이 무엇인지 찾을수 있어야하고(Find) 2개의 집합을 하나로 합치는 연산(Union)을 지원해야한다. 이를 Union Find Problem이라고 한다. 결론을 이야기하면 Union Find Problem을 해결하기 위해, 각각의 집합을 하나의 트리로 표현해야한다.이 때, 이러한 트리에 규칙이 없다. 이진 트리도 아니고 자식이나 부모에 대한 규제도 없다.대신 해당 집합의 모든 원소들이 트리의 노드로 들어가야한다는 것이다. 또한 일반 트리가 밑으로 내려가는 것과 달리, 여기서는 루트 노드까지 올라가는 연산, 즉 상향식 트리이다.이것의 .. 2017. 6. 2. [파이썬&루비] 믹스인(Mixin) 믹스인(Mixin) 앞서 파이썬에서 다중 상속에 대해 살펴보았다.다중 상속에서 루비에 대해 다루지 않은 이유는 루비는 다중상속을 지원하지 않기때문이다.대신 믹스인이라는 세련된 방법을 사용한다. 믹스인이라는 것은 객체와 모듈의 관계이다. 1234567891011121314151617# rubymodule M1 def m1_m p "m1_m" endendmodule M2 def m2_m p "m2_m" endendclass C include M1, M2 endc = C.new()c.m1_m()c.m2_m()cs 위의 코드를 찬찬히 읽어보면 단번에 어떤 부분이 믹스인인지 알수 있을 것이다. 바로 include라는 부분이다.먼저 모듈 M1과 M2가 선언되며, 클래스 C가 이 모듈들을 include한다.모든 과정.. 2017. 6. 2. 이전 1 2 다음 반응형
