매일 매일 미라클 코딩

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

데이터를 탐색할 때 쓰이는 대표적인 탐색 알고리즘 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

리스트를 두 그룹으로 나누어 먼저 정렬하고, 두 그룹의 맨 앞부터 차례대로 병합하는 방식. 한 그룹의 자료가 모두 소진되면 남은 그룹의 정렬 상태 그대로 결과 리스트에 삽입하면 된다. 이렇게 주어진 문제를 절반으로 나눈다음 각각 재귀호출로 풀어가는 방식을 '분할정복'이라고 함 시간 복잡도 O(n logn)으로 O(n²)인 선택/삽입정렬보다 빠르다. 따라서 정렬해야할 자료의 개수가 많을 수록 병합정렬이 선택/삽입 정렬보다 좋은 성능을 보인다. def merge_sort(a): n = len(a) #종료 조건 if n