코딩테스트 (5) 썸네일형 리스트형 BFS 설명 및 구현 with 파이썬 ※ BFS란? BFS. Breadth First Search 말그대로 너비 우선 탐색 그래프에서 가장 가까운 노드부터 먼저 탐색한다 ※ BFS구현? - BFS는 큐를 통해서 구현한다 ※ BFS 과정은? 1. 탐색을 시작할 노드를 큐에 삽입하고 방문 처리한다 2. 큐에서 노드를 꺼낸다. 인접한 노드 중에 방문하지 않은 노드가 있으면 모두 큐에 넣고 방문 처리한다 3. 더이상 2번을 수행할 수 없을 때까지 반복한다. ※ BFS 구현 def bfs(graph, v, visited): queue = deque() visited[v] = True print(v,"방문했음") queue.append(v) while len(queue) != 0: for i in graph[queue.popleft()]: if not.. 파이선 DFS 설명 및 구현 ※ DFS란? DFS. Depth First Search 말그대로 깊이 우선 탐색 그래프에서 가장 깊은 부분을 먼저 탐색한다 ※ DFS구현? - DFS는 스택 or 재귀를 통해서 구현한다 => 스택을 재귀로도 구현하니까 당연한말이다. ※ DFS 과정은? 1. 탐색을 시작할 노드를 스택에 삽입하고 방문 처리한다 2. 스택의 최상단 노드에 인접한 노드 중에 방문하지 않은 노드가 있으면 방문 처리하고 스택에 집어 넣는다 - 최상단 노드에 인접한 노드 중 방문하지 않는 노드가 없다면 스택에서 꺼낸다. 3. 더이상 2번을 수행할 수 없을 때까지 반복한다. ※ DFS 구현 def dfs(graph, v, visited): visited[v] = True print(v, ends=' ') for i in graph[.. 파이썬 재귀함수 재귀함수란 자기 자신을 다시 호출하는 함수 def recursive_function(): print("이 함수는 재귀") recursive_function() recursive_function() 파이썬에서는 재귀함수 깊이에 한계가 있기 때문에 어느 정도 이상이면 종료됨. 하지만 코테에서는 무조건 종료조건 넣어줘야함. 그렇지 않으면 무한루프.... def recursive_term_function(i): if i == 100: return print(i, "번째 재귀함수에서",i + 1, "번째 재귀함수 호출한다") recursive_term_function(i+1) print(i, "번째 재귀함수 종료한다") recursive_term_function(1) 파이썬으로 재귀함수 팩토리얼 구현 def fa.. 파이썬 큐 구현 from collections import deque queue = deque() #삽입 1, 3 queue.append(1) queue.append(3) #꺼내기 순서 1, 3 queue.popleft() queue.popleft() print(queue) queue.reverse() print(queue) 파이썬 스택 구현 stack = [] #삽입 순서 1, 3 stack.append(1) stack.append(3) #pop 순서 3, 1 stack.pop() stack.pop() #최상단부터 출력 print(stack[::-1]) #최하단부터 출력 print(stack) 이전 1 다음
