본문 바로가기

전체 글114

Topological Sorting 위상 정렬이라고 불리는 Topological Sorting 에 대해 알아보려고 한다. Topological Sorting은 Directed Acyclic Graph (DAG)를 사용하여 Vertices를 순서 있게 나열하는 것이다. (즉, DAG 형태가 아니라면 해당 정렬은 사용할 수 없다.) 그림 1. DAG 그런데 기본 구조인 그래프의 특성상 정렬 방법은 여러개가 될 수 있다.그림 1을 보면 (5, 4, 2, 3, 1, 0), (4, 5, 2, 3, 1, 0) 이렇게 2개가 될 수 있다. 이는 시작점은 항상 들어오는 부분이 없는 (in-degree가 0) 정점이 되어야 한다. 이를 바탕으로 그림 1을 보면 In-degree가 0인 부분은 2개(5, 4) 이다. Topological Sorting의 구.. 2019. 6. 10.
[Kubernetes] StatefulSet 이번 포스팅에서는 StatefulSet에 대해 알아보려고 한다. ReplicaSet 그림 1. ReplicaSet 다시금 ReplicaSet을 살펴보면 그림 1 처럼 미리 정의해 놓은 Pod의 설정을 Replicas 개수에 따라 만든다. 그림 2. PVC & PV 더군다나 Pod를 설정 할 때 PVC와 같은 Volume을 포함하게 되면 그림 2와 같이 Replicas로 만들어진 모든 Pod는 동일한 PVC를 참조하게 된다. (ReplicaSet으로 만들어지는 모든 Pod는 동일한 매니페스트 파일을 사용하기 때문에) 만일, 위와 같이 사용하고 싶다면 큰 문제는 없지만 그렇지 않다면 문제가 될 수 있다. 이미 매니페스트 파일을 만들 때 PVC를 정의했기 때문에 각 Pod는 다른 PVC를 접근할 수 없다. 이.. 2019. 6. 7.
[Kubernetes] Headless Service 그림 1. Service 일반적으로 Service는 Client에 의해 요청이 들어올 경우 Service가 관리하고 있는 여러 Pod들 중 임의로 하나를 선택해서 연결을 한다. 그런데 만일 Client가 Service가 제공하는 모든 Pod와 연결이 필요하다면 어떻게 해야 할 것인가? 어찌보면 당연하게도 모든 Pod의 주소를 알면된다.이를 위해 k8s에서는 Client가 DNS lookup을 통해 Pod의 IP를 찾는 것을 허용한다. 그런데 매니페스트 파일을 구성할 때 속성에 따라 DNS lookup 에서 나오는 결과가 다르다.spec: clusterIP: None 위와 같이 Service의 ClusterIP를 None으로 설정하면 DNS는 Service의 ClusterIP 대신에 모든 Pod의 IP 목.. 2019. 6. 7.
Segment Tree Segment Tree는 Tree의 일종으로 각 노드에 특정 범위에 대한 정보가 담겨있다. (범위를 Interval, Segment 등으로 표현한다.) Tree의 응용은 당연스럽게 기존의 방식으로는 시간 복잡도가 높기 때문이다. 한 가지 예를 든다면, [1,2,3,4,5]의 트리에서 (배열로 구성된 트리) 2~4 사이의 합을 알고 싶다면 어떻게 해야 할까?누구나 접근할 수 있는 쉬운 방법은 전체를 다 훑어보는 것이다. 그렇다면 O(n) 정도의 시간 복잡도가 나온다. 그런데 만약 부분합과 같이 각 노드에 미리 합쳐진 값이 존재한다면 O(1)과 같이 상수의 시간 복잡도로 범위 값을 찾을 수 있다. 이렇듯 Segment Tree는 범위에 대한 정보를 미리 저장함으로써 다음 계산시에 사용할 수 있도록 한다. 때.. 2019. 6. 7.
Boyer–Moore Majority Vote 우연찮게 본 Boyer-Moore majority vote 알고리즘에 대해 알아보려고 한다. Boyer-Moore는 사람 이름이라 제외하고 Majority vote만 보면, 말 그대로 가반수 값을 찾는 알고리즘이다.때문에 단순히 input 데이터 중 반복되는 값이 많은 것을 찾는 것이다. 그림 1. Boyer-Moore Majority Vote 그림 1을 보면 좀더 확실하게 알 수 있다. X축 밑에 그림이 각 순차적인 인덱스 별로 나오는 값이고 Y축 값은 Majority 값의 개수를 나타낸다.그래서 맨 처음 0으로 시작하다 마지막엔 빨간색 네모가 카운트 4까지 위치하는 것을 볼 수 있다. 결과적으로 빨간색 네모가 해당 input 데이터 중 가반수를 차지한다는 의미이다. 이처럼 가반수의 값이 무엇인지 쉽게.. 2019. 6. 6.
Insertion Sort Insertion Sort는 이름에서 드러나듯 값을 어딘가(?)에 넣어서 정렬한다. 글로는 어려 울 수 있으니 간단히 Flow를 확인하면 다음과 같다.12, 11, 13, 5, 6Let us loop for i = 1 (second element of the array) to 4 (last element of the array)i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12 11, 12, 13, 5, 6i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 11, 12, 13, 5, 6i = 3. 5 will move to the b.. 2019. 6. 6.

티스토리툴바