딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/12920

1. 문제설명

0-1 냅색알고리즘을 이용하는 문제이다.

이 문제에서는 아이템이 복수개인 경우가 존재한다.

이를 아이템 하나씩 나눠서 기존의 0-1 냅색 알고리즘을 시행하면 아이템 개수가 많아지기 때문에 시간초과가 난다.

아이템 개수 여러개를 줄여줄 수 있는 방법이 필요하다.

이진수는 모든 정수를 표현함을 이용하면 문제를 해결할 수 있다.

예를 들어 아이템 15개인 경우에는

아이템을 사용할 수 있는 경우의 수는

1, 2, 3, ... 15까지 총 15개가 있다.

이를 다른 방법으로 표현할 수 있다.

아이템을 하나씩 두는 게 아니라

아이템 1개, 아이템 2개, 아이템 4개, 아이템 8개로 덩어리를 만들어 새로운 아이템을 만들면

덩어리 4개로 15개를 표현할 수 있다.

이 문제에 적용하면 만약 무게 3, 만족도 4인 아이템의 개수 K가 10이라 치면

이를 다음과 같은 아이템으로 처리하고 0-1 냅색 알고리즘을 시행하면 된다.

일단 K가 10이므로 덩어리를 만들면

1, 2, 4, 3(2의 배수로 더이상 나눠지지 않으면 나머지는 그냥 둔다)으로 만들 수 있고

무게 3, 만족도 4,

무게 6, 만족도 8

무게 12, 만족도 16

무게 9, 만족도 12

인 아이템이 4개 있다고 생각하고 냅색 알고리즘을 시행하면

결과적으로 초기에 10개 있던 아이템에 대해서 아이템을 0개쓴경우부터 ~ 10개 다쓴경우가 적용되어

문제를 해결할 수 있다.

이렇게 하면 아이템의 총 개수가 log를 씌운 값에 가까워져서 연산을 덜 할 수 있다.

2.문제풀이코드 

#include <bits/stdc++.h>

using namespace std;

int N, M;
int dp[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        int V, C, K;
        cin >> V >> C >> K;

        int cnt = 1;
        while (K > 0) {
            cnt = min(cnt, K);
            for (int j = M; j >= V * cnt; j--) {
                dp[j] = max(dp[j], dp[j - V * cnt] + C * cnt);
            }
            K -= cnt;
            cnt *= 2;
        }
    }
    cout << dp[M] << '\n';

    return 0;
}

처음엔 그래프 거리를 구하는 걸 냅색 알고리즘을 어떻게 응용해야할지 모르겠어서

우선순위큐 BFS를 이용해 풀어봤다.

답은 맞았다.

#include <bits/stdc++.h>
using namespace std;

int n, m;

int arr[101][101], ch[101];

struct Edge{
	int node, dist;
	Edge(int a, int b){
		node = a;
		dist = b;
	}
	bool operator<(const Edge &e) const{
		return dist > e.dist;
	}
	
};

priority_queue<Edge> Q;

int DIST(int s,int e){

	int res = INT_MAX;
	Q.push(Edge(s,0));
	
	while(!Q.empty()){
		int cur_node = Q.top().node;
		int cur_dist = Q.top().dist;
		Q.pop();
		ch[cur_node] = 1;
		if(cur_node == e){
			res = min(res, cur_dist);
		}
		
		for(int i=1; i<=n; i++){
			if(arr[cur_node][i]!=INT_MAX && ch[i]==0){
				Q.push(Edge(i, cur_dist+arr[cur_node][i]));
			}
		}
		
	}
	
	for(int i=1; i<=n; i++){
		ch[i] = 0;
	}
	
	
	return res;

}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) continue;
			arr[i][j] = INT_MAX;
		}
	}
	
	for(int i=1; i<=m; i++){
		int a,b,c;
		cin>> a >> b >> c;
		arr[a][b] = c;
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			int ans = DIST(i,j);
			if(ans==INT_MAX) cout <<"M ";
			else cout << ans << " ";
		}
		cout <<'\n';
	}
	
}

플로이드워샬 알고리즘이란?

플로이드워샬 알고리즘은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다.

다익스트라 벨만포드 알고리즘과 플로이드워샬 알고리즘의 차이는?

다익스트라, 벨만포드 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리를 구한다는 점에서

플로이드워샬 알고리즘과 차이가 있다.

점화식

arr[i][j] 는 i노드에서 j노드로 가는 거리를 저장한다.

arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);

i노드에서 j노드로 가는 거리와

i노드에서 k노드를 거쳐 j 노드를 가는 거리를 비교해서 더 짧은 방법을 선택한다.

k에 대하여 존재하는 모든 노드를 한 번씩 다 적용시켜보면

모든 노드에서 모든 노드로 가는 최단 거리 테이블을 만들 수 있다.

다음과 같은 그림이 있을 때

k노드를 선택하기 이전에

arr[i][j] = 20이었다.

i - > j 노드로 가는 것 보다

i -> k -> j 노드로 가는 게 더 짧다.

arr[i][j] = 18로 선택된다.

추가적으로 t 노드가 있을 때

이제 i ->k ->j 보다

i-> k -> t -> j 노드로 가는 게 더 빠르다.

arr[i][j] = 18에서

arr[i][j] = arr[i][t] + arr[t][j] = 17로 갱신된다.

이런식으로 모든 노드에 대해서 갱신해주면

모든 노드에서 모든 노드로 가는 최단 거리를 구할 수 있다.

arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);

k번째 노드를 계속 선택해줘서 경유점으로 둘 때

최솟값을 계속 갱신해준다는 점에서 냅색알고리즘과 유사하다.

노드를 가방에 담을지 안담을지 선택한다고 보면 된다.

for(int k=1; k<=n; k++){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(arr[i][k]==INT_MAX || arr[k][j] == INT_MAX) continue;
            arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);
        }
    }
}

1부터 n까지 모든 노드 k에 대해서

k를 경유점으로 추가하는 것과 이전의 k를 경유점으로 추가하지 않는 것을 비교하면서

최솟값을 계속 저장해준다.

이러면 결과적으로 arr[i][j]에 i부터 j까지 가는 최단 거리가 저장된다.

(애초에 i에서 j로 갈 수 없는 점들은 INT_MAX로 초기화해두고 시작한다)

#include <bits/stdc++.h>
using namespace std;

int n, m;

int arr[101][101];


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i==j) continue;
			arr[i][j] = INT_MAX;
		}
	}
	
	for(int i=1; i<=m; i++){
		int a,b,c;
		cin>> a >> b >> c;
		arr[a][b] = c;
	}

	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				if(arr[i][k]==INT_MAX || arr[k][j] == INT_MAX) continue;
				arr[i][j] = min(arr[i][j], arr[i][k]+arr[k][j]);
			}
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if (arr[i][j]==INT_MAX) cout << "M ";
			else cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
	
}

플로이드 와샬 알고리즘을 이용하면

맨위처럼 우선순위큐 BFS를 사용하지 않아도

간단하게 모든 노드에서 모든 노드로 가는 최단거리를 구할 수 있다.

https://www.acmicpc.net/problem/14728

1. 문제설명

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과

시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와

그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

각 문제는 한번 씩만 풀 수 있고 최대 점수를 구해야 한다.

2. 접근 방법[알고리즘]

각 문제는 한 번만 풀 수 있으므로

다이나믹 테이블 dy에 for문을 뒤부터 돌면서

최댓값을 누적해주면 된다.

for문을 뒤부터 도는 이유는

이 문제는 각 단원 문제를 단 한 번씩 풀 수 있는데

앞에서부터 돌면 계속해서 중복된 값을 더해서 누적하기 때문이다.

중복된 값을 누적하는 걸 피하기 위해 뒤부터 돈다.

만약 각 단원 문제를 여러번 풀 수 있다면

for문을 앞에서 부터 돌아 계속 중복해서 누적해주면 된다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, t, dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		int k, s;
		cin >> k >> s;
		for (int j = t; j >= k; j--) {
			dy[j] = max(dy[j], dy[j - k] + s);
		}
	}
	cout << dy[t];

}

https://www.acmicpc.net/problem/7579

1.문제 설명, 접근 방법[알고리즘]

다이나믹프로그래밍 문제이자 배낭 문제이다.

"현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여

M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다."

M바이트의 메모리를 확보하는 게 아니라

M바이트 이상의 메모리를 추가로 확보해야 한다.

나는 처음에 이전에 배낭문제를 풀었던 걸 기억해서

무지성으로 메모리를 기준점을 잡고 비용의 최솟값을 갱신해나가려 했는데

그러면 메모리의 범위가 1 ≤ M ≤ 10,000,000 이어서 배열의 최대 사이즈를 넘어 사용할 수가 없다.

그런데 알고보니 메모리를 기준점으로 하는 게 아니라

비용을 기준점으로 하면 비용의 최댓값이 100이고 n의 최댓값이 100이어서

배열을 dy[10001]로 잡아주면 충분하다.

dy[i] 는 cost가 i 일 때 최대 확보한 메모리이다.

점화식

dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);

문제처럼 입력이 다음과 같을 때

5 60
30 10 20 35 40
3 0 3 5 4

dy 테이블은

각 문제를 적용했을 때 확보된 메모리가 60이상인 최소의 비용은

6이다.

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, mem[101], cost[101], dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> mem[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}


	for (int i = 0; i < n; i++) {
		for (int j = 10000; j >= cost[i]; j--) {
			dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
		}
	}

	for (int i = 0; i <= 10000; i++) {
		if (dy[i] >= m) {
			cout << i;
			break;
		}
	}


}