본문 바로가기

컴퓨터공학기초 개념/알고리즘 개념38

Advanced Algorithm - MST(Union-Find Algorithm)(2) * 본 포스팅은 이전 포스팅과 이어지는 내용입니다. [복습] 최소신장트리(MST)의 개념 - 어떤 그래프를 기반으로 만들어진, 간선의 총 가중치(비용)가 최소이며 사이클 없이 모든 노드가 연결된 트리 최소신장트리의 대표 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 크루스칼 알고리즘 - 어떤 그래프를 기반으로 MST를 만들기 위한 알고리즘 - 모든 간선의 가중치를 오름차순으로 정렬하고 가중치가 낮은 간선부터 사이클이 생기지 않는 조건하에 모든 노드를 연결 - 사이클의 발생유무를 판단하기 위해서 크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘 - 크루스칼 알고리즘에서 노드간의 연결을 통해 발생.. 2020. 9. 30.
Advanced Algorithm - MST(concepts of the MST)(1) 1. 신장 트리(Spanning Tree)란? - 그래프 내부의 모든 노드가 연결되어 있으며, 동시에 트리의 속성을 만족하는 그래프를 의미한다. 그래프의 모든 노드가 서로 연결되어 있다.(거리는 멀어도 접근경로가 있다.) 트리의 속성을 만족한다.(사이클이 없음) 2. 최소 신장 트리(Minimum Spanning Tree)란? - 하나의 그래프를 기반으로 파생된 신장트리 중에서, 간선의 가중치 합이 최소인 신장트리를 의미한다. - Minumun Spanning Tree의 약자로 MST라고 부른다. 3. MST 대표 알고리즘 - MST 알고리즘이란, 어떤 그래프를 가지고 MST를 구하는 방법을 의미한다. - 대표적으로 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Al.. 2020. 9. 29.
Advanced Algorithm - 최단경로(Shortest Path) 알고리즘(2) * 해당 포스팅은 최단경로(Shortest Path) 알고리즘(1)과 이어지는 내용입니다. 1. 파이썬을 이용한 다익스트라 알고리즘 구현(우선순위 큐 활용) a) heapq 라이브러리를 활용하여 우선순위 큐 사용하기 # heapq 라이브러리를 이용한 우선순위 큐 작성 import heapq queue = [] # heappush(자료구조, 삽입할 데이터) - queue라는 자료구조에 MinHeap 형태로 데이터를 삽입한다. # 거리를 key로 노드명을 value로 사용한다. heapq.heappush(queue, [2,'A']) heapq.heappush(queue, [5,'B']) heapq.heappush(queue, [1,'C']) heapq.heappush(queue, [7,'D']) [테스트 및.. 2020. 9. 28.
Advanced Algorithm - 최단경로(Shortest Path) 알고리즘(1) 1. 최단경로 알고리즘이란? - 그래프에서 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘이다. - 가중치 그래프(weighted graph)에서 간선(edge)의 가중치 합이 최소인 경로를 찾는 것이 목적이다. 2. 최단경로 문제의 종류 a) 단일 출발 및 단일 도착(Single-source & single-destination shortest path problem) - 그래프 내의 특정 노드 A에서 출발하여 또 다른 특정 노드 B에 도착하는 가장 짧은 경로를 찾는 문제 b) 단일 출발(Single-source shortest path problem) - 그래프 내의 특정 노드 A와 A를 제외한 그래프 내 모든 노드 각각의 가장 짧은 경로를 찾는 문제 c) 전체 쌍(all-pair) 최단경로 - 그래.. 2020. 9. 27.
Advanced Algorithm - 탐욕(Greedy) 알고리즘 1. 탐욕 알고리즘 이란? - 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘이다. - 여러가지 경우 중 하나를 결정해야할 때, 상황에 따라 매순간 최선의/최적의 경우를 선택하여 최종적인 값을 구하는 방식이다. - 다시 말해, 문제를 풀기위해 최선의 경우를 선택하는 방식 2. 탐욕 알고리즘의 예 a) 동전 문제 - 지불해야 하는 값이 4720원 일 때, 1원 40원 100원 500원짜리 동전을 사용하여 가장 적은 동전 수를 이루는 조합을 찾아라. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 된다. coin_list = [1,50,100,500] def min_coin_count(value, coin_list):.. 2020. 9. 26.
Advanced Algorithm - 깊이 우선 탐색(Depth First Search) 1. 깊이 우선 탐색(DFS)이란? - 방향과 상관없이 오른쪽 또는 왼쪽 노드를 기준으로, 한 노드의 자식노드를 타고 끝까지 순회한 후 다시 돌아와서 다른 형제들의 자식을 타고 내려가는 방식으로 순회하는 탐색 a) DFS 예시 DFS 동작방식: A - B - D - E - F - C - G - H - I - J 2. DFS 알고리즘 동작방식의 이해 - DFS 알고리즘은 Stack과 Queue를 이용하여 구현할 수 있다. - need_visit Stack과 visited Queue를 사용하여 구현한다. - stack의 특성(LIFO)으로 인해 BFS와는 다르게 need_visit Stack에서 꺼내오는 데이터는 가장 나중에 삽입된 데이터다. 3. DFS 알고리즘 코드구현 def dfs(graph, star.. 2020. 9. 25.
Advanced Algorithm - 너비 우선 탐색(Breadth First Search) 1. 그래프 탐색 알고리즘이란? - 그래프를 기반으로 특정 노드를 찾아가기 위한 알고리즘 - 이 그래프 알고리즘에는 2가지 대표 알고리즘이 있다. 너비 우선 탐색(Breadth First Search) - 정점(노드)과 같은 레벨에 있는 노드(=형제 노드)를 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search) - 정점(노드)의 자식노드를 먼저 탐색하는 방식 a) 너비 우선 탐색(BFS)의 예 - 방향과 상관없이 왼쪽 또는 오른쪽 노드를 기준으로, 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드(형제 노드)를 먼저 순회하는 탐색 BFS 이동순서: A - B - C - D - G - H - I - E - F - J b) 깊이 우선 탐색(DFS)의 예 - 방향과 상관없이 왼쪽 또는.. 2020. 9. 24.
Advanced Algorithm - 그래프의 이해(basic concepts of the graph) 1. 그래프(Graph) 란? - 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위한 방법 ex) 집에서 회사로가는 경로를 그래프로 표현 a) 그래프 관련 용어 정리 노드(Node): 위치를 말함, 정점(Vertex)라고도 함 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) 정점(vertex) 또는 인접 정점 (Adjacent Vertex): 간선과 직접 연결된 정점(또는 노드) ex) 집과 지하철, 집과 버스, 버스와 회사, 지하철과 회사 추가 참고 용어 - 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 (In-Degree): 방.. 2020. 9. 23.
Advanced Algorithm - 순차 탐색(Sequential Search) 1. 순차 탐색이란? - 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교하여 원하는 데이터를 찾는 방법 2. 코드구현 a) random 라이브러리를 이용하여 리스트 생성 import random data_list = random.sample(range(100), 10) print(data_list) b) Sequential Search 함수 구현 def sequential(data_list, search_data): for index in range(len(data_list)): if data_list[index] == search_data: return index return -1 c) 테스트 3. 순차 탐색의 시간복잡도 - 찾는 데이터가 리스트에 존재하지 않는다면, 최악의 경우 O(n)만큼의 시간복.. 2020. 9. 22.

티스토리툴바