위상정렬

[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다. 그럼 문제를 보자 문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다. 보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다. 그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다. [python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) 위상정렬 어떤..

[python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 )

위상정렬 어떤 일을 하는 순서를 찾는 알고리즘, 즉 순서가 정해져 있는 일을 차례대로 수행하는 것이다. 답이 여러개 가능 DAG(Directed Acyclic Graph)에만 적용 가능 큐나 스택을 사용 DAG(Directed Acyclic Graph) 방향성 비순환 그래프는 개별요소들이 특정한 방향을 향하고, 순환하지 않는것. ( o -> o -> o 요런 형태) 사실 그냥 봐서는 잘 이해가 가기 어렵다. 그러므로 고수님의 링크(https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html) 대강 어떤 알고리즘인지 알았다면 문제를 보자 문제를 쓰윽 보면 키 순서대로 학생을 정렬하려고 하는데 모든 학생의 비교 결과가 아닌 일부의 비교 결과..