매일 매일 미라클 코딩

BFS는 큐 자료구조에 기초하여 구현이 간단하다. deque 라이브러리를 이용한다. 가까운 노드부터 탐색하는 알고리즘으로, 최대한 멀리있는 노드를 우선 탐색하는 DFS 와 반대이다. 인접 노드를 작은 순으로 큐에 담고, 다음 turn에서 빼므로 (선입선출) 자연스럽게 가까운 노드 순으로 방문하게 된다 DFS(깊이우선탐색) 보다 실제 수행시간이 짧다 = 빠르다. 1) 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다 2) 큐에서 노드를 꺼내, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 3) 2)의 과정을 더이상 수행할 수 없을 때 까지 반복 이번에도 위 그래프를 너비우선탐색 방식으로 처리해보자 from collections import deque #BFS 메서드..

DFS ( Depth First Search ) : 최대한 멀리있는 노드를 우선으로 탐색하는 방식 특정상황에서 최대한 깊숙이 들어가서 녿를 방문한 후 , 다시 돌아가 다른 경로를 탐색한다. 이 때 스택 자료구조를 이용한다 1) 탐색 시작 노드를 스택에 삽입 한 후 방문처리 2) 스택 최상단에 방문하지 않은 인접 노드가 있다면 그 인접노드를 스택에 넣고 방문처리 한다. 또 그 인접노드의 인접노드중 방문하지 않은 게 있다면 스택에 넣고 방문처리 ... (이때 재귀함수가 쓰인다) 3) 방문하지 않은 인접노드가 더 이상 없으면 수행을 멈춘다. 아래는 위 그래프를 DFS 방식으로 탐색하는 코드이다 #DFS 예제 #DFS 메소드 정의 def dfs(graph, v, visited): # 현재노드를 방문처리 visi..

데이터를 탐색할 때 쓰이는 대표적인 탐색 알고리즘 DFS와 BFS 를 이해하려면 기본 자료구조인 스택과 큐, 그리고 재귀함수에 대한 이해가 필요하다 아래는 스택과 큐를 간단히 구현하는 방법 1) 스택 # 스택에서의 삽입과 삭제 # 재귀함수는 내부적으로 스택 자료구조와 동일하다 stack =[] stack.append(5) #최하단 stack.append(2) stack.append(4) stack.append(7) stack.pop() # 자료 최상단에서 삭제 stack.append(1) # 최상단 print(stack) print(stack[::-1]) #자료 최하단부터 거꾸로 출력하는 방법 결과 [5, 2, 4, 1] [1, 4, 2, 5] 2) 큐 - deque 라이브러리가 필요하다는 점 유의 # ..

그리디: 지금 당장 좋은것을 고르는 방법. 현재의 선택이 나중에 미칠 영향을 고려하지 않을때 사용 Ex ) 큰 수의 법칙 예제 입력받은 숫자들을 M 번 더해 가장 큰 수를 만들어라 첫줄에 숫자 세개를 입력받는다 = 배열 크기 N, 숫자 더해지는 횟수 M, 연속더하기 가능한 수 K # 2