2020/0215 프림 알고리즘(Prim's algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이런 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 성택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 프림(Prim) 알고리.. 2020. 2. 6. 세그먼트 트리(Segment Tree) 세그먼트 트리는 구간의 값을 저장하는 트리입니다. 1~N인 수열이 있을 때, "인덱스가 a~b인 수들의 합을 구하고 싶다." 혹은, "a~b번째 수들 중 최소 값이나 최대값을 구하고 싶다." 같은 경우 사용합니다. 세그먼트 트리는 이진 트리 모습을 가지며 자식 노드는 부모 노드의 범위를 반 씩 가지고 있습니다. 즉, 부모 노드가 1~5까지의 구간합을 가지고 있다면 자식 노드의 왼쪽 자식은 1~3의 구간 합을 가지고 오른쪽 자식은 4~5까지의 구간 합으로 나눠가집니다. 수열의 크기(N)가 5인 수열 A = {1, 2, 3, 4, 5}의 구간 합을 구하고자 할 때 사용하는 세그먼트 트리를 생성해 봅시다. 인덱스(i)는 접근이 쉽게 0이 아닌 1부터 시작하였습니다. 처음 상태의 세그먼트 트리는 다음과 같습니다.. 2020. 2. 2. [Coursera][Machine Learning] 제출용 email, token 2주차에 Octave 실습 후 submit()에서 이메일이랑 토큰을 뭘 써야하는지 잘 몰랐었는데, Machine Learning > 2주 차 > Linear Regression 에 있었다. 편안하다. 2020. 2. 1. 이전 1 2 3 다음
