위상정렬2 [C++] 2623번: 음악 프로그램 (위상 정렬) https://www.acmicpc.net/problem/2623문제 이해하기 문제의 요구사항은 다음과 같습니다.각 부분 순서를 보고, 이에 맞는 전체 순서를 구하여라. 시간복잡도 어림하기위상 정렬 알고리즘 여러 노드들의 순서 정보를 보고 전체 순서를 결정하는 것은 위상 정렬 알고리즘으로 해결할 수 있습니다. 위상 정렬 알고리즘의 시간복잡도는 O(V + E)입니다. 이 문제에서 N의 최대값은 1000이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.알고리즘 설계하기 위상 정렬은 Khan 의 알고리즘을 사용하여 다음과 같이 구현합니다./*L : 정렬된 원소들을 담을 리스트*//*S : incoming edge가 없는 노드의 집합*/while S가 비어있지 않을 때 동작 S에서 노드 n 삭제 .. 2024. 8. 16. [C++] 백준 2252번: 줄 세우기 (위상 정렬) https://www.acmicpc.net/problem/2252문제 이해하기 문제의 요구 사항은 다음과 같습니다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 앞에서부터 줄을 세운 결과를 구하여라.시간복잡도 어림하기 이번 문제는 문제 페이지를 알고리즘 분류를 보고 힌트를 얻어 해결한 문제입니다. 위상 정렬이라는 개념을 사용하여 해결하는 문제로, 알고리즘을 설계하기 전에 시간복잡도를 어림하기 애매하여 이번 단계는 생략하도록 하겠습니다.알고리즘 설계하기 문제 페이지의 알고리즘 분류에 '위상 정렬'이 있는 것을 보고 위상 정렬에 대해 알아보았습니다.위상 정렬은 "방향 그래프의 노드를 간선의 방향을 거스르지 않도록 나열하는 것"을 의미합니다. 이때, 위상 정렬를 하기 위해서는 그래프의 순환이 존재하면 안 됩.. 2024. 7. 15. 이전 1 다음