급하게임개발

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

이 문제의 경우 아마도 프로그래머스 고득점 알고리즘 키트해도 비슷한 문제가 수록 되있을 것이다 단 백준에서는 매우 큰수까지의 비교를 하기 때문에 자료형에 unsinged long long을 해줌으로 범위를 널널 하게 잡아줘야 한다

이 문제의 경우는 각 테이블 마다 특정 시간을 주고 해당 시간 동안 몇명의 인원수를 상대할 수 있는 지를 더해서 친구들의 수와 같으면 정답이게 출력을 해주면 되지만 해당 조건을 만족하는 더 작은 수가 있을  수  있다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	unsigned long long n, m;
	vector <unsigned long long > times;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		unsigned long long tmp1;
		cin >> tmp1;
		times.push_back(tmp1);
	}

	sort(times.begin(), times.end());
	unsigned long long answer = 0;
	unsigned long min = 1;
	unsigned long long max = m * times.back();

	while (min <= max) {
		unsigned long long tmp = 0;
		unsigned long long avg = (min + max) / 2;
		for (unsigned long long i = 0; i < n; i++) {
			tmp += avg / times[i];
		}

		if (tmp < m) {
			min = avg + 1;
		}
		else {
			max = avg - 1;
			answer = avg;
		}
	}
	cout << answer;
}

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/2631

이 문제는 LIS 문제이다  그 이유는 이 문제의 경우 학생들을 원하는 위치이 넣을 수 있으므로 정렬되어 있지 않은 학생들을 정렬된 학생의 알맞은 위치에 넣으면 되는것이다 즉 전체 수에서 LIS만큼  뺴주면 되는 문제였다

#include <iostream>
#include <algorithm>
using namespace std;
int arr[200];
int dp[200] = { 0, };
int lis = 0;
int main() {
	int n,x,y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <i; j++) {
			if (arr[i] > arr[j]) {
				dp[i]=max(dp[i], dp[j] + 1);
				lis = max(lis, dp[i]);
			}
		}
	}
	cout << n-lis;
}

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/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();
	}

}