코딩을 보라

결과 메모리: 167436 KB 시간: 868 ms 알게된 것 다익스트라: 한 정점에서 다른 모든 정점으로의 최단 거리 플로이드-와샬: 모든 정점에서 다른 모든 정점으로의 최단 거리 heap (https://hocheon.tistory.com/70) (https://dingrr.com/blog/post/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-heap%ED%9E%99) 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 형태의 자료구조. O(log n) 삽입: 트리 마지막 원소에 추가 삭제: 루트 노드 제거, 마지막 노드를 루트로 이동 이진 탐색트리와의 차이점: 이진 탐색트리는 탐색을 위함, 힙은 최소/최대값 찾기 위함. 왜 사용?: 데이터를 큐나, 배열에 데이터를 넣고 최..

결과 (PyPy3) 메모리: 127824 KB (개선: 126088ms) 시간: 5440 ms (개선: 640ms) 주의할 것 항상 index 때문에 틀렸습니다 를 한 번 마주친다. 조심하자!!!! 개선 시간이 너무 오래 걸려서 몇가지를 개선해보았다. 참고: https://www.acmicpc.net/source/18012011 maxsize 대신 0 대입. maxsize는 정말 필요할 때만 쓰자. 시간: 5440ms to 3232ms 🎉 import readline. 그냥 input() 대신 sys.stdin.readline import sys ip = sys.stdin.readline 시간: 3232ms to 640ms 😇 (이걸 이제까지 몰랐다니) 개선 전 코드 from sys import maxs..

https://www.acmicpc.net/problem/2458 결과 메모리: 126508 KB 시간: 976 ms 해결 방식 도저히 모르겠어서 블로그를 찾아봤다. (감사합니다 ㅎ.ㅎ) https://chldkato.tistory.com/42 아직 플로이드의 원리를 제대로 파악하지 못해서 그런 것 같다. 제대로 이해하고 풀자. key: 자신의 정점으로 오는 경로가 모두 파악된 것만이 자신의 키가 몇 번째인지 알 수 있다. 라는 것이다. 알게된 것 print([1, 2, 3, 3].count(3)) # count 함수 플로이드-와샬 알고리즘을 3번째 푸는데, 점점 감이 잡힌다! from sys import maxsize n, m = map(int, input().split()) arr = [[maxsiz..

결과 메모리: 126224KB 시간: 348ms www.acmicpc.net/source/24194515 해결방식 전형적인 플로이드 문제. maxsize를 import 하지 않고 100000정도로 설정하면 너무 작아서 "틀렸습니다"가 뜬다. 주의하기. 제출코드 # 제출 from sys import maxsize # 큰 값 max = maxsize n = int(input()) m = int(input()) route = \[\[max\] \* n for \_ in range(n)\] # 1. 도시1에서 도시1의 비용은 0이니까 for i in range(n): route\[i\]\[i\] = 0 # 2. 각 도시 간의 비용 연결 for \_ in range(m): a, b, c = map(int, inp..

알게된 것 다익스트라 알고리즘: 하나의 정점에서 다른 모든 정점으로의 최단 거리 구하기 플로이드 와샬 알고리즘: 모든 정점에서 모든 정점으로의 최단 경로 구하기, 거쳐가는 정점을 기준으로 최단 거리를 구한다. 참고 블로그 https://mygumi.tistory.com/110 https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F 이번 문제에서는 '플로이드 와샬 알고리즘'을 이용한다. BFS로도 풀 수 있다고 한다. 맨처음에는 BFS도 아닌, 플로이드도 아닌, 단순하게 각각의 거리를 비교하는 방식으로 풀었는데, 도저히 아닌 것 같아서 풀이를 검색해서 해결했다..

결과 메모리 123264 KB 시간 116 ms 알게된 것 bfs에서 도중에 return 하는 예시도 연습해봤다. 푼 과정 directions 순서가 방향마다 달라서 getDirections를 만들었다. bfs 처음에 매번 print(a, b) 해서 내가 의도한대로 동작하는지 다 따라가봤다. 역시 직접 해보는게 제일 빠르다! 제출 코드 # 제출 N, M = map(int, input().split()) robotR, robotC, currentD = map(int, input().split()) area = [list( map(int, input().split()) ) for _ in range(N)] directions = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 북 기준 de..

# 형변환 a, b = input().split() a = int(a) # map a, b = map(int, input().split()) # for문 for i in range(n): a, b = map(int, input().split()) print(a + b) # while, try/except while True: try: a, b = map(int, input().split()) print(a + b) except: break # if, and if (a == 0 and b == 0): break # split a, b = map(int, input().split(',')) # 문자열 입력받기 while True: try: print(input()) except EOFError: break ..