gompaang/algorithm_python

algorithm_python

this repository is about algorithm implementation by python.
more detail description: https://hey-stranger.tistory.com

contents

• sorting
• divide-and-conquer
• dynamic programming
• greedy algorithm
• graph algorithm

0. sorting

주어진 배열을 오름차순(내림차순)으로 정렬하는 문제이다.

• selection sort [code]
• insertion sort [code]
• quick sort [code] , [python easy ver.]
• merge sort
• count sort [code]

1. divide-and-conquer

주어진 문제를 분할(divide)하고, 해결(conquer)하여 결과들을 다시 합(combine)하는 방식이다.
주로, recursive 재귀를 사용하여 구현한다.

• binary search : compare mid [code]
• merge sort
• quick sort : pivot, recursive [code]

2. dynamic programming

주어진 문제를 한 번만 풀도록 하는 방식이다.
큰 문제를 sub-problem으로 나눌 수 있으며, sub-problem을 해결한 정답이 큰 문제에서도 동일하다.
dynamic programming 과 divide-and-conquer 의 가장 큰 차이점은 sub-problem의 중복여부 이다.

• Fibonacci numbers : recursive, memoization(top-down), for문(bottom-up) [code]
• shortest paths (Floyd-Warshall)
• longest increasing subsequences
• edit distance
• knapsack
• chain matrix multiplication
• independent sets in trees

3. greedy algorithm

매 순간마다의 최선의 선택을 하는 방식이다.
매 순간마다의 최선의 선택을 한 것이 최종적인 전체 선택을 보았을 때 최선의 선택이 되는지는 정확하지 않다. greedy algorithm 으로 최적의 솔류션을 도출하는 문제들이 있다.

• MST (Minimum Spanning Tree)
  • Kruskal's algorithm : priority queue - heap [code]
  • Prim's algorithm
• Huffman-encoding

4. graph algorithm

• graph traversal
  • DFS (Depth-first search) : stack [code] , recusive [code]
  • BFS (Bredth-first search) : queue [code]
• shortest path
  • Dijkstra's algorithm : greedy (priority queue - heap) [code]
  • Bellman-Ford's algorithm : include negative edges [code]
  • Floyd-Warshall's algorithm : dynamic programming