급하게임개발

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

이 문제의 경우 전형 적인 다익스트라 알고리즘으로 풀 수 있을거 같았다 그 이유는 첫시작 점이 0 그리고 endPoint인 n-1 까지 가는 것으로 정해졌기에

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

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}

굳이 플로이드  와샬로 전체 의 거리는 구할 필요가 없기 때문이다 

항상 다익스트라에서 쓰는 로직과 비슷하다 일단 StartVertex를 StarVertex까지의 거리가 0이라 두고 큐에다가 넣는다

그후 edgeList에서  startNode와 연결된 모든 노드들과 계산하여 거리를 구한후 priority queue에 넣는다 이를 반복하면 결국에 마지막 노드까지 가는거리가 최단거리로 완성이 된다.

이문제의 경우 단 djikstra를 풀때 조건이 하나가 추가되는데 해당 vertex의 시야값이 1이면 가지 않는 것이다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1234987654321
priority_queue < pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> djikstra_pq;
vector<pair<int, long long>> edgeList[300000];
vector<long long> distanceV(300000);
bool canGo[300000] = { 0, };
int n, m;
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,start });

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

		if (distanceV[toVertex] < toCost)
			continue;

		for (int i = 0; i < edgeList[toVertex].size(); i++) {
			int nextVertex = edgeList[toVertex][i].second;
			long long nextCost = edgeList[toVertex][i].first;
			if (distanceV[nextVertex] > toCost + nextCost && (canGo[nextVertex] || nextVertex==n-1)) {
				distanceV[nextVertex] = toCost + nextCost;
				djikstra_pq.push({ toCost + nextCost,nextVertex });
			}
		}

	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> canGo[i];
		canGo[i] = !canGo[i];
	}

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		edgeList[from].push_back({ cost,to });
		edgeList[to].push_back({ cost,from });
	}
	distanceV.assign(n , INF);
	djikstraSolution(0);
	if (distanceV[n - 1] >= INF)
		cout << -1;
	else
		cout << distanceV[n-1];
}

전체 코드는 위와 같다

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

이 문제의 경우 전형적인 플로이드 워셜 알고리즘을 사용 하여 구현한다
핵심이 되는  부분은

void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}

k즉 i to k , k to j 즉 어떠한 정점 까지 갈때 중간에  거치는 지점이다 즉 계속 거치는 지점을 업데이트 해주면서 최소 거리를 구하는게 플로이드 워셜의 로직이다

#include <iostream>
#define INF 987654321
using namespace std;
int dp[401][401];

int v, e;
void floyd() {
	//k는 경유점
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
}
int main() {
	int maxValue = INF;
	cin >> v >> e;
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (i == j)
				dp[i][j] == 0;
			else
				dp[i][j] = INF;
			
		}
	}
	for (int i = 0; i < e; i++) {
		int from, to, value;
		cin >> from >> to >> value;
		dp[from][to] = value;
	}

	floyd();

	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			if (dp[i][j] + dp[j][i] < maxValue && !(i==j)) {
				maxValue = dp[i][j] + dp[j][i];
			}
		}
	}
	if (maxValue >= INF) {
		cout << -1;
	}
	else {
		cout << maxValue;
	}
}

이 문제의 경우 프로그래머스 에서 dfs, bfs로 분류를 해놓았다 하지만 문제를 보았을 때 해당 방식으로 푸는것 보다는 그래프 이론중 유니온 파인드를 통해서 푸는게 더 맞는 방식으로 생각되어 해당 방식으로 풀이를 진행 하였다

#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
int parent[200];

int GetParent(int x) {
    if (parent[x] == x)
        return parent[x];
    else {
        parent[x] = GetParent(parent[x]);
        return parent[x];
    }
}

bool IsSameParent(int x, int y) {
    if (GetParent(x) != GetParent(y)) {
        return false;
    }
    else
        return true;
}

void MakeSameParent(int x, int y) {
    if (!IsSameParent(x, y)) {
        parent[GetParent(y)] = GetParent(x);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    set<int> s;
    for (int i = 0; i < n ; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(computers[i][j]==1)
                MakeSameParent(i, j);
        }
    }

    for (int i = 0; i < n ; i++) {
        s.insert(GetParent(parent[i]));
    }

    answer = s.size();
    return answer;
}

int main() {
    vector<vector<int>> computers = { {1,1,1},{1,1,0},{1,0,1} };
    int n = 3;

    cout<<solution(3, computers);
}

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

이 문제의 경우 점화식을 세우기 빡셌다 이문제의 경우 일단 대충의 로직은

이 상태에서 시작하게 된다 맨위에 파란부분은 수고 그이후의 행들은 해당 숫자를 만드는 데 사용하는 수의 개수를 의미합니다 현재 1행에 숫자 1들이 들어간 이유는 각 수를 만드는데는 자기자신 하나만 필요하기 때문입니다.

자 그리고 다음 행을 봅시다
0을 만드는데는 어차피 0 하나로 밖에 못만드니 

이렇게 채워 줍시다
그다음 2행을 채우게 되면 숫자 2개로 해당 수를 만드는 방법을 봅시다 1은 1+0 과 0+1 로만들 수 있습니다 2는 1+1과 0+2와  2+0으로 만들 수있습니다 우리는 여기서 알수있는게 해당행의 이전행에서의 나자신까지의 합을 모두 더해주면 된다는 것을 알수 있습니다. 0을 선택하게 되면 자동을 2가선택 1을 선택하면 자동으로 1이선택 2를 선택하면 자동으로 0이선택되니 이전행의 자신 열까지의 합을 넣어주면 됩니다

그후 3행은 숫자 3개를 이용하는 것이기에 이전 행에서 2개를 선택한 로직에서 추가로 확장하면 됩니다 숫자 3개로 1을 만드는 방법은 (0+0)+1 , (1+0)+0,  (0+1)+0 이고 2의경우는 이전에 2개를 선택한거에 추가로 해당 수를 제외한 수를 더해주면 자동으로 더해지게 됨으로 이전행의 열들의 값을 더해주면 됩니다

결과적으로 그림이 이렇게 되서 완료가 됩니다.
해당 코드를 구현하면

#include <iostream>
using namespace std;
long long m = 1000000000;
long long dp[204][204];
int main() {
	long long n, k;
	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}


	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[k][n];
}

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

이 문제는 그리디 문제이다 처음에 이문제를 완전 탐색으로 하려 했으나 완전 탐색을 하라고 낸 문제는 아닌거 같았다 이에 s->t 를 하기보다는 t->s 를 해야겠다고 생각했다 이에 끝문자가 A면 단순 Pop을 B면 Pop을 하고 뒤집어주었다

#include <iostream>
#include<string>        
#include<algorithm>
using namespace std;
int main() {
	string s, t;
	cin >> s;
	cin >> t;
	while (1) {
		if (s.size() == t.size()) {
			if (t == s) {
				cout << 1;
			}
			else {
				cout << 0;
			}
			break;
		}
		if (t[t.size() - 1] == 'A') {
			t.pop_back();
		}
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}
}

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

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

int dfs(int x,int y) {
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다

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

이 문제의 경우  최소 신장  트리 문제중 하나로 일단  최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다
크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다 

이 문제에서는 핵심적으로 4개의로직이 있다.

1. 부모를 찾는 로직

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);

이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다

2. 같은 부모인지 찾는 로직

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;

3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다

void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}

4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서  2번 3번 과정을 반복해준다 그후 연결된 cost중 가장  높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다

	for (int i = 0; i < inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}

전체 코드는 아래와 같다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 0, };

int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e;
	long long cost;
	cost = 0;
	int cnt = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}
	cout << cost;
}

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

이 문제는 전형 적인 그리디 문제이다 그리디 문제의 특징은 모든 과정에서의 답이아니기 때문에 풀 수 있다

이문제는 일단 주의 할점을 일반적으로 input을 받으면 int 형자료형은 50만자리의 수를 받을 수없기 때문에 string으로 input을 받아 사용하는게 좋다

또한 이문제는 스택을 두고 이전에 들어온 값들보다 현재 들어오는 값들을 뽑고 거기에 넣으면서 뽑은 횟수를 저장해야한다 그래서 만약에 최대 뽑기수보다 못뽑으면 그냥 그상태로 값이 나온다

#include<iostream>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
stack<long long> bigStack;
stack<long long> answerStack;
long long n, k;
string num;
vector<long long> arr;
long long popCount=0;
long long result = 0;
int main() {
	cin >> n >> k;
	cin >> num;
	for (int i = 0; i < num.length(); ++i) {
		arr.push_back(num[i] - '0');  // 문자 '0'을 빼서 실제 숫자로 변환
	}

	if(arr.size()!=0)
		bigStack.push(arr[0]);
	for (long long i = 1; i < n; i++) {
		while (!bigStack.empty()&& bigStack.top() < arr[i] && popCount<k) {
			bigStack.pop();
			popCount += 1;
		}
		bigStack.push(arr[i]);
	}
	while (popCount < k) {
		bigStack.pop();
		popCount += 1;
	}
	while (!bigStack.empty()) {
		answerStack.push(bigStack.top());
		bigStack.pop();
	}

	while (!answerStack.empty()) {
		cout << answerStack.top();
		answerStack.pop();
	}

}