푸으름

Algorithm 공부 #16 - 다익스트라 알고리즘  ✏️ 다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프 상에서 한 정점에서 다른 정점들간의 최단 거리를 구할 수 있는 알고리즘이다.즉 도착 정점 뿐만 아니라 모든 다른 정점가지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다.매번 최단 경로의 정점을 선택해 탐색을 반복한다고 생각하면 될 것 같다.시간복잡도는 O(ElogV)이며 이때 특징으로는 에지값이 모두 양수여야 한다.최단 거리 알고리즘은 이외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있는데 이 알고리즘들은후에 포스팅을 할 예정이다.  ✏️ 구현 방법출발 노드와 도착 노드를 설정'최단 거리 테이블'을 초기화(출발 지점을 0으로, 나머지는..

Algorithm 공부 #15 - 그래프(위상 정렬) 위상 정렬(Topology Sort) ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 ● 항상 유일한 값으로 정렬되지 않음 ● 진입 차수 : 자기 자신을 가리키는 에지의 개수 ● 원리 파악하기 노드는 5개이고 각 노드는 1,2,3,4,5 1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를 4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기 진입차수 배열 D[N] 1 2 3 4 5 0 1 1 2 2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기 이 과정을 모든 노드의 ..

Algorithm 공부 #14 - 유니온 파인드  ✏️ 유니온 파인드(Union Find)유니온 파인드는 합집합이라는 의미를 지니고 있으며, Disjoint Set이라고도 불린다. Disjoint Set은 상호 베타적 집합이라는 뜻을 가지고 있는데 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용한다.상호 배타적이라는 단어가 헷갈릴 수 있는데, 그냥 부분 집합 간의 교집합에는 원소가 없고, 모든 부분 집합들의 합집합은 전체 집합과 같다는 뜻이다. 쉽게 말해서 여러 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다고 생각하면 될 것 같다. ✏️ Union 연산Union 연산은 말 그대로 Union(합집합)을 만드는 과정이다..

Algorithm 공부 #13 - 그래프(그래프의 표현) 에지 리스트(edge list) ● 에지를 중심으로 그래프를 표현 ● 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 ● 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현 인접 행렬(adjacency matrix) ● 2차원 배열을 자료구조를 이용하여 그래프를 표현 ● 노드를 중심으로 그래프를 표현 ● 노드와 관련되어 있는 에지를 탐색하기 위해서는 N번 접근해야 하므로 시간복잡도가 인접 리스트에 비해 느림 ● 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 인접 리스트(adjacency list) ● 2차원 벡터로 그래프를 표현 ● 구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 뛰어나며, 노드 개수가..