본문 바로가기
  • 기억의 유한함을 기록의 무한함으로✍️　 　 　 　 　 　 예비 개발자가 꿈꾸는 공간 여기는 안나의 개발 블로그 💻

topology sort2

[백준 Java] 2252번 줄 세우기 ( 그래프 , 위상정렬) [Gold III] 줄 세우기 - 2252 문제 링크 성능 요약 메모리: 46084 KB, 시간: 4360 ms 분류 그래프 이론, 위상 정렬 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 .. 2023. 6. 26.
[알고리즘 정리] Topology Sort ( 위상 정렬 ) - O(V+E), 순서가 정해져 있는 작업, 여러 답이 존재 Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc... 2023. 6. 26.
반응형

티스토리툴바