'알고리즘/🗂️ 정리' 카테고리의 글 목록 (2 Page)

Bellman-Ford (벨만-포드)

2023.09.08

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다. 👀 특징 음의 가중치를 갖는 간선도 존재 가능하다. 음의 사이클의 존재 여부를 확인할 수 있다. 최단거리를 구하기 위해서는 V-1번 E개의 모든 간선을 확인한다. 음의 사이클 존재 여부를 확인하기 위해 한 번 더 E개의 간선을 확인한다. 총 연산 횟수 = VxE ⌛️ 시간 복잡도 = O(VE) V번째 모든 간선을 확인했을 때 거리배열이 갱신되었다면 그래프 G는 음의 사이클을 가지는 그래프이다. 위와 같이 음의 가중치를 갖고 있는 그래프가 있을 때, 다익스트라로 정점 1에서 모든 정점까지의 거리를 구현한다면 1 ➔ 2 = 1 1 ➔ 2 ➔ 3 = 2 1 ➔ 2 ➔ 3 ➔ ..

알고리즘/🗂️ 정리

LCA (최소공통조상)

2023.09.04

LCA는 Lowest Common Ancestor의 약자로 최소 공통 조상을 찾는 알고리즘이다. 트리구조에서 사용되며 두 정점 u, v에서 가장 가까운 공통 조상을 찾으면 된다. 이 그래프에서 13번 정점과 15번 정점의 최소공통조상은 5번 정점이다. 11번 정점과 13번 정점의 최소공통조상은 1번 정점이다. 이런 상황에서 12번 정점과 14번 정점의 최소공통조상은 12번 정점이다. 🕹️ LCA 과정 1️⃣ 입력받은 정점과 간선으로 양방향 그래프 (트리구조) 를 생성한다. 2️⃣ BFS나 DFS를 사용하여 depth를, DP를 활용하여 parent 정보를 저장하는 트리를 생성한다. 3️⃣ LCA(u, v) 메서드를 호출하여 u와 v의 최소공통조상을 찾는다. u와 v 중에서 깊이가 더 깊은 정점을 얕은 깊..

알고리즘/🗂️ 정리

Binary Search (이분탐색)

2023.09.01

Binary Search는 정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 원하는 값을 얻는 알고리즘이다. 리스트가 반드시 정렬되어 있어야 하며, 3개의 변수 (low, mid, high)를 사용해서 값을 탐색한다. 중앙값(mid)을 기준으로 비교하여 low와 high 값을 정하고, 이 과정을 반복해서 값을 얻어내면 된다. 탐색 범위가 반으로 줄어들면서 start와 end 값을 정하는 과정을 거치기 때문에 시간복잡도가 낮고, 순차적 탐색보다 빠른 탐색이 가능하므로 배열의 원소 개수가 많을 때 주로 사용된다. 🕹️ Binary Search 과정 1️⃣ 배열의 중간 값을 계산하여 찾고자 하는 값과 비교한다. 중간 값은 (low+high)/2 로 계산한다. 2️⃣ 중간 값이 찾고자 하는 값보다 작다면 중간값보다..

알고리즘/🗂️ 정리

Floyd-Warshall (플로이드 워셜)

2023.08.29

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 모든 정점 사이의 최단경로를 구하는 알고리즘으로 (모든 노드 간에 최단거리를 구하는 알고리즘) 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 구하는데 사용된다. 음수인 가중치를 갖는 간선이 존재해도 된다. 어떤 두 정점 사이의 최단 경로는 어떤 경유지(K)를 거치거나 거치지 않는 경로 중 하나이다. ex). 정점 A와 정점 B 사이의 최단 경로 = A-B 또는 A-K-B 만약, 경유지를 거친다면 최단 경로를 이루는 부분 경로 또한 최단 경로이다. ex). A-K와 K-B 또한 최단경로 👀 특징 순환만 없다면 음수 가중치도 가능하다 기본적으로 동적계획법(DP)으로 접근한다. ⌛️ 시간복잡도 : θ(V³) (V는 노드..

알고리즘/🗂️ 정리

Union Find (유니온 파인드)

2023.08.29

그래프 (트리) 알고리즘으로 두 노드가 같은 그래프에 속해있는지 판별 Union 연산 & Find 연산 union(x, y) : 노드를 합치는 연산 find(x) : x가 어느 그래프에 속해 있는지 판별하는 연산 (노드의 루트 노드 탐색) 🕹️ 유니온 파인드 과정 현재 5개의 노드는 서로 연결되어있지 않은 상태이므로 부모는 자기 자신을 가리키고 있다. (부모 노드 초기화) x는 노드 번호이고, parent[x]는 x가 어떤 부모 노드에 속해 있는지 나타낸다. 1️⃣ union(1, 2) 노드 1과 노드 2를 합친다. 노드 2의 부모 노드는 1이 되었다. parent[2] = 1 2️⃣ union(3, 4) / union(3, 5) 노드 3과 노드 4를 합치고, 노드 3과 노드 5를 합친다. 노드 4와 노..

알고리즘/🗂️ 정리

Dijkstra (다익스트라)

2023.03.03

DP(다이나믹 프로그래밍)를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 문제에서 사용된다. 최단 거리는 여러 가지 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하는 특징이 있다. 🕹️ 다익스트라 알고리즘 과정 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 해당 노드 거쳐서 특정한 노드로 가는 경우 고려하여 최소 비용 갱신 3️⃣, 4️⃣번 반복 기본적인 다익스트라 - 선형탐색 public class Main{ static int INF = 10000..

Bellman-Ford (벨만-포드)

LCA (최소공통조상)

Binary Search (이분탐색)

Floyd-Warshall (플로이드 워셜)

Union Find (유니온 파인드)

Dijkstra (다익스트라)

티스토리툴바