하노이의 탑
### 하노이의 탑 ### : 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_)
DFS(깊이 우선 탐색) : stack, 재귀함수, check 사용 : 멀리 있는 노드를 우선으로 탐색하는 알고리즘 => 최단거리 + 가중치(이동과정 제약) 경우 사용 def dfs(graph,start_node): visited = list() #queue stack = list() #stack stack.append(start_node) while stack: node = stack.pop() if node not in visited: visited.append(node) stack.extend(graph[node]) return visited https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
BFS(너비 우선 탐색) : 경로가 있는지 탐색하는 알고리즘 : 가까운 노드부터 탐색하는 알고리즘 : 주로 queue 사용 => 최단 거리만을 가지고 있는 경우 사용 # 속도를 빠르게 하기 위해 deque를 사용하기도 한다. from collections import deque def bfs(graph, start_node): visited = [] queue = list() queue.append(start_node) count = 0 while queue: node = queue.pop(0) if node not in visited: visited.append(node) queue.extend(graph[node]) return visited https://ko.wikipedia.org/wiki/%E..
#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 ..
ps 구현 문제를 풀다가 slice를 사용해하는 문제를 풀게 되었다 . 그러나 계속 slice 할때 나머지를 출력해야 하는데 list index out of range가 뜰거 같아서 뱅뱅 머물렀다 . 그런데 실수로 찾았다.... s[a:b]에서 b > len(s)+1를 넘어가도 a 부터 끝까지 출력이 된다. 즉, s[:len(s)+A] => s 전체 출력 (A > 1) https://dojang.io/mod/page/view.php?id=2208