728x90 반응형 Python19 BFS(Breadth-First Search) BFS 너비우선탐색 - 가까운 노트부터 먼저 탐색하는 알고리즘 - queue 사용 - 시작노드 1일 경우 큐에 1 삽입 / 현재 큐 1 / 방문 1 1을 꺼내서 인접노드 2 3 8 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 2 3 8 / 방문 1 2 3 8 2를 꺼내서 인접노드 1 7 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 3 8 7 / 방문 1 2 3 7 8 3을 꺼내서 인접노드 1 4 5 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 8 7 4 5 / 방문 1 2 3 4 5 7 8 8을 꺼내서 인접노드 1 7 중 방문하지 않은 노드는 큐에 삽입하고 방문처리 / 현재 큐 7 4 5 / 방문 1 2 3 4 5 7 8 7을 꺼내서 인접노드 2 6 중 방.. 2022. 7. 7. DFS(Depth-First Search) DFS 깊이우선탐색 - 스택 또는 재귀함수 이용 - 작은 것부터 탐색 - 시작노드 1일 경우 1 방문처리 / 방문 1 1의 인접노드 2 3 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 2의 인접노드 1 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 7의 인접노드 2 6 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 6의 인접노드 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 7의 인접노드 2 6 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 8의 인접노드 1 7 중 방문하지 않은 노드가 있으면 방문처리 / 방문 1 2 7 6 8 1의 인접노드 2 3 8 중 방문하지 않은 노드가 있으면 방문처리 / 방문 .. 2022. 7. 3. Python 재귀함수로 GCD 최대공약수 구하기 GCD(Greatest Common Divisor)를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다. 유클리드 호제법 - 두 자연수 A, B 에 대햐여 A > B 일 때 A를 B로 나눈 나머지를 R이라고 하자 이 때 A와 B의 최대공약수는 B와 R 의 최대공약수와 같다. ex) GCD(192, 162) = 6 def GCD(a, b): if a % b == 0: return b return GCD(b, a%b) print(GCD(192, 162)) 6 출처 https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 2022. 7. 3. Python queue 사용하기 from collections import deque 파이썬 내장모듈 collections 에서 deque 라이브러리 사용 from collections import deque queue = deque() deque 는 double ended queue 의 줄임말로 양방향 데이터 처리가 가능하다. queue.append(data) queue.popleft() 사용으로 큐로 사용 사진 출처 https://jungeun960.tistory.com/148 2022. 7. 3. Python eval() 함수 문자열 계산, 진짜 수로 바꾸기 input 으로 식을 받았다면 eval() 함수를 통해 바로 계산할 수 있다. data = input #1+2 number = eval(data) print(number) 3 또는 문자로 된 숫자를 정수로 바꿀 수 있다. data = '200' number = eval(data) print(number) 200 2022. 7. 2. 이전 1 2 3 4 다음 728x90 반응형
