다이나믹 프로그래밍 (2) - P/NP,플로이드-워셜 알고리즘

1. P와 NP

• 입력 데이터 크기가 증가함에 따라 문제 해결의 복잡도가 어느 정도까지 향상되는지 파악
• P 문제 : 다항 시간내에 해답을 구할 수 있음을 의미
  • 시간 복잡도가 $O(n), O(n^2), O(log n)$
• NP 문제 : 비결정적 다항 시간문제
• 주어진 문제의 솔루션을 검증하는 것은 쉬우나 실제 솔루션을 만드는 일은 매우 어려움
• NP의 많은 문제들은 NP-완전으로 알려져 있음
  • 특별한 특성을 공유
  • 다항 시간처럼 효율적으로 해결하는 솔루션이 발견 → 다른 문제에도 적용 가능

2. 부분집합의 합 문제 다시보기

• 특정 부분집합에 대한 유효성 검증은 각 부분집합의 원소를 모두 더하여 목표치와 같은지를 검사하는 방식
• 검증에 대한 복잡도는 부분집합 크기에 대해 선형 관계 만족
• 부분집합의 합 문제를 O(n*m) 형태의 다항 시간 복잡도로 해결하는 방법 설명 (이전 게시글)
  • m은 부분집합의 합 목표치로 해당 값이 두 배가 될 경우 연산은 두 배로 증가
  • 부분집합의 합 문제는 의사 다항 시간으로 동작하며 NP-완전 문제라고 결론지을 수 있음

3. 배낭 문제

• 대표적인 NP-완전 문제

1) 0-1 배낭 문제 - 부분집합의 합 문제 확장하기

• 부분집합의 합 문제의 상태 변환 로직과 유사한 공통점 발견
• i 번째 물건의 무게가 w이고 가격이 v라면 다음 중 하나를 수행 가능
  1. 기존에 선택된 물건들의 무게에 w를 더한 결과가 최대 용량보다 같거나 작을 경우, 기존에 선택된 물건들의 가격 합에 v를 더함
  2. 기존에 선택된 물건들의 가격 합을 그대로 유지
• 가격이 v이고 무게가 w인 ( i+1 )번째 물건을 고려할 때, 선택된 물건들의 무게 합 W인 경우의 최대 가격 합은 다음 중 하나로 결정
  1. i번째 물건에 대해 선택된 물건들의 무게 합이 W인 경우의 최대 가격 합
  2. i번째 물건에 대해 선택된 물건들의 무게 합이 W - w인 경우의 최대 가격합에 v를 더한 값
• DP 테이블을 체우는 의사코드
• i번째 인텍스에서 total_weight ( 1≤ total_weight ≤ max_capacity ) 값에 대해:
  • 만약 total_weight < weight[i]이면:
    • DP(i, total_weight) = DP(i -1, total_weight)
  • 그렇지 않으면:
    • DP(i, total_weight) = 다음 중 최댓값:
      1. DP(i-1, total_weight)
      2. DP(i-1, total_weight - weight[i]) + value[i]

2) 연습 문제 41: 0-1 배낭 문제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Knapsack_01(int items, int capacity, vector<int> values,
	vector<int> weight)
{
	vector<vector<int>> DP(items + 1, vector<int>(capacity + 1, 0));

	for (int i = 1; i <= items; i++)
	{
		int currentWeight = weight[i - 1];
		int currentValue = values[i - 1];

		for (int totalWeight = 1; totalWeight <= capacity; totalWeight++)
		{
			if (totalWeight < currentWeight)
			{
				DP[i][totalWeight] = DP[i - 1][totalWeight];
			}
			else
			{
				DP[i][totalWeight] = max(DP[i - 1][totalWeight],
					DP[i - 1][totalWeight - currentWeight] + currentValue);
			}
		}
	}

	return DP[items][capacity];
}

int main()
{
	int items, capacity;
	cin >> items >> capacity;

	vector<int> values(items), weight(items);

	for (auto& v : values) cin >> v;
	for (auto& w : weight) cin >> w;

	int result = Knapsack_01(items, capacity, values, weight);

	cout << "배낭에 채울 수 있는 물건들의 최고 가격: " << result << endl;
}

3) 무한 개수 배낭 문제

• 각 물건을 개수 제한 없이 배낭에 담을 수 있는 무한 개수 배낭 문제

1. (i-1)번쨰 물건과 total_weight 무게를 고려할 떄 최대 가격 합
2. (i-1)번째에서 선택된 물건들의 무게에 current_weight을 더하여 total_weight가 형성되었다고 가정할 경우:
   1. (i-1)번째에서 선택된 물건들의 무게가 total_weight - current_weight일 때의 최대 가격 합에 현재 물건 가격을 합한 값
   2. 현재 선택된 물건들의 무게가 total_weight - current_weight일 때의 최대 가격 합에 현재 물건 가격을 합한 값

• 상태 공간 축소
  • 문제의 상태를 표현하기 위해 사용하는 공간의 크기가 최소화하도록 알고리즘을 재구성하는 작업

4) 연습 문제 42: 무한 개수 배낭 문제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int UnboundedKnapsack(int items, int capacity, vector<int> values, 
	vector<int> weight)
{
	vector<int> DP(capacity + 1, 0);

	for (int w = 0; w <= capacity; w++)
	{
		for (int i = 0; i < items; i++)
		{
			if (weight[i] <= w)
			{
				DP[w] = max(DP[w], DP[w - weight[i]] + values[i]);
			}
		}
	}

	return DP[capacity];
}

int main()
{
	int items, capacity;
	cin >> items >> capacity;

	vector<int> values(items), weight(items);

	for (auto& v : values) cin >> v;
	for (auto& w : weight) cin >> w;

	int result = UnboundedKnapsack(items, capacity, values, weight);

	cout << "배낭에 채울 수 있는 물건들의 최고 가격: " << result << endl;
}

5) 실습 문제 22: 최대 이익

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Product
{
	int quantity;
	int price;
	int value;

	Product(int q, int c, int v)
		: quantity(q), price(c), value(v) {}
};

int main()
{
	int N, budget, capacity;
	cin >> N >> budget >> capacity;

	vector<Product> products;

	for (int i = 0; i < N; i++)
	{
		int quantity, cost, value;
		cin >> quantity >> cost >> value;

		products.push_back(Product(quantity, cost, value));
	}

	vector<vector<vector<int>>> DP(N + 1, vector<vector<int>>(budget + 1, vector<int>(capacity + 1, 0)));

	for (int i = 1; i <= N; i++)
	{
		Product product = products[i - 1];

		for (int cost = 0; cost <= budget; cost++)
		{
			for (int count = 0; count <= capacity; count++)
			{
				if (cost < product.price || count < product.quantity)
				{
					DP[i][cost][count] = DP[i - 1][cost][count];
				}
				else
				{
					DP[i][cost][count] = max(DP[i - 1][cost][count],
						DP[i - 1][cost - product.price][count - product.quantity] + product.value);
				}
			}
		}
	}

	cout << DP[N][budget][capacity] << endl;
}

4. 그래프와 동적 계획법

1) 벨만-포드 알고리즘 다시보기

• start라는 이름의 시작 정점, 정점 개수 V, 에지 개수 E로 구성된 그래프가 주어지면 다음 단계 수행

1. 0부터 (V-1)번째 정점의 거리 값을 UNKNOWN으로 초기화하고, start 정점의 거리 값을 0으로 설정
2. 1부터 (V-1)까지 반복 수행
3. 각각의 반복에서 모든 에지를 검사하면서 에지의 시작 정점 거리 값이 UNKNOWN인지를 검사하고 만약 해당 에지의 시작 정점 거리가 UNKNOWN이 아니면 에지로 연결된 정점의 거리 값을 시작 정점 거리 값에 에지 가중치를 더한 값과 비교
4. 만약 에지의 시작 정점 거리값에 에지 가중치를 더한 값이 인접한 정점의 거리 값보다 작으면 해당 정점의 거리 값을 더 작은 값으로 갱신
5. (V-1)번의 반복이 끝나면 최단 거리 값이 모두 계산, 모든 에지에 대해 반복을 통해 음수 사이클의 존재를 확인

2) 동적 계획법으로 최단 경로 문제 다루기

• 벨만-포드 알고리즘을 하향식 솔루션으로 변경
• 첫 번째 기저 조건 : depth = 0이면, ShortestPath(node, depth) → UNKNOWN
• 두 번째 기저조건 : node = target이면, ShortestPath(node, depth) → 0
• 중간 상태 정의
  • 현재 정점과 연결된 모든 에지에 대해:
    • edge → neighbor, weight
    • 만약 ShortestPath(neighbor, depth-1) + weight < ShortestPath(node, depth)이면:
      • ShortestPath(node, depth) = ShortestPath(neighbor, depth-1) + weight

3) 연습 문제 43: 단일 시작 최단 경로

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

const int UNKNOWN = 1e9;

int V, E;
vector<vector<int>> weight;
vector<vector<int>> adj;

map<pair<int, int>, int> memo;

int ShortestPath_Memoization(int depth, int node,
	vector<vector<int>>& adj, vector<vector<int>>& weight)
{
	// 맵에 키가 있는지를 확인
	if (memo.find({node, depth}) != memo.end())
	{
		return memo[{node, depth}];
	}

	memo[{node, depth}] = UNKNOWN;

	// 인접한 에지에 대해 반복
	for (auto next : adj[node])
	{
		int w = weight[node][next];
		int dist = ShortestPath_Memoization(depth - 1, next, adj, weight) + w;

		memo[{node, depth}] = min(memo[{node, depth}], dist);
	}

	return memo[{node, depth}];
}

vector<int> SingleSourceShortestPaths(int source)
{
	vector<vector<int>> adj_t(V);
	vector<vector<int>> weight_t(V, vector<int>(V, UNKNOWN));

	memo.clear();

	for (int i = 0; i < V; i++)
	{
		// 전치 그래프 생성
		for (auto j : adj[i])
		{
			adj_t[j].push_back(i);
			weight_t[j][i] = weight[i][j];
		}

		// 기저 조건 - 시작 정점에서 자기 자신까지의 최단 거리는 항상 0

		memo[{source, i}] = 0;

		if (i != source)
		{
			// V-1 반복 후 소스 이외의 노드에 도달한 경우,
			// 경로가 존재하지 않음

			memo[{i, 0}] = UNKNOWN;
		}
	}

	vector<int> distance(V);

	for (int i = 0; i < V; i++)
	{
		distance[i] = ShortestPath_Memoization(V - 1, i, adj_t, weight_t);
	}

	return distance;
}

int main()
{
	cin >> V >> E;

	weight.resize(V, vector<int>(V, UNKNOWN));
	adj.resize(V);

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].push_back(v);
		weight[u][v] = w;
	}

	vector<vector<int>> paths(V);

	for (int i = 0; i < V; i++)
	{
		paths[i] = SingleSourceShortestPaths(i);
	}

	cout << "각 정점 사이의 최단 거리:" << endl;

	for (int i = 0; i < V; i++)
	{
		cout << i << ": ";

		for (int j = 0; j < V; j++)
		{
			(paths[i][j] == UNKNOWN) ? cout << "- "
				: cout << paths[i][j] << " ";
		}
		cout << endl;
	}
}

4) 연습 문제 44: 플로이드-워셜 알고리즘 구현하기

• 그래프의 모든 정점을 중간 정점으로 사용하여 결과 정확도 향상
• 모든 상황에서 최선이라고 보장할 수 없음
• 밀집 그래프서 사용하는 것이 좋음
• 음수 에지 사이클은 별도의 수행 처리

#include <vector>
#include <iostream>

using namespace std;

const int UNKNOWN = 1e9;

vector<vector<int>> FloydWarshall(int V, vector<vector<int>> weight)
{
	vector<vector<int>> distance(V, vector<int>(V, UNKNOWN));

	for (int i = 0; i < V; i++)
	{
		for (int j = 0; j < V; j++)
		{
			distance[i][j] = weight[i][j];
		}

		distance[i][i] = 0;
	}

	for (int mid = 0; mid < V; mid++)
	{
		for (int start = 0; start < V; start++)
		{
			for (int end = 0; end < V; end++)
			{
				if (distance[start][mid] + distance[mid][end] < distance[start][end])
				{
					distance[start][end] = distance[start][mid] + distance[mid][end];
				}
			}
		}
	}

	for (int i = 0; i < V; i++)
	{
		// 자기 자신으로의 거리가 0보다 작으면 음수 가중치 사이클이 있는 것으로 판단
		if (distance[i][i] < 0)
			return {};
	}

	return distance;
}

int main()
{
	int V, E;
	cin >> V >> E;

	vector<vector<int>> weight(V, vector<int>(V, UNKNOWN));

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		weight[u][v] = w;
	}

	vector<vector<int>> distance = FloydWarshall(V, weight);

	if (distance.empty())
	{
		cout << "음수 가중치 사이클이 있습니다." << endl;
		return 0;
	}

	for (int i = 0; i < V; i++)
	{
		cout << i << endl;

		for (int j = 0; j < V; j++)
		{
			cout << "\\t" << j << ": ";

			(distance[i][j] == UNKNOWN) ? cout << "_" << endl
				: cout << distance[i][j] << endl;
		}
	}
}

5) 실습 문제 23: 도로 건설

#include <vector>
#include <iostream>

using namespace std;

const int UNKNOWN = 1e9;
const char EMPTY_SPACE = '.';
const string roads = "-|/\\\\";

struct Point
{
	int x;
	int y;

	Point() : x(0), y(0) {}
	Point(int x, int y) : x(x), y(y) {}

	bool operator !=(const Point& other) const
	{
		return x != other.x || y != other.y;
	}
};

int H, W;
int N;

vector<string> grid;
vector<vector<int>> terrain;
vector<vector<int>> cost;
vector<Point> houses;

int GetDirection(int x_dir, int y_dir)
{
	if (y_dir == 0) return 0;
	if (x_dir == 0) return 1;
	if (x_dir == -1)
	{
		return (y_dir == 1) ? 2 : 3;
	}
	return (y_dir == 1) ? 3 : 2;
}

void DrawPath(int start, int end)
{
	Point a = houses[start];
	Point b = houses[end];

	int x_dir = 0;
	int y_dir = 0;

	if (a.x != b.x)
	{
		x_dir = (a.x < b.x) ? 1 : -1;
	}

	if (a.y != b.y)
	{
		y_dir = (a.y < b.y) ? 1 : -1;
	}

	int direction = GetDirection(x_dir, y_dir);
	char mark = roads[direction];

	do {
		a.x += x_dir;
		a.y += y_dir;

		if (grid[a.y][a.x] == EMPTY_SPACE)
		{
			grid[a.y][a.x] = mark;
		}
		else if (!isalpha(grid[a.y][a.x]))
		{
			// 만약 두 도로가 교차하면 '+' 문자로 대체
			grid[a.y][a.x] = (mark != grid[a.y][a.x]) ? '+' : mark;
		}
	} while (a != b);
}

vector<int> GetPath(int start, int end, vector<vector<int>>& next)
{
	vector<int> path = {start};

	do {
		start = next[start][end];

		path.push_back(start);
	} while (next[start][end] != end);

	return path;
}

void GetShortestPaths()
{
	vector<vector<int>> dist(N, vector<int>(N, UNKNOWN));
	vector<vector<int>> next(N, vector<int>(N, UNKNOWN));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = cost[i][j];

			if (dist[i][j] != UNKNOWN)
			{
				next[i][j] = j;
			}
		}

		dist[i][i] = 0;
		next[i][i] = i;
	}

	for (int mid = 0; mid < N; mid++)
	{
		for (int start = 0; start < N; start++)
		{
			for (int end = 0; end < N; end++)
			{
				if (dist[start][end] > dist[start][mid] + dist[mid][end])
				{
					dist[start][end] = dist[start][mid] + dist[mid][end];
					next[start][end] = next[start][mid];
				}
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		vector<int> path = GetPath(i, N - 1, next);

		int curr = i;

		for (auto neighbor : path)
		{
			DrawPath(curr, neighbor);
			curr = neighbor;
		}
	}
}

bool DirectLine(Point a, Point b)
{
	if (a.x == b.x) return true;
	if (a.y == b.y) return true;
	if (abs(a.x - b.x) == abs(a.y - b.y)) return true;

	return false;
}

int GetCost(int start, int end)
{
	Point a = houses[start];
	Point b = houses[end];

	int x_dir = 0;
	int y_dir = 0;

	if (a.x != b.x)
	{
		x_dir = (a.x < b.x) ? 1 : -1;
	}

	if (a.y != b.y)
	{
		y_dir = (a.y < b.y) ? 1 : -1;
	}

	int cost = 0;

	do {
		a.x += x_dir;
		a.y += y_dir;

		cost += terrain[a.y][a.x];
	} while (grid[a.y][a.x] == EMPTY_SPACE);

	return (a != b) ? UNKNOWN : cost;
}

void BuildGraph()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (i == j) continue;

			// 두 집이 수평, 수직, 대각 위치에 있는지 확인
			if (DirectLine(houses[i], houses[j]))
			{
				// 두 집 사이의 도로 건설에 필요한 비용 계산
				cost[i][j] = cost[j][i] = GetCost(i, j);
			}
		}
	}
}

void Input()
{
	cin >> H >> W;
	cin >> N;

	grid.resize(H);
	houses.resize(N);
	terrain.resize(H, vector<int>(W, UNKNOWN));
	cost.resize(N, vector<int>(N, UNKNOWN));

	// 지도 정보
	for (int i = 0; i < H; i++)
	{
		cin >> grid[i];
	}

	// 지반 강도 정보
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> terrain[i][j];
		}
	}

	// 주택 좌표
	for (int i = 0; i < N; i++)
	{
		cin >> houses[i].x >> houses[i].y;

		// 주택 레이블 설정
		grid[houses[i].y][houses[i].x] = char(i + 'A');
	}
}

int main()
{
	Input();
	BuildGraph();
	GetShortestPaths();

	for (auto it : grid)
	{
		cout << it << "\\n";
	}

	return 0;
}

 

 

출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++