분류 전체보기114 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. 기본 소프트웨어 시스템 설계 관점 스터디를 위한 자료로 "데이터 중심 애플리케이션 설계" 책을 읽고 정리한 것이다. Q. 시스템(현재 서비스 되고 있는)에서 가장 크게 부하를 주는 요소는 무엇일까?Q. 소프트웨어의 3가지 요소(신뢰성, 확장성, 유지보수성)을 고려하고 있는가? (고려 했는가?)Q. 내부 시스템 요소(데이터베이스 등)를 잘 이해하고 사용하고 있는가? 시스템은 기술 숙련도, 조직 구성과 같은 외부적인 요인과 시스템 간의 의존성, 응답 시간과 같은 내부적인 요인들이 설계에 많은 영향을 끼친다. (현실은 항상 Clear하지 않으므로)그러나 이런 상황에서도 시스템은 항상 신뢰성, 확장성, 유지보수성에 대한 기준을 가지고 고려되어야 한다. (그렇게 하려고 최소한 노력해야 한다.)때문에 소프트웨어 시스템에서 중요하게 여기는 3가지 관.. 2019. 6. 24. 이전 1 ··· 8 9 10 11 12 13 14 ··· 29 다음
