본문 바로가기
728x90
반응형

BASE34

자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 순환이 생긴다. - G는 연결 그래프이고, 어떤 간선을 제거하면 연결그래프가 아니다. - G의 어떤 두 정점에 대해서 단순 경로가 하나 존재한다. 2. 신장 트리 (Spanning Tree) - 무향 연결 그래프 G의 부분그래프이고 G의 모든 정점을 포함하는 트리(Tree)인 그래프 1) 깊이 우선 신장 트리 (DFS Spanning Tree) 무향 연결 그래프 G에서 깊이 우선 탐색(DFS)으로 탐색하면서 생성된 신장 트리 (Spanning Tree) 2) 너비 우선 신장 트리 (BFS Span.. 2021. 2. 2.
알고리즘 - 위상정렬 (Topological Sort) 알고리즘 - 위상정렬 (Topological Sort) DAG(비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 알고리즘으로 위상정렬은 각 정점을 우선순위에 따라 배치한다. 일반적으로 결과는 유일하지 않다. jina-developer.tistory.com/112 자료구조 - DAG (Directed Acyclic Graph) 1. Directed Acyclic Graph란? DAG란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. - 선행자(predecessor), 후행자(successor) : DAG에서 어떤 정점 v.. jina-developer.tistory.com 각 노드들의 진입 차수 계산 진입 차수가 0인 노드들.. 2021. 2. 2.
자료구조 - 비순환 방향 그래프 (DAG, Directed Acyclic Graph) 1. 비순환 방향 그래프란? 비순환 방향 그래프(DAG, Directed Acyclic Graph)란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. 1) 선행자(predecessor), 후행자(successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 경로가 존재하면, vi, vj의 선행자(predecessor), vj는 vi의 후행자(successor)라고 한다. 2) 즉각 선행자(immediate predecessor), 즉각 후행자(immediate successor) DAG에서 어떤 정점 vi, vj에 대해서 vi에서 vj로의 간선이 존재하면, vi를 vj의 즉각 선행자(immediate predecessor), vj.. 2021. 2. 2.
자료구조 - 서로소 집합 1. 서로소 집합이란? 서로소 집합(Disjoint Set)이란 교집합이 공집합인 집합들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조이다. - Union 연산 : 어떤 두 원소 a, b에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산 - Find 연산 : 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환 2. 서로소 집합의 표현(Disjoint Set, Union-Find) 3. 서로소 집합의 구현 및 최적화 1) 초기화 : parent 배열에 i원소에 대한 부모 노드 번호를 저장, 루트 노드인 경우 자기 자신의 번호를 저장 function initialize() for i : 1 ~ N parent[i] = i 2) Union 연산 : 하나.. 2021. 2. 2.
알고리즘 - 에라토스네스의 체 알고리즘 - 에라토스네스의 체 1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수라고 한다. 에라토스네스의 체란, 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식으로 프로그래밍에서는 상당히 효율적인 방법론이다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.) 2부터 시작하여 남아있는 수.. 2021. 2. 2.
알고리즘 - 유클리드 호제법 알고리즘 - 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다. 이를 사용해 최대공배수를 구할 수 있는데, 두 수의 곱을 유클리드 호제법으로 구한 최대공약수로 나누면 그것이 최대공배수이다. jina-developer.tistory.com/77 프로그래머스 Level 2 - N개의 최소공배수 [문제 설명] 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수 .. 2021. 2. 2.
728x90
반응형

티스토리툴바