Algorithm
11. [Algorithm] 위상 정렬 (그래프 이론)
11. [Algorithm] 위상 정렬 (그래프 이론)
2023.03.27위상 정렬 (Topological Sorting) 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다. 예시를 통해 확실하게 이해해보도록 하자. 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 → 알고리즘 → 고급알고리즘 (O) 순서로 과목을 들어야 한다. 만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣게 되면, 올바른 학습순서가 아니다. 진입차수와 진출차수 위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입..
10. [Algorithm] 크루스칼 알고리즘 (그래프 이론)
10. [Algorithm] 크루스칼 알고리즘 (그래프 이론)
2023.03.27크루스칼 알고리즘 (Kruskal Algorithm) 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘' 이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘 이 있다. 크루스칼 알고리즘 을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘 이다. 그리디 알고리즘으로 분류된다. 그렇다면, 신장 트리란 무엇인가? 신장 트리 란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. → 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리 의 성립 조건이기도 함. 신장 트리는 알겠고.. 그러면 최소 신장 ..
9. [Algorithm] Union-Find 알고리즘 (서로소 집합 Disjoint-Set)
9. [Algorithm] Union-Find 알고리즘 (서로소 집합 Disjoint-Set)
2023.03.24Union-Find Disjoint-Set을 구현할 때 사용하는 알고리즘 집합을 구현하는데 비트 벡터, 배열, 연결리스트를 사용할 수 있으나, 가장 효율적인 트리 구조를 이용하여 구현함 크루스칼 알고리즘에서 그래프의 최소 신장 트리(MST: Minimum Spanning Tree)를 찾는데 활용된다. (정점 연결 및 사이클 형성 여부 확인) 초기에 {0}, {1}, {2}, ... {n}이 각각 n + 1 개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우. 집합의 표현 - 백준1717번 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우. 친구 네..
8. [Algorithm] 플로이드 워셜 알고리즘 (최단 경로)
8. [Algorithm] 플로이드 워셜 알고리즘 (최단 경로)
2023.03.24플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 지난 시간에 포스팅 했던 다익스트라 알고리즘의 경우, 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에는 어떻게 해야할까? 바로 플로이드 워셜 알고리즘을 사용하면 된다. '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘 다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 이후 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다. ←→ 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만, ..
7. [Algorithm] 다익스트라 알고리즘 (최단 경로)
7. [Algorithm] 다익스트라 알고리즘 (최단 경로)
2023.03.24다익스트라 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘 유형에는 다양한 종류가 있다. 대표적으로 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 이렇게 3가지이다. 이번 글에서는 다익스트라 알고리즘 에 대해서 알아보도록 하겠다. 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 그래프에서 여러 개이 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 다익스트라는 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하는데, 이 때문에 기본적으로 그리디 알고리즘으로 분류된다. 다익스트라 알고리즘의 원리 출발 노드를 설정 최단 거리 테이블을 초기화 방문하지 ..
6. [Algorithm] 다이나믹 프로그래밍
6. [Algorithm] 다이나믹 프로그래밍
2023.03.21다이나믹 프로그래밍 DP란 '동적 계획법' 이라고도 불리는 알고리즘 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 / 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 DP는 다음의 조건을 만족할 때 사용 할 수 있음 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 하는 경우 ※ 일반적인 프로그래밍 분야에서 동적(Dynamic)의 의미는? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 을..