그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제 2458번: 키 순서  1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다. 예를 들어 1번  이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고,  그렇지 못한 학생들도 있다. 이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------------ 상식적으로? 먼저 생각해보면 i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾..

• format_list_bulleted 그래프 이론 정복기
• · 2025. 3. 29.
• textsms

플로이드 워셜 주의해야할 점(k > i > j 순서로 돌기)

2224번: 명제 증명 명제가 주어질때 참으로 가능한 명제들을 모두 출력하는 문제 p => p같은 전건과 후건이 같은 명제는 출력하지 말고 삼단논법에 의해서만 참이 될 수 있는 명제만 출력하는 문제 전건 후건으로 가능한 것은 알파벳 대소문자이고 총 52개여서 이를 노드 번호로 바꿔주고 from sys import stdinn = int(stdin.readline())node = {chr(i+65):i for i in range(26)}for i in range(26,52): node[chr(i+71)] = ichange = {v:k for k,v in node.items()}  A => b,  b => C이면 A노드에서 b노드로 갈 수 있다는 의미이고, b노드에서 C노드로 갈 수 있다는 의미..

• format_list_bulleted 최단거리 알고리즘
• · 2025. 1. 11.
• textsms