본문 바로가기
728x90
반응형

algorithm11

알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) jina-developer.tistory.com/114 자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 jina-developer.tistory.com 1. 크루스칼 알고리즘(Kruskal's Algorithm) 1) 순서 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연.. 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.
알고리즘 - 유클리드 호제법 알고리즘 - 유클리드 호제법 유클리드 호제법은 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.
알고리즘 - 너비 우선 탐색 (Breadth First Search) 알고리즘 - 너비 우선 탐색 (Breadth First Search) BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. [ BFS 활용 ] 최단경로 찾기, 위상정렬 등 [ pseudocode로 BFS 구현 ] BFS(G, s) for each vertex u ∈ G.V - {s} //초기화 작업 u.color = WHITE//s를 제외한 모든 정점의 상태를 white로, u.d = ∞//거리를 무한대로 u.𝝅 = NIL .. 2021. 1. 27.
알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) 알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 미로에서 갈림길로 돌아가서 길을 찾는 것을 생각하면 된다. DFS를 설명하기 전에, 먼저 그래프의 기본 구조를 알아야 한다. https://jina-developer.tistory.com/108 자료구조 - 그래프 1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 jina-developer.tistory.com 모든 노드를 .. 2021. 1. 27.
자료구조 - 배열(Array) 1. 배열이란? 배열(Array)은 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조로 연속된 메모리 공간에 순차적으로 저장한다. 배열의 크기는 고정되어 있고, 선언할 때 크기를 정하고 후에 변경할 수는 없다. 2. 시간 복잡도 1) 삽입 / 삭제 - 배열의 맨 앞에 삽입 / 삭제하는 경우 : O(n) - 배열의 맨 뒤에 삽입 / 삭제하는 경우 : O(1) - 배열의 중간에 삽입 / 삭제하는 경우 : O(n) 2) 탐색 - O(n) 3. 장단점 1) 장점 - 인덱스를 가지고 있어 바로 접근 가능하다. (자료의 크기가 클수록 매우 유리) - 연속된 메모리 공간에 존재하기 때문에 관리가 편리하다. - 구조가 간단하여 프로그램 작성이 쉽다. 2) 단점 - 데이터 삽입 / 삭제가 어렵다... 2021. 1. 26.
728x90
반응형

티스토리툴바