벨만 포드 알고리즘그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (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는 모든 정점에 대해 자식 정점을 손자 정점보..

동전 거스름돈(Coin Change) 문제란?동전 거스름돈의 최소 동전 수를 찾는 그리디 알고리즘달성 목표 : 최소 동전 수제한 조건 : 거스름돈의 가치가 같도록 한다 그리디 방식의 동전 거스름돈을 결정하는 해결 문제매 순간마다 남은 거스름돈의 총액을 초과하지 않는 조건하에 ‘greedy, 욕심내어’ 가장 큰 액면의 동전을 취함가장 큰 액면을 가진 동전부터 차례로 선택하여 남은 거스름돈 액수보다 작을 경우 해답에 포함시킨다슈도 코드동전의 액면은 500원, 100원, 50원, 10원, 1원이라고 할 때입력 : 거스름돈 액수 W출력 : 거스름돈 액수에 대한 최소 동전수1. change=W, n500=n100=n50=n10=n1=0 // n500, n100, n50, n10, n1은 각각의 동전 카운트2. w..

웰시-포웰 알고리즘이란앞에서 봤던 그리디 그래프 컬러링 알고리즘은 1번 정점부터 그래프 컬러링을 시작했다.시작한 정점에 따라 사용한 색상의 수가 달라질 수 있다. 이를 조금 향상시키는 방법은 차수(degree, 정점에 연결된 에지의 개수)가 높은 정점부터 차례대로 그래프 컬러링을 수행하는 것이다.이를 웰시-포웰 알고리즘이라고 한다.모든 정점을 차수에 대한 내림차순으로 정렬하고 배열에 저장한다정렬된 배열에서 색상이 지정되지 않은 첫 번재 정점을 선택하고(배열에서 색상이 지정되지 않은 것들 중에서 차수가 제일 높은 것), 이 정점과 연결된 모든 정점을 조사하여, 아직 사용되지 않은 색상을 해당 정점(아까 말한 차수가 제일 높은 정점)에 지정한다. 이 색상을 C라고 지칭하자.정렬된 배열에서 색상이 지정되지 않..

그래프 컬러링 문제란?정의: "주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야 한다"그래프 컬러링의 평가는 얼머나 적은 수의 색상을 사용했는가에 의해 결정된다.택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기 문제 등을 그래프로 모델링 한 후 컬러링 문제로 해결할 수 있다.그래프 컬러링에 필요한 최소 개수의 색상 수를 찾는 것은 NP-완전 문제로 알려져 있다.문제를 조금 변경함으로써 시간 복잡도를 크게 변경할 수 있다.그리디 방식이 유용한 근사치를 제공한다.ex) 컴파일러 설계에서 사용 EX) 스도쿠 퍼즐을 그래프 컬러링 문제로 모델링하기각각의 셀(cell)을 그래프 정점으로 표현한다같은 행, 같은 열, 3X3 블록 안에 있는 모든 정점기리 에지를 연결한다생성된 ..

최소 신장 트리 문제란?정의"정점(vertex)의 집합 V와 가중치를 갖는 에지(edge)의 집합 E로 구성된 그래프 G = (V, E)가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오"신장 트리 :  주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리정점의 수가 n 개이면 신장 트리의 간선 수는 n-1 개최소 신장 트리(MST): 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리ex) 상수도관 네트워크, 도로 네트워크 설계Example)지도상에 여덟 개의 마을이 있고, 모든 마을이 서로 연결될 수 있도록 도로를 설계한다고 해보자. 연결된 도로는 사이클을 구성하면 안 된다.연결된 도로의..