Review/SW Jungle35 [WEEK03] 서로소 집합 자료구조 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union, find 2개의 연산으로 조작할 수 있음 => union - find 자료구조라 부름 특징 - 서로소 집합 자료구조를 구현할 때 트리 자료구조를 이용하여 집합을 표현하는데 서로소 집합 정보 (합집합 연산)이 주어졌을 때 트리자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같음 1) union(합집합) 연산을 확인하여 서로 연결된 두 노드 A, B를 확인 - A와 B의 루트 노드 A', B'를 각각 찾음 - A'를 B'의 부모노드로 설정 (B'가 A'를 가르키도록 함) 2) 모든 합집합 연산을 처리할 때까지 1)의 과정을 반복 - 일반적으로 find, union 연산을 활용하면 .. 2022. 10. 13. [WEEK03] 위상정렬 Topology Sort 방향그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 특징 - 정렬 알고리즘의 일종으로 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 - 예를 들면 '선수과목을 고려한 학습순서 설정'을 들 수 있음 - 진입차수 (indegree) ? 특정한 노드로 '들어오는' 간선의 개수 - 위상 정렬은 여러 개의 답이 존재할 수 있음 - DAG(Directed Acyclic Graph)에서만 적용 DAG? 사이클이 발생하지 않는 방향 그래프 - 위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 있음 1. 현재 그래프는 위상정렬이 가능한지 2. 위상정렬이 가능하다면 그 결과는 무엇인지 알고리즘 진행과정 1. 진입차수가 0인 노드를 큐에 넣.. 2022. 10. 13. [WEEK03] 최단경로 - 다익스트라 / 플로이드워셜 1. 다익스트라(Dijkstra) - 그래프에서 여러개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - '음의 간선'이 없을 때 정상적으로 작동 - 현실세계의 길에서는 음의 간선이 표현되지 않으므로 다익스트라 알고리즘은 실제 GPS 소프트웨어의 기본알고리즘으로 채택됨 구현과정 1. 출발 노드를 설정 2. 최단거리 테이블을 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신 5. 위의 과정에서 3번과 4번을 반복 - '각 노드에 대한 현재까지의 최단거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신 - 매번 현재 처리하고 있는 노드를 기준으.. 2022. 10. 11. [WEEK03] BFS & DFS (+전위/중위/후위순회) 순서트리의 노드를 스캔하는 방법은 크게 두가지로 BFS와 DFS가 있음 1. BFS Breadth-First-Search - 가로검색, 수평검색 - 한 레벨 다음에 다음 레벨로 넘어가는 순서 - 가까운 노드부터 탐색하는 알고리즘 - 큐를 이용 / 구현은 큐 자료구조를 이용 동작방식 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3. 2번의 과정을 더이상 수행하지 못할 때까지 반복 시간복잡도 - 탐색을 수행함에 있어 O(N)의 시간이 소요됨 - 실제 수행시간의 경우 DFS보다 좋음 - DFS는 재귀적으로 들어가기 때문에 실제 프로그램 수행시간은 느려질 수 있음 소스코드 # 출처 : 이코테 from c.. 2022. 10. 11. [WEEK03] 신장트리와 최소신장트리 (크루스칼 + 프림 알고리즘) 1. 신장트리 Spanning Tree - 신장트리는 그래프 알고리즘 문제로 자주 출제되는 문제유형 - 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 - 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 함 최소신장트리 알고리즘 (MST; Minimum Spanning Tree) - 신장트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 2. 크루스칼 알고리즘 특징 - 대표적인 최소신장트리 알고리즘 중의 하나 - 그리디 알고리즘으로 분류 - 모든 간선에 대해 정렬을 수행한 뒤에 가장 짧은 간선부터 집합에 포함시킴 (이때 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음 => 최적의 해 보장) .. 2022. 10. 10. [WEEK03] 그래프와 트리 (+인접행렬 / 인접리스트 / 이진트리) 1. 그래프 특징 - 노드와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 - '서로 다른 개체 혹은 객체가 연결되어 있음' 혹은 '여러 개의 도시가 연결되어 있음' 내용이 나오면 그래프 알고리즘을 일단 생각 용어의 정리 1) 정점 (Vertex / Node) : 각각의 노드를 의미 2) 간선 (Edge / Link) : 그래프에서 각 정점들을 연결하는 선 : 화살표 표시 혹은 그냥 직선 3) 가중치 (Weight) : 간선 위에 표시된 숫자 : 비용을 표현하는 것 등에 쓰임 4) Directed Graph / Undirected Graph : 방향성 혹은 무방향성 그래프 5) Adjacency : 방향성 있는 그래프에서 간선으로 연결된 인접 정점 6) Degree out-degree.. 2022. 10. 10. 이전 1 2 3 4 5 6 다음
