### Floyd-Warshall(플로이드-워셜) ### : 그래프에서 모든 정점간 사이의 최단 거리 찾기 => 모든 최단경로 구하기 == 모든 정점 최단 경로 알 수 있다. + 모든 경로를 돌아보는 것으로 왔다갔다한 것을 다 알 수 있다. 시간 복잡도: O(n^3) for i in range(n): for j in range(n): for k in range(n): if dist[j][k] > dist[j][i] + dist[i][k] dist[j][k] = dist[j][i] +dist[i][k]
하노이의 탑
### 하노이의 탑 ### : 3개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있다. : n개의 원판 일 경우 원판을 모두 마지막 기둥으로 옮길 수 있는 방법의 수는 (2^n) - 1번 이다 (메르센 수) 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있으면 안된다. # 첫 번째 규칙 1->2, 1->3, 2->3을 잘 생각해서 재귀 하면 된다. # 재귀할 때 해당 code 다 끝나면 돌아온다. def hanoi(n, from_, to_, by_): if n == 1: print(from_, by_) else: hanoi(n-1, from_, by_, to_) print(from_, by_) hanoi(n-1, to_, from_, by_)
#1. import time start = time.time() #시간 시작 # ... # source code # ... end = time.time() #시간 끝 total_time = end - time #source code 시간 print(total_time) #2. import timeit start = timeit.default_timer() # ... # source code # ... end = timeit.default_timer() total_time = end - time #source code 시간 print(total_time) 결국 total_time 이 0.304020234234 이면 => source code가 0.3초 걸린다. https://www.ics...
함수를 만들어서 풀 때 None을 반환하는 경우가 있습니다. Why? 함수가 반환할 값이 없을 때 None을 반환합니다. 그래서 함수를 사용할 때 중간 중간에 return도 좋지만 끝에 return을 넣어주어 반환값을 잘 지정해야 합니다. # wei 값이 모두 1일 경우 sol2의 함수는 None을 반환 합니다. n = int(input()) wei = list(map(int,input().split())) wei.sort() def sol(): value = 1 for i in wei: if value < i: break value += i return value def sol2(): value = 1 for i in wei: if value < i: return value value += i ..
1. 재귀 함수를 사용할 경우 (DFS , BFS ....) 재귀가 가능한 허용 깊이를 늘려주는 코드 사용 import sys sys.setrecursionlimit(1000001) 2. 속도가 느릴 경우 빠르게 하는 방법 (1) input() -> sys.stdin.readline() 으로 변경 import sys sys.stdin.readline() (2) Python3 대신 PyPy를 사용하자 (but PyPy에서는 sys.setrecursionlimit 사용 못함....) PyPy 설명 링크 https://ko.wikipedia.org/wiki/PyPy