본문 바로가기
반응형

전체 글340

[알고리즘] 최단경로(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.
[파이썬&루비] 다중상속(Multiplex Inheritance) 다중상속(Multiplex Inheritance) 기존에 부모 객체로 부터 메소드를 받을 수 있는 것을 상속이라고 하며,여러개의 부모객체로 부터 상속을 받는 것을 다중 상속이라고 한다.객체 지향을 하는 언어들이 모두 다중 상속을 지원 하는 것은 아니며, 대부분은 지원하지 않는다.이유는 죽음의 다이아몬드라는 다중상속의 크나큰 단점때문인데,이 때문인지 몰라도 루비에서는 다중상속을 지원하지 않고 파이썬에서는 지원한다.대신 루비에서는 Mixin이라는 기능을 이용해서 비슷한 목적을 이룰수 있다.따라서 이번에는 파이썬 코드만 보도록 하겠다. 12345678910111213141516171819202122# pythonclass C1(): def c1_m(self): print("c1_m") def m(self): .. 2017. 6. 2.
[파이썬&루비] 객체와 모듈 객체와 모듈 123456789# test.pyimport libobj = lib.A()print(obj.a()) #lib.pyclass A: def a(self): return 'a' cs 이번에는 객체를 모듈화 하는 것에 대해 알아보도록 한다.먼저 클래스에 대한 모듈 파일을 만든다.이렇게 만들어진 모듈 파일을 사용할 파일에서 import 시켜야한다.그리고 나서 모듈 내부의 객체 이름으로 인스턴스를 만들어 준다.결과적으로, 해당 객체 인스턴스가 생성되고, 내부 메소드를 사용할 수 있게된다. 12345678910111213# test.rbrequire_relative 'lib' obj = Lib::A.new()p obj.a() #lib.rbmodule Lib class A def a() return 'a'.. 2017. 6. 2.
[파이썬&루비] 오버라이드(Override) 오버라이드(Override) 오버라이드는 재정의라는 의미를 내포하고 있다.상속이라는 개념에서 상당히 중요한 기능이며, 복잡해진 객체 지향을 좀 더 잘 사용하기 위해 만들진것이다. 오버라이드는 상속 받은 메소드를 재정의 하는 것을 말한다.부모 객체에서 자식 객체로 메소드가 넘어갈 때 이 메소드의 기능을 수정 하기 위해해당 메소드의 코드를 다시 작성하는데 이것이 오버라이드이다. 123456789101112131415161718192021222324# pythonclass C1: def m(self): return 'parent'class C2(C1): def m(self): return super().m() + ' child' passo = C2()print(o.m()) # rubyclass C1 def m.. 2017. 6. 2.
[파이썬&루비] 클래스 멤버(Class Member) 클래스 멤버(Class Member) 1234567# rubyrequire 'date'd1 = Date.new(2000, 1, 1)d2 = Date.new(2010, 1, 1) p d1.year()p d2.year()p Date.today()cs 지금까지 배운 변수와 메소드는 '인스턴스 멤버'였다.이번에 배울 내용은 '클래스'에 소속 되어있는 변수와 메소드이다.그렇다면 인스턴스의 멤버와 클래스멤버의 차이점과,왜 이런 차이점을 가지고 있는지에 대해 생각해보자. 먼저 루비에서 날짜에 대한 기능을 가지고 있는 객체를 살펴보자require 로 date객체를 불러온 후 d1이라는 변수에 Date 객체를 이용해서 인스턴스를 만든다.똑같은 방법으로 d2 변수에도 인스턴스를 만든다. 현재 d1에는 2000년 1월 1일.. 2017. 6. 1.
[파이썬&루비] 상속(Inheritance) 상속(Inheritance) 우선 비유를 통해 상속을 알아보자. 우리가 자전거를 만든다고 했을때, 부품들을 조합해서 만들게된다.이렇게 사용되는 부품을 함수라고 생각해보자. 이렇게 함수라는 부품을 조합해서 자전거라는 객체를 만들었다.그리고 이 자전거를 다른사람에게 팔았는데, 팔린 후 새로운 기능을 달고싶어했다.결국, 자전거에 전조등을 달게 되었는데 기존에 깔끔하게 자전거 기능만 담고있던 자전거에전조등의 기능을 추가하면서 새로운 객체가 되었다. 위의 예 처럼 새로운 기능을 추가해서 새로운 객체를 만드는 것.이것을 상속(Inheritance)이라고한다. 123456789101112131415161718#pythonclass Class1(object): def method1(self): return 'm1' c.. 2017. 6. 1.
반응형

티스토리툴바