10000COW

들어가기 전에, 문제에서 주어진 '정렬할 대상의 갯수'가 커지면 정렬이 어렵다. 그것에 대한 해결책은? 분할 정복 기법(Divide-and-Conquer) STEP 1. 원래 문제를 독립적으로 풀 수 있는 작은 문제로 나눔(Divide) STEP 2. 각각의 문제를 풂(Delegate) STEP 3. 각각의 문제의 답을 이용해 원래 문제의 답을 만든다.(Combine) 정렬을 위한 분할 정복 기법은 대표적으로 두 가지가 있다. 1. 병합 정렬(Merge sort) 2. 퀵 정렬(Quick sort) 본격적으로 병합 정렬에 대해 알아보자. 알고리즘의 기본 아이디어 Divide - 정렬할 리스트를 앞 쪽 반, 뒤쪽 반으로 나눈다. Half Delegate(Front) - 앞 쪽 반을 정렬한다. Half De..

삽입 정렬 - 이미 정렬된 부분은 항상 정렬되어 있다. - 처음에는 정렬된 부분에 원소가 1개 - 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다. 시간 복잡도 Θ(n^2) - 가장 좋을 때: 이미 오름차순으로 정렬되어 있을 때 -> 총 n-1 번 = Θ(n) - 최악의 경우: 역순으로 정렬되어 있을 때 i번째 위치의 원소를 정렬된 부분에 추가할 때, i-1 개의 원소와 모두 비교해야한다. i = 2,3, ..., n일 때 각각 비교해야할 개수는 1+ 2+ ... + n-1 = n(n-1)/2 = Θ(n^2) 삽입 정렬 Python 코드 def insertionSort(): nums = list(map(int, input().split(' '))) for i in range(1, len(n..

버블 정렬: 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복. 시간복잡도: O(n^2) 버블정렬 Python 코드 def bubbleSort(): numbers = list(map(int, input().split(' '))) for i in range(0, len(numbers) - 1): for j in range(i+1, len(numbers)): if(numbers[i] > numbers[j]): tmp = numbers[j] numbers[j] = numbers[i] numbers[i] = tmp print(numbers) 입력 및 출력

BFS는 큐를 이용한 반복 구조로 구현한다. 먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자. 1) 큐를 이용한 BFS Pseudo code BFS(G, start_v) let Q be a queue label start_v as discovered Q.enqueue(start_v) while Q is not empty do v := Q.dequeue() if v is the goal then return v for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered then label w as discovered w.parent := v Q.enqueue(w) 2) 큐를 이..

1) 재귀를 이용한 DFS 구현 Pseudo code G는 그래프, v는 정점(vertex)일 때, DFS(G,v) lable v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w) 재귀를 이용한 DFS 구현 Python code def recursive_dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recusrive_dfs(w, discovered) ..