본문 바로가기

알고리즘

 (36)
DFS DFS (Depth-First Search) 깊이 우선 탐색 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프 연결 관계 표현 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계 표현 # 인접 행렬 INF = 999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] # 인접 리스트 graph = [[] for _ in range(3)] # node 0 graph[0].append((1,7)) graph[0].append((2,5)) # node 1 graph[1].append((0,7)) # node 2 graph[2].append((0,5))
Python 연산자 OperatorDescriptionExample + 더하기 a + b = 30 - 빼기 a - b = -10 * 곱하기 a * b = 200 / 나누기 b / a = 2.0 % 나머지 b % a = 0 ** 제곱 a ** c = 1000 // 몫 a // c = 3
합병 정렬 (Merge Sort) 합병 함수 - 2개의 정렬된 List 합병 template void Merge (T* initList,T* mergedList, const int l, const int m, const int n) { for (int i1=l, iResult=1, i2=m+1; i1
정렬(Sorting) - 합병 정렬 (Merge Sort) 합병 정렬 (Merge Sort) 이미 정렬된 리스트 2개 → 1개의 정렬된 리스트 시간 복잡도 : O(n-l+1) . [ n-l+1 = 원소 수] init List 3 4 8 10 2 6 8 9 ↑ l ↑ m ↑ m+1 ↑ n i1 i2 merged List 2 3 4 6 8 8 9 10 반복 합병 정렬 입력 열의 길이가 1인 n개의 정렬된 List를 합병하여 길이가 2인 List 생성 길이가 2인 n/2개의 List를 합병하여 길이가 4인 List 생성 길이가 n인 List로 최종 합병될 때까지 계속
정렬(Sorting) - 퀵 정렬 (Quick Sort) pivot, i, j를 이용하여 i는 왼쪽에서 오른쪽으로 이동하며 pivot보다 큰 값을 찾고 j는 오른쪽에서 왼쪽으로 이동하며 pivot보다 작은 값을 찾은 후 a[i] a[j]를 swap i를 기준으로 분할 (Partition) 후 단계 반복 평균 수행시간 최소 순환호출 사용 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] left right (26 5 37 1 61 11 59 15 48 19) 1 10 ↑ pivot ↑ i ↑ j 19 37 ↑ i ↑ j 15 61 pivot i j (11 5 19 1 15) 26 (59 61 48 37) (11 5 19 1 15) 1 5 (1 5) 11 (19 15) 1 5 1 2 15 19 4 5 (59 61 48 37) 7 10 (48..
정렬(Sorting) - 삽입 정렬 (Insertion Sort) 단계 삽입 원소를 기존의 정렬된 부분 리스트 속에 끼워 넣기 삽입 원소의 위치를 옮기면서 처음 단계의 insert 반복 적용 분석 $\sum_{i=1}^{n-1}(i+1)=n^2$ → O($n^2$) 최선 : 오름차순으로 정렬된 상태 최악 : 내림차순으로 정렬된 상태 data 양이 적을 때 사용하면 빠름 dyeoma.tistory.com/40 삽입 정렬 (Insertion Sort) 기본 단계 insert 함수 template void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입 // a[0] = -∞; while (e < a[i]){ a[i+1] = a[i]; i--; } a[i+1] = e; } 최악 : i+1 삽입 정렬 함수 templa.. dyeom..
퀵 정렬 (Quick Sort) WorkHorse void QuickSort (T* a, const int left, const int right) { // Workhorse // pivot = a[left] // a[left] pivot );// j : right→left. pivot보다 큰 값 찾기 if (i
삽입 정렬 (Insertion Sort) 기본 단계 insert 함수 template void Insert (const T& e, T* a, int i) { // 정렬된 리스트에 e 삽입 // e = 끼워넣을 값 // a = 배열 // i = 현재까지 정렬된 index // a[0] = -∞; while (e < a[i]){ a[i+1] = a[i]; i--; } a[i+1] = e; } 최악 : i+1 삽입 정렬 함수 template void InsertionSort (T* a, const int n) { // a[1:n] 오름차순 정렬 for (int j=2; j

티스토리툴바