Brute force Study

강한 연결 요소동영상 서비스 사이트에서 다양한 채널 구독자 간의 공통점에 대한 통계를 작성하여, 서로 연관이 있는 구독 정보 그룹으로 나누려고 한다. 이 때 방향 그래프에서 나타나는 공통적인 특징을 이용하여 이러한 복잡한 문제를 해결할 수 있다. 방향 그래프에서 에지는 명시적인 "방향" 정보를 가진다. 방향 그래프에서 에지는 한쪽 방향으로만 이동할 수 있기 때문에 그래프의 특정 정점에 도달할 수 있는지 여부는 탐색을 어느 정점에서 시작했는지에 따라 다르게 결정된다.주어진 그래프를 여러 개의 구역으로 나누되 같은 구역 안의 정점끼리는 서로 이동 가능한 경로를 갖도록 나눌 경우, 각 구역은 해당 그래프의 강한 연결 요소를 나타낸다. 방향 그래프와 무방향 그래프에서 연결성무방향 그래프에서 연결 요소(conne..

벨만 포드 알고리즘그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾는다 (V는 정점의 개수)음수 가중치가 있는 그래프를 다룰 때 벨만 포드 그래프를 사용할 수 있다.다익스트라 알고리즘에 비해 높은 점근적 시간 복잡도를 가지지만, 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공한다. 벨만-포드 알고리즘 구현각 정점의 최단 거리 값 배열을 반환하는 함수struct Edge{ int src; int dst; int weight;};const int UNKNOWN = INT_MAX;vector BellmanFord(vector edges, int V, int start){ vector distance(V, UNKNOWN..

단일 시작 최단 경로 문제"주어진 그래프에서 시작 정점과 목적 정점이 주어질 때 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하는 문제" 다익스트라 알고리즘이란?음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변형한 형태이다.프림 알고리즘과 다익스트라 알고리즘의 차이점프림 알고리즘 : 경계로부터 최소 거리의 정점의 거리 값으로 설정. 모든 정점을 방문해야 종료다익스트라 알고리즘 : 시작 정점으로부터 각 정점까지의 전체 거리를 사용. 목적 정점이 나타나면 종료 다익스트라 알고리즘의 동작모든 정점의 거리 값을 무한대로 초기화한다. 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 ..

MST 문제란?정점 집합 V와 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 Cf) 크루스칼 알고리즘그래프의 모든 에지를 최소 힙에 추가하고 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성한다 프림 알고리즘은?BFS의 동작 방식과 유사하다.먼저 시작 정점을 이용하여 경계를 구성한다경계는 이전에 방문했던 정점들에 의해 구성된다현재 경계에 인접한 정점을 반복적으로 탐색한다이 때 경계를 관통하는 에지 중에서 가장 가중치가 적은 에지를 선택하고, 이 에지이 연결된 정점을 방문한다'프림 알고리즘을 구현하려면 그래프의 각 정점에 경계로부터의 거리(distance)정보를 기록해야 한다. 프림 알고리즘..

이분 그래프란?정점을 두 개의 집합으로 나눌 수 있는 그래프그래프의 모든 에지는 서로 다른 집합에 속한 정점끼리 연결되어야 한다.ex) 학생 목록과 수업 목록을 모델링하는 경우ex) 스트리핑 플랫폼에서 영화 목록과 시청자 사이의 관계를 모델링하는 경우최대 매칭 또는 최소 정점 커버 문제와 같은 NP-완전 문제들이 이분 그래프에서는 다항시간으로 풀 수 있다.따라서 주어진 그래프가 이분 그래프인지 아닌지 판별하는 것은 매우 중요하다 이분 그래프의 구현DFS를 변형하여 만들 수 있다.1번 정점부터 DFS를 시작한다고 가정한다(1번 정점을 스택에 추가한다)스택에 방문하지 않은 정점이 남아있다면 스택에서 정점을 하나 꺼내고 이를 현재 정점으로 설정한다이전 정점에 할당된 색상이 검은색이면 현재 정점에 빨간색을 할당..

깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)는 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.DFS 구현BFS에서는 방문하지 않은 정점을 저장하기 위해 큐를 사용했다.큐를 사용하기 때문에 가장 가까이에 있는 정점부터 접근이 가능했다.하지만 DFS는 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하기 때문에, 스택을 사용한다.후입 선출 속성을 갖는 스택을 사용하기 때문에 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합하다.PS에서 그래프를 나타내야하는 경우 인접 행렬..

그래프 순회 문제그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제EX) 사무실에서 출발하여 주변 거래처를 순회하며 결재를 하는 경우그래프에서 특정 정점을 찾기 위한 용도로 사용될 수 있기 때문에 그래프 탐색 문제라고도 부른다.여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문하다.너비 우선 탐색(BFS, Breadth-First Scrach)시작 정점을 경계(frontier)에 추가하는 것으로 시작경계는 이전에 방문했던 정점들에 의해 구성된다그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다같은 거리에 있는 정점들의 방문 순서는 임의로 정해도 되지만, 멀리 있는 정점보다는 가까운 정점을 먼저 방문해야 한다.BFS는 모든 정점에 대해 자식 정점을 손자 정점보..