매일 매일 미라클 코딩

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

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