목록Algorithms/알고리즘 정리 (5)
공부하는 스누피
선택 정렬 - 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복한다. - 시간복잡도는 O(N^2)이다. => 배열 순회하는 반복문(N) + 가장 작은 데이터를 찾는 반복문(N-1+N-2+...+2) = N * (N+1) / 2 1) 바꿀 데이터의 인덱스를 i라 하고, 0(맨 앞)으로 초기화한다. 2) 가장 작은 데이터를 선택해 i 인덱스의 데이터와 바꾼다. 3) 그다음 작은 데이터를 선택해 i+1 인덱스에 있는 데이터와 바꾼다. 4) i가 배열의 마지막에 도착할 때까지 반복한다. def selection(arr): for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[i] > arr[j]: min_index = j..
(참고) www.geeksforgeeks.org/trie-insert-and-search/ Trie | (Insert and Search) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org Trie는 reTrieval data structure을 의미하며, 검색 복잡도가 최적의 값이 되게 해줍니다. 만약 우리가 k..
(참고) en.wikipedia.org/wiki/Topological_sorting Topological sorting - Wikipedia In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the gra en.wikipedia.org 컴퓨터 과학에서 방향이 있는 그래프의 위상 정렬이란 그래프의 노드를 정렬한 것으로..
(출처) www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks Minimum Spanning Tree for weighted, connected & undirected graph is a spanning tree with weight less than or equal to that of every other spanning tree. www.geeksforgeeks.org 최소 신장 트리는 무엇일까요? 방향이 없이 연결되어 있는 그래프에서 신장 트리(spanning tree)는 그래프의 모..
(참고) www.geeksforgeeks.org/window-sliding-technique/ Window Sliding Technique - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 슬라이딩 윈도우 기법 슬라이딩 윈도우 기법은 시간 복잡도를 줄이기 위해 중첩된 반복문을 어떻게 단일 반복문으로 바꿀 수 있는지..