IT/Algorithm16 Bellman Ford 벨만 포드(Bellman Ford) 알고리즘에 대해 알아보려고 한다. (자세한 부분은 아래 페이지 참조)https://www.geeksforgeeks.org/bellman-ford-algorithm-simple-implementation/https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ 벨만 포드 알고리즘을 알아보기 전에 흔히 알려진 다익스트라 알고리즘은 시작점으로부터 그래프 상의 모든 정점까지의 최단 거리를 찾아준다. 그러나 간선 값이 양수가 아닌 음수일 경우에는 정상적으로 알고리즘을 사용할 수 없다. 바로 이 시점에 등장한 것이 벨만 포드 알고리즘이다.즉, 간선 값이 음수 일 경우에도 시작점으로부터 모든 정점까지의 최단 거리를 찾아 준다. 물론.. 2019. 8. 25. Disjoint Set (Improved) 개선된 버전인 Disjoint Set에 대해 알아보려고 한다. 보다 자세한 내용은 아래 페이지를 확인하면 된다.(https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/) 이전에 살펴본 Disjoint Set은 Union-Find 알고리즘 사용하여 undirected graph 에서 순환을 찾는 방식을 취했었다.def find_parent(self, parent, i): if parent[i] == -1: return i if parent[i] != -1: return self.find_parent(parent, parent[i]) # A utility function to do union of two subsets def union.. 2019. 7. 22. Disjoint Set Disjoint Set에 대해 알아보려고 한다. 보다 자세한 부분은 아래 페이지를 확인하면 된다.(https://www.geeksforgeeks.org/union-find/) Disjoint Set 자료 구조의 정의를 먼저 살펴보면 여러 개의 분리된 하위 집합(Subset)으로 분할된 여러 집합을 기록하는 자료 구조이다.일반적으로 Disjoint Set을 Union-Find로 불리기도 하는데 이는 내부적으로 Union-Find 알고리즘이 사용되기 때문이다. 잠시 해당 알고리즘을 살펴보면, (정의된 명명처럼 union 및 find 작업을 수행한다.)1) Find : 어느 특정한 요소가 어느 하위 집합에 있는지 찾는 작업 (보통 두 요소가 같은 하위 집합에 있는지 찾을 때 사용된다.)2) Union : 두 .. 2019. 7. 22. 0-1 Knapsack 이번에는 0-1 Knapsack 문제에 대해 알아보려고 한다.(https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) 일반적으로 해당 문제는 N개의 아이템에 대한 Value와 Weight가 주어졌을 때, 배낭(knapsack)의 최대 허용치 Weight 만큼 아이템을 넣어 최대 Value를 찾는 것이다.즉, 각각의 아이템을 선택할 필요가 없으며 넣었다 뺐다 (0-1 속성) 하면서 최대 Value를 뽑아내는 것이다. 위의 예시를 보면, Knapsack의 최대인 W = 50 안에서 여러 아이템을 섞는다. (결과는 220)물론 직관적으로 가장 쉬운 방법은 모든 아이템을 찾아서 일일이 만들어 보는 방법이다. def knapSack(W , wt , val , n).. 2019. 6. 28. 이전 1 2 3 4 다음
