급하게임개발

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

이 문제는 다 풀어놓고 하나를 실수 해서 조금 헤맸었다
이 문제는 일반적인 다익스트라 문제이다 이에 소스코드는 이렇게 되고 25% 에서 이슈가 있었다

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> djikstra_pq;
vector<pair<int, int>> edgeList[100000];
vector<int> distance_v;
int testCase;
int n, d, c;
#define INF 1000000001
void djikstraSolution(int start) {
	int startNode = start;
	int toCost = 0;
	djikstra_pq.push({ toCost,startNode });
	while (!djikstra_pq.empty())
	{
		int vertex = djikstra_pq.top().second;
		int toCost = djikstra_pq.top().first;
		djikstra_pq.pop();
		if (toCost > distance_v[vertex])
			continue;

		for (int i = 0; i < edgeList[vertex].size(); i++) {
			int nextVertex = edgeList[vertex][i].first;
			int nextCost = edgeList[vertex][i].second;
			if (distance_v[nextVertex] > nextCost + toCost) {
				distance_v[nextVertex] = nextCost + toCost;
				djikstra_pq.push({ nextCost + toCost,nextVertex });
			}
		}
	}
}
int main() {
	cin >> testCase;
	for (int i = 0; i < testCase; i++) {
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			int from, to, cost;
			cin >> from >> to >> cost;
			edgeList[to].push_back({ from,cost });
		}
		distance_v.assign(n + 1, INF);
		int cpuCnt, lastSecond;
		djikstraSolution(c);
		lastSecond = 0;
		cpuCnt = 0;
		distance_v[c] = 0;
		for (int i = 1; i <= n; i++) {
			if (distance_v[i] != INF) {
				cpuCnt++;
				if (distance_v[i] > lastSecond) {
					lastSecond = distance_v[i];
				}
			}
			edgeList[i].clear();
		}
		cout << cpuCnt << " " << lastSecond << endl;
	}
}

이런식으로 되는데 내가 처음에 distanceVector를 초기화 해줄 때 나에서부터 나까지의  거리는 0이라고 설정을 안해놓았었다 그 후 무조건 감염 PC는 하나니 cpuCnt값을 1로두고 셌다 근데 문제는 여기서 a->b b->a 로가는 경로가 생길시 a의 경로값이 갱신 되면서 

			if (distance_v[i] != INF) {
				cpuCnt++;

이 부분에서 CPUCNT가 하나더 증가해서 이미센 감염피씨를 한번 더세면서 문제가 틀렸었다 이에 감염된 피씨의 초를 0으로 바꿔주고 cpuCNt의 값을 0으로 바꿔주니 정상적으로 나왔다

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

이 문제의 경우 문제 분류에 부르트 포스 라고 되어있지만 정확히는 dfs 백트래킹이라고 보는게 맞을거 같다 
처음에는 0 부터 9876543210 까지 수들을 검사해서 해당 수가 감소하는 수 인지를 검사하는 방법을 사용했지만 해당 방법은 시간초과를 유발했기에 dfs와 백트래킹을 사용하여 해당 문제를 풀었다

해당 이미지를 보자 우리가 백트래킹으로감소하는 수를 만들려고 할시 반복문의 범위를 단지 이전 자리의 숫자의 값까지만 증가시켜주면서 넣어주면 된다

#include <iostream>
using namespace std;
long  long arr[1000001];
long  long n;
long  long numCnt;
long  long idxOfNum = 10;
void makeDecreaseNum(long  long num , long  long numOfone , long  long cntOfNum) {
	if (cntOfNum==numCnt) {
		arr[idxOfNum] = num;
		idxOfNum++;
	}
	else {
		num = num * 10;
		for (long  long i = 0; i < numOfone; i++) {
			makeDecreaseNum(num + i, i, cntOfNum+1);
		
		}
	}

}
int main() {
	cin >> n;
	for (long  long i = 0; i < 1000001; i++) {
		arr[i] = -1;
	}
	for (long  long i = 0; i < 10; i++) {
		arr[i] = i;
	}
	for (long  long i = 2; i <= 11; i++) {
		numCnt = i;
		for (long  long j = 1; j <= 9; j++) {
			makeDecreaseNum(j, j, 1);
		}
	}
	cout << arr[n];
}

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=cpp

이 문제는 프로그래머스 알고리즘 고득점 Kit의 문제이다 
Programmers LV3 문제 치고는 접근 법이 매우 쉬웠다 이 문제의 경우

이렇게 생긴 벡터가 제공이 된다 

실제 자료형은 이렇게 제공이 되는데
이 문제는 똑같은 삼각형을 만들고 나의 이전 행에 있는 나를 기준으로 양대각선의 있는 값중 나와의 합이 최대가 되는 애와의 합을 내가 현재 있는 위치에 넣는 것이다

즉 이그림을 보면 3번 째줄에 와서 보면 1을 기준으로 내가 선택할 수 있는 것은 이전행의 10과 15이다 이중 두값중 1과 합했을때 큰값을 16임으로 나의 위치에 16을 넣어준다 이를 계속 반복 해주면 된다

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    vector<vector<int>> dpV;
    vector<int> rowV1;
    dpV.push_back(rowV1);
    dpV[0].push_back(triangle[0][0]);
    for(int i=1; i<triangle.size(); i++){
        vector<int> rowV;
        dpV.push_back(rowV);
        
        for(int j=0; j<triangle[i].size(); j++){
            if(j==0){
                dpV[i].push_back(dpV[i-1][j]+triangle[i][j]);
            }
            else if(j==triangle[i].size()-1){
                dpV[i].push_back(dpV[i-1][j-1]+triangle[i][j]);
            }
            else{
                dpV[i].push_back(max(triangle[i][j]+dpV[i-1][j-1],triangle[i][j]+dpV[i-1][j]));
            }
        }
    }
    int answer = 0;
    for(int i=0; i<dpV[triangle.size()-1].size(); i++){
        answer=max(answer,dpV[triangle.size()-1][i]);
    }
    return answer;
}

위에 코드를 보게 되면 똑같은 이차원 벡터를 만들어 주고 해당 벡터를 dp 로 놓고 이전 행과의 합을 계속 누적 하고 마지막행에서 최댓값을 구하는 방법으로 코드를 구현 했다

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

이 문제의 경우 dfs로 풀이를 진행했다  이 문제를 풀 때 한가지 잘못 생각한점으 치즈 안의 공간은 실내온도에 접촉 한것이아니라는 것이었다.  문제에서 테두리에는 치즈가 없다고 명시해주었으므로 dfs혹은 bfs로 0,0 위치 와 연결된 공간들을 모두 -1  로 체크 해주었다 그후 dfs를 한번더 진행하여 치즈들중 외부공기 2층이랑 이어진 공간들에 대해서 다른 배열에 넣어서 계산해주고 다시 0,0부터 dfs를 돌려 외부공기를 체크해 주었다.

#include <iostream>
using namespace std;
int N, M;
int arr[100][100];
int willMelt[100][100];
int xIdx[4] = { 1,0,-1,0 };
int yIdx[4] = { 0,1,0,-1 };
bool isVisited[100][100] = { 0, };
bool canGo(int x, int y) {
	if (x < N && y < M && x >= 0 && y >= 0) {
		if (!isVisited[x][y] && (arr[x][y] == 1))
			return true;
		else
			return false;
	}
	else
		return false;
}
void copyArr(int arr[100][100], int arr2[100][100]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			arr[i][j] = arr2[i][j];
		}
}
void dfs(int x, int y) {
	int zeroCount = 0;
	for (int i = 0; i < 4; i++) {
		if (arr[x + xIdx[i]][y + yIdx[i]] == -1) {
			zeroCount += 1;
		}
		if (canGo(x + xIdx[i], y + yIdx[i])) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			dfs(x + xIdx[i], y + yIdx[i]);
		}
	}
	if (zeroCount >= 2) {
		willMelt[x][y] = 0;
	}

}
void airDfs(int x, int y) {
	arr[x][y] = -1;
	for (int i = 0; i < 4; i++) {
		if (x + xIdx[i] < N && y + yIdx[i] < M && x + xIdx[i] >= 0 && y + yIdx[i] >= 0 && !isVisited[x + xIdx[i]][y + yIdx[i]]&& (arr[x + xIdx[i]][y + yIdx[i]] == 0|| arr[x + xIdx[i]][y + yIdx[i]] == -1)) {
			isVisited[x + xIdx[i]][y + yIdx[i]] = true;
			arr[x + xIdx[i]][y + yIdx[i]] = -1;
			airDfs(x + xIdx[i], y + yIdx[i]);
		}
	}


}
void meltCheese() {
	copyArr(willMelt, arr);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!canGo(i, j))
				continue;
			isVisited[i][j] = true;
			dfs(i, j);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	copyArr(arr, willMelt);
}
bool isMelted() {
	int sum = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] != -1)
				sum += 1;
		}
	}
	if (sum == 0)
		return true;
	else
		return false;
}
void process() {
	int year = 0;
	airDfs(0, 0);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			isVisited[i][j] = false;
		}
	}
	while (!isMelted()) {
		meltCheese();
		airDfs(0, 0);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				isVisited[i][j] = false;
			}
		}
		year += 1;
	}
	cout << year;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}
	process();
}

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;
	}
}

이 문제의 경우 처음에 for문을 연달아 쓰려 했으나 그렇게 할봐에 차라리 재귀를 통한 진행이 맞을 것이라고 판단하였다

#include <string>
#include <vector>
#include <string>

using namespace std;
int cnt=-1;
int answer=0;
string target="";
string aeiou="AEIOU";
void dfs(string word){
    cnt+=1;
    if(target==word){
        answer=cnt;
        return;
    }
    if(word.length()>=5)
        return;
    for(int  i=0; i<5; i++){
        dfs(word+aeiou[i]);
    }
}
int solution(string word) {
    target=word;
    dfs("");
    return answer;
}