동치관계(Equivalence Relation) - DFS(Stack) & LinkedList,List

Matrix의 0을 없애는 방법

Matrix에서 쓸데없는 0들을 없애고 필요한 값만 넣으면 시간을 O(n)으로 줄 일 수 있습니다. 그러면 Marker에서 O(n) Stack에서 O(n) Matrix(이 경우 Linked List or list)에서 O(n)으로 총 O(n)시간으로 줄게됩니다.

 

Linked List

먼저 링크드리스트를 이용하려고 합니다. 동치관계를 위해서는 Insert기능만 필요하므로 Insert만 구현하고 링크드리스트의 자세한 내용은 다음에 포스팅 하겠습니다.

 

 

Linked List를 사용 할 때는 Matrix를 기억하는 변수 대신 Node를 기억하는 변수를 사용하면 됩니다.

 

List

학교에서 수업을 들을 때는 C++의 벡터를 이용했지만 Python에서는 기본 자료형인 list를 이용하면 간단하게 구현 할 수 있습니다.