급하게임개발

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

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있다 현재 이블로그에 있는 다익스트라 알고리즘에 관한 문제는 비슷한 양상을 보인다

void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}

이 부분이 핵심 부분인데

1. 일단 start 즉 시작점으로 부터의 거리를 구할 것이기에 Start -> Start의 toCost를 0 start->start의 다음인덱스 start를 우선순위 큐에 넣는다 (우선순위 큐는 값이 작은게 root 에 있다)

2.그리고 우선순위 큐가 빌때 까지 
현재 우선순위 큐에 들어가 있는 버텍스와 경로들을 뽑아서 해당 경로들에  영향을 받는 다른 vertex들의 cost값을 업데이트 해줘야 한다

3.일단 node1 -> node2 로 갈때의  현재 우선순위 큐에들어가 있는 가장 작은 애를 가져온다 그후 내가 node1을 통해서 가는 node2 까지의 거리와 이전부터 업데이트  해놓은 1부터 node2까지의 거리를 비교해서 작은 값일 때  node2를 통해서 가는 거리들의 값을 업데이트 해준다 그후 다음 업데이트를 할수도 있으니 해당 값들을 우선순위 큐에 넣어주고 반복한다

전체 코드는 아래와 같다

#include <iostream>
#include<queue>
using namespace std;
int n, m;

#define INF 1e9+7
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[5001];
vector<int> distanceV(5001);
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ startNode,toCost });

	while (!djikstra_pq.empty()) {
		int toVertex = djikstra_pq.top().first;
		int toCost = djikstra_pq.top().second;

		djikstra_pq.pop();

		int distanceToNextVertex = distanceV[toVertex];
		if (distanceToNextVertex < toCost) {
			continue;
		}
		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			// 다음 인덱스로 가는 cost
			int cost = edgeList[toVertex][i].second + toCost;
			// 나를 통해 갈 다음 IDX
			int nextIdx = edgeList[toVertex][i].first;
			if (cost < distanceV[nextIdx]) {
				distanceV[nextIdx] = cost;
				djikstra_pq.push({ nextIdx,cost });
			}
		}


	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;

		edgeList[temp1].push_back({ temp2,temp3 });
		edgeList[temp2].push_back({ temp1,temp3 });

	}
	int start, end;
	cin >> start >> end;

	distanceV.assign(n + 1, INF);
	djikstraSolution(start);

	cout << distanceV[end];
}

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

솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의  로직을 아는사람이 풀 수 있었다.  핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 1이라는 무게추가 있다고 가정 하자 1이라는 무게추가 있을 때 다음 무게추가 지금 내가 가지고 있는 무게추의 무게보다 크게 되면 사이 무게인 2를 만들 수없다.

다른 예시로 현재 내가 1,1,2 이렇게 총 3개의 무게추를 가지고 있는데 다음 무게추로 6이 들어오게 되면 나는 4를 만들 수  없다

즉 현재 내가 가지고 있는 총 무게추의 무게보다 작은 무게들을 다 만들 수 있을 때 다음에 사용할 무게추는 내가 가지고 있던 총 무게보다 작아야 한다.

해당  로직이 이문제를 풀 수 있게 하는 핵심 로직이었다

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[1000];

int main() {

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    sort(arr, arr + N);

    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }

    cout << res;
}

이 문제는 dp문제이다

#include <iostream>
#include <algorithm>
using namespace std;
//dp[i][j]= 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j였을 떄 배낭에 들어간 물건의 가치합의 최댓값
//예를 들어
int dp[101][100001];
int W[101];
int V[101];
int main() {
	//N은 물건의 갯수를 의마한다.
	//K는 버틸수 있는 물건의 무게를 의미한다.
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (j - W[i] >= 0) {
				//현재 무게의 최댓갑은 이전아이템까지 넣은 단계에서의 최댓값과
				//지금 아이템의 무게를 넣은 물건의 값을 비교하여 더 큰값을 넣는다.
				//i번째 물건을 넣을 지 말지가 중요하다.
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]+V[i]);
			}
			else {
				//현재 아이템을 넣었을때 무게가 오바된다면 넣지 않고 이전걸 그대로 가져온다
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][K];
}

코드를 살펴보면 일다 우리는 가지고 있는 첫번째 아이템 부터 차근차근 가방에 넣을 것이다. 차근차근 넣을 때 제한 무게를 초과한다면 그 아이템은 넣지 않는다가 이문제의 핵심이다. 즉 i번째 아이템을 넣은 것과 안 넣은 것의 최댓값을 계속 갱신해주면서 진행하는게 해당 문제의 해결 방법이다. i=1일때 우리는 가방에 이 아이템을 넣을지 말지 결정 한다. dp[0][0]은 어차피 0이다 하지만 무게해당하는 j값이 0이기에 일단 넣지 않는다. 이에 dp[1][6]=13이다 즉 1번아이템을 넣었을 때의 무게는 6이고 13이다라는 의미이다 이제 2번아이템을 넣는다고 가정해보자 2번아이템도 마찬가지로 진행이된다. dp[4][4]의 가치는 일단 8이다 하지만 이제 dp[6]으로 간다면 2번까지 넣어서 6이하의 무게를 만든 가방보다 1번만 넣어서 6이하의 무게를 가진 가방의 가치가 더높으므로 dp[2][6]=13이다. 

자이제 3번아이템까지 넣는다고 가정하자  일단 dp[3][3]=6이다 dp[2][4]=8이고 이에 따라 dp[3][4]=8이다

dp[3][7]의 기준으로 보자 지금 까지는 dp[1][6]의 값이 계속 들어 와서 13이었을 것이다. 하지만 3번 아이템을 넣는다고 가정해보았을 때 dp[2][4]+dp[3][3] 즉 dp[2][4]+V[i]의 값이 기존의 dp[2][7]즉 dp[1][6]의 값이 계속 넣어진 상황 보다 큼으로

갱신된다