topological sort
-
고대어 사전 / ALGOSPOT / V2 풀이 O(N)ALGOSPOT 2020. 3. 27. 18:06
이전 포스팅에서 그래프를 어떻게 코딩할 것인지? 에 대해서 알아 보았습니다. 이번에는 만든 클래스들(Vertex, DirectedEdge)을 가지고 문제를 풀어 보겠습니다. 고대어 사전 / ALGOSPOT / V2 풀이 O(N) 문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 제출링크 : https://algospot.com/judge/submission/detail/664902 문제해설 : https://skysign.tistory.com/197 import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.io.DataI..
-
시간 복잡도를 보다 빠르게~ 고대어 사전 / ALGOSPOTALGOSPOT 2020. 3. 27. 17:11
문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 이전 포스팅에서 답은 나오지만, 너무 느린 O(N^2) 시간 복잡도를 가진 코드로 작성해서, 이번에는 시간 복잡도를 개선하는 코딩방법에 대해서 알아 보겠습니다. DICTIONARY / ALGOSPOT 문제는 Topological sort를 사용해서 푸는 문제입니다. Topological sort는 그래프에 속해있는 vertex와 edge에 따라서 정렬하는 방식임으로, 우선 그래프(graph)를 어떻게 코딩할지를 알아 보겠습니다. 그래프 코딩 방법 크게 2가지 방법이 있구요, 리스트와 2차원 배열을 이용하는 방식입니다. HashMap과 같은 container를 사용해서, vertex와 edge를 구현하는..