(23.05.14) https://github.com/gompaang/algorithm_python GitHub - gompaang/algorithm_python Contribute to gompaang/algorithm_python development by creating an account on GitHub. github.com Count sort (계수 정렬) 모든 데이터가 양의 정수이고, 데이터의 범위가 제한 적일 경우에 사용하면 매우 빠르다. 시간 복잡도와 공간 복잡도는 O(N+K) 이다. 동일한 값을 가지는 데이터가 여러 개 등장할 때 사용하기에 적합하다. # count sort def count_sort(array): count = [0] * (max(array)+1) result = []..
(23.05.14) 정렬 알고리즘 정리!! https://github.com/gompaang/algorithm_python GitHub - gompaang/algorithm_python Contribute to gompaang/algorithm_python development by creating an account on GitHub. github.com selection sort : 선택 정렬 1. 가장 작은 수를 선택하여 맨 앞의 수와 자리를 바꾼다. 2. 그 다음으로 가장 작은 수를 선택하여 맨 앞에서 두번째 수와 자리를 바꾼다. 3. 위의 과정을 반복한다. def selection_sort(array): for i in range(len(array)): min_index = i for j in ..
(23.03.31) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.5 chain matrix multiplication chain matrix muliplication - 행렬 곱셈 연산에서 곱셈 순서를 다르게 하면, 곱셈 cost도 달라지는데 최소의 cost로 곱셈 연산을 할 수 있도록 하는 방법을 dynamic programming 알고리즘을 통해서 알아낼 수 있다. - 아래와 같이 A, B, C, D 행렬의 곱셈 순서를 다르게 하면 cost가 다르다. - T..
(23.03.30) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.4 Knapsack 예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/140 Knapsack - 최대 무게가 정해져있는 배낭 안에 value가 최대가 되도록 물건을 담는 방법을 찾는 문제이다. - knapsack은 중복을 허용하여 물건을 선택하는 경우와 중복을 허용하지 않고 물건을 선택하는 경우로 나누어 생각해 볼 수 있다. knapsack with re..
(23.03.29) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.3 Edit distance Edit distance - edit distance: 어떤 두 단어(문자열)가 같아지도록 하기 위해 수행해야하는 연산의 수 (minimum number of edits) - 예를 들어 edit distance를 해결한 예시를 살펴보면 아래와 같다. - edit distance by dynamic programming - edit distance algorithm by ..
(23.03.29) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 6.1 Shortest paths in dags, revisited 6.2 longest increasing subsequences Dynamic Programming - dynammic programming의 핵심은 문제를 한 번만 풀도록 하는 것이다. - 하나의 problem을 sub-problem으로 계속해서 쪼개고, 가장 작은 sub-problem부터 해결함으로써 더 큰 sub-problem을 ..
(23.03.25) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 5.2 Huffman encoding ---> prefix encoding 예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/152 Huffman encoding - 빈도수에 따라서 문자를 bit로 표현하는 방법이다. - 빈도수가 높을수록 더 적은 bit, 빈도수가 낮을수록 더 많은 bit으로 표현한다. - 이를 표현할 때 prefix-free encodin..
(23.03.24) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 5.1 Minimum spanning trees -> prim's algorithm Prim's algorithm - dijkstra와 비슷한 방법으로 priority queue를 사용한다. - priority queue에다가 weight를 저장하여 가장 작은 weight을 가진 노드를 꺼내는 방식으로 진행한다. 꺼낸 노드에 인접한 노드의 cost와 edge의 weight을 비교하여 더 적은 값으로 업..
(23.03.20-22) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 5.1 Minimum spanning trees -> kruskal's algorithm -> cut property -> Union Find Greedy algorithm 매 순간마다의 최선의 선택을 하는 방법인데, 매순간마다의 그 최선의 선택이 결국 최종적으로 최선의 선택이 된다는 보장은 없다. top-down 방식으로 최선의 선택을 하는 것이다. 다시 말하면 아래와 같다. "solution ..
(23.03.19) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 4.6 Shortest paths in the presence of negative edges 4.7 Shortest paths in dags negative edges가 있는 graph에서 shortest path를 찾는 알고리즘으로는 Bellman-Ford algorithm 이 있다. - input: graph, length_e, start_node - output: distance_v - 시작 노..
(23.03.17) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 4.4 Dijkstra's algorithm 4.5 Prority queue implementations Dijkstra's algorithm은 BFS를 좀더 일반적인 graph로 가져온 것인데, BFS와는 다르게 edge의 length가 positive integers로 구성되어있다. Dijkstra's algorithm 수행 예제 priority queue - 우선순위 큐 heap - heap di..
(23.03.16) (최종 업데이트: 23.05.14) https://github.com/gompaang/algorithm_python GitHub - gompaang/algorithm_python Contribute to gompaang/algorithm_python development by creating an account on GitHub. github.com DFS, BFS는 탐색 알고리즘의 대표적인 2가지 알고리즘이다. DFS,BFS 구현시 알아두어야하는 자료구조 #reference: https://data-marketing-bk.tistory.com/44 #depth-first search #1. dfs by python list (stack) def dfs_list(graph, start..
(23.03.16) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 4.1 Distances 4.2 Breadth-first search 4.3 lenghts on edges BFS 예제 수업 들으면서 정리해두었던, DFS, BFS 개념과 예제 https://hey-stranger.tistory.com/153 [알고리즘] Network flow : BFS & DFS (2021.11.12) 알고리즘 수업들으면서 정리하기 19탄 w10-3 녹화강의, w11-1 실강 BFS..
(23.03.15) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 3.4 Strongly connected components