320x100 PS84 [CLASS 4]백준 1238번 - 파티 1238번 : 파티 문제를 보고 가장 먼저 든 생각은 역시 코드를 작성하는 입장에서 가장 편한 플로이드 와샬 알고리즘이었다. 어렵지 않게 첫 시도를 해볼 수 있었다. 내 코드(플로이드 와샬, 시간 초과) # dawitblog.tistory.com/169 import sys input = sys.stdin.readline INF = sys.maxsize # 입력 n,m,x = map(int,input().split()) x -= 1 # 길 소요시간 리스트 roads = [[INF]*n for _ in range(n)] for _ in range(m): a,b,t = map(int,input().split()) a -= 1 b -= 1 roads[a][b] = t # 플로이드 와샬 for v in range.. 2021. 7. 1. [CLASS 4]백준 1167번 - 트리의 지름 1167번 : 트리의 지름 트리의 지름의 특징에 대해 잘 생각해보면 DFS를 통해 쉽게 풀 수 있는 문제이다. 해당 문제랑 완전히 동일한 문제를 풀었었다... https://dawitblog.tistory.com/153 왠지 너무 익숙하더라.. [CLASS 4]백준 1967번 - 트리의 지름 1967번 : 트리의 지름 이 문제를 풀기 위한 핵심 아이디어만 알았다면 쉽게 풀 수 있다. 문제에 힌트가 나와 있는데, 트리의 지름의 양 끝에 해당하는 두 노드를 선택해서 양쪽으로 당기면 나머지 dawitblog.tistory.com 내 코드: # dawitblog.tistory.com/168 from sys import stdin input = stdin.readline # 입력 n = int(input()) t.. 2021. 6. 30. [CLASS 4]백준 14938번 - 서강그라운드 14938번 : 서강그라운드 가장 먼저 든 생각은 플로이드 와샬 알고리즘이었다. 구현이 쉽기도 하고 지역의 개수가 최대 100개라 O(V^3)으로도 풀릴까? 라는 생각에 먼저 플로이드 와샬로 구현해 보았다. 내 코드(플로이드 와샬): # dawitblog.tistory.com/166 import sys input = sys.stdin.readline INF = sys.maxsize # 입력 n,m,r = map(int,input().split()) items = list(map(int,input().split())) roads = [[INF]*n for _ in range(n)] for _ in range(r): a,b,c = map(int,input().split()) a -= 1 b -= 1 road.. 2021. 6. 29. [CLASS 4]백준 11404번 - 플로이드 11404번 : 플로이드 재미없게 문제 제목에서 어떤 알고리즘을 써서 풀어야 할지 스포일러 해버린 문제이다. 방향성이 있고 음의 간선이 없는 그래프에서 모든 정점에서 모든 정점까지의 최단거리를 구할 때는 플로이드 와샬 알고리즘을 사용한다. 이를 알고 있다면 아주 쉽게 풀 수 있는 문제이다. 구현도 어렵지 않다. 내 코드: # dawitblog.tistory.com/165 from sys import stdin input = stdin.readline INF = 10_000_000 # 도시 수 n = int(input()) # 노선 비용 정보 cities = [[INF]*n for _ in range(n)] # 입력 for _ in range(int(input())): a,b,c = map(int,inpu.. 2021. 6. 28. 이전 1 2 3 4 ··· 21 다음
