반응형 2017/06100 [알고리즘] 최소비용신장트리(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. [파이썬&루비] 다중상속(Multiplex Inheritance) 다중상속(Multiplex Inheritance) 기존에 부모 객체로 부터 메소드를 받을 수 있는 것을 상속이라고 하며,여러개의 부모객체로 부터 상속을 받는 것을 다중 상속이라고 한다.객체 지향을 하는 언어들이 모두 다중 상속을 지원 하는 것은 아니며, 대부분은 지원하지 않는다.이유는 죽음의 다이아몬드라는 다중상속의 크나큰 단점때문인데,이 때문인지 몰라도 루비에서는 다중상속을 지원하지 않고 파이썬에서는 지원한다.대신 루비에서는 Mixin이라는 기능을 이용해서 비슷한 목적을 이룰수 있다.따라서 이번에는 파이썬 코드만 보도록 하겠다. 12345678910111213141516171819202122# pythonclass C1(): def c1_m(self): print("c1_m") def m(self): .. 2017. 6. 2. 이전 1 ··· 20 21 22 23 24 25 다음 반응형
