급하게임개발

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

이 문제의 경우 프로그래머스 에서 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);
}

이 문제는 프로그래머스의 분류 실수이다 처음에는 그리디 문제로 계획을 했겠지만 후에 테스트케이스를 추가하면서 완전 탐색으로 풀게 변경되었다. 문제의 알고리즘이 변경되면 분류도 변경되어야 하지만 해당부분이 변경되지 않아 푸는데 많은시간을 소비하게 됬다

그리디로 풀었을 때의 코드는

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
bool isVisited[20] = { 0, };
int nextIdx(int idx) {
    if (idx + 1 == n) {
        return 0;
    }
    else
        return idx + 1;
}
int beforeIdx(int idx) {
    if (idx - 1 == -1) {
        return n - 1;
    }
    else {
        return idx - 1;
    }
}
int solution(string name) {
    int idx = 0;
    int beforeDif = 1;
    string alphaAs = "";
    int nIdx;
    int bIdx;
    n = name.size();
    for (int i = 0; i < n; i++) {
        alphaAs += 'A';
    }
    int answer = 0;
    while (name.compare(alphaAs) != 0) {
        isVisited[idx] = true;
        answer += min(name[idx] - 'A', 'Z' - name[idx] + 1);
        name[idx] = 'A';
        int left_idx = idx;
        int right_idx = idx;
        int leftCnt = 0;
        int rightCnt = 0;
        while (name[left_idx] == 'A' && leftCnt<n) {
            if (name.compare(alphaAs) == 0) {
                return answer;
            }
            left_idx = beforeIdx(left_idx);
            leftCnt++;
        }
        while (name[right_idx] == 'A' && rightCnt<n) {
            if (name.compare(alphaAs) == 0) {
                return answer;
            }
            right_idx = nextIdx(right_idx);
            rightCnt++;
        }
        if (leftCnt < rightCnt) {
            answer += leftCnt;
            idx = left_idx;
        }
        else {
            answer += rightCnt;
            idx = right_idx;
        }

    }
    return answer;
}

이렇게 되지만 해당 부분이 정답이 아니었다.
이에 프로그래머스 커뮤니티를 찾아보니 그리디로 풀리지 않는다고 나왔다.
이 문제는 어떻게 보면 투포인터 혹은 탐색문제의 가깝다

이 문제의 알파벳 탐색 방향은 총 4가지다

1. 오른쪽으로 쭉 탐색하기
2. 왼쪽으로 쭉 탐색하기
3. 왼쪽으로 갔다가 오른쪽으로 가기
4. 오른쪽으로 갔다가 왼쪽으로 가기
즉 1번어떠한 지점까지 갔다가 다시되돌아오면서 탐색하는  거 까지가 이 문제의 진행 방향이다
여러번되면 최소인 1번과 2번의 횟수보다 많아지기에 해당 로직은 검사하지 않는다

예시로 JAZAAAP 라는 문자가 있다고 생각하자

일단 우리는 방향을 바꿀 지점이 필요하고 방향을 바꾸고 어디까지 탐색할지에 대한 지점이 필요하다

자 이 문제를 우리가 해결하기 위해서는 처음 받은 문자열에서 가장 긴 문자열을 탐색 하지 않아야 한다 이에 
우리가 이문제를 풀기 위해서는
가장 긴 AAA가 나오는 부분을 건너지 말아야하므로 해당 영역의 시작점 X와 Y를 구해야한다

해당 예시에서 구해지면 이렇게 된다.
즉 이렇게 우리가 구간을 나눴을 때 우리는 
방향을 바꿔서 원점에서 -> y -> x 와 원점에서 ->x->y 에서의 최솟값을 구해야 한다.

원점에서 왼쪽으로 y를 탐색하고 x를 탐색하는 것의 식은
(n-y)+(n-y)+x 이고
원점에서 오른쪽으로 x를 탐색하고 y를 탐색하는 것의 식은
x+x+(n-y)이다

이에 우리는 특정 x를 기준으로 가장 긴 A가 만들어지는 Y를 찾으면 되는 문제이다 그후 두영역에서 방향을 바꾼다고 가정할 때의 최솟값이 커서의 이동의 최소 횟수 임으로 해당 횟수 + 문자를 A로 바꾸는횟수를 더해주면 된다

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int solution(string name) {
    int upDownMove[26] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1 };
    int ans = 0, n = name.size();
    int leftRightMove = n - 1;
    for (int x = 0; x < n; x++) {
        ans += upDownMove[name[x] - 'A'];
        int y = x + 1; 
        while (y < n && name[y] == 'A') y++;
        leftRightMove = min(leftRightMove, min(x + x + (n - y), x + (n - y) + (n - y)));
    }
    ans += leftRightMove;
    return ans;
}

map을 사용하는 문제 였다
이문제의 경우 완주자의 경우 이름이 불린 수가 짝수 이다 그 이유는 참가 할때 한번 완주할 때 한번 불리기 때문이다 사람이 동명이인이 있어도 마찬가지이다

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

string solution(vector<string> participant, vector<string> completion) {
    map<string,int> mp;
    map<string,int>::iterator iter;
    for(int i=0; i<participant.size(); i++){
        mp[participant[i]]++;
    }
    for(int i=0; i<completion.size(); i++){
        mp[completion[i]]++;
    }
    for(iter=mp.begin(); iter!=mp.end(); iter++){
        if((iter->second)%2==1)
            return iter->first;
    }

}

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

이 문제의 경우 bfs 문제이다 dfs로 풀어도 무방하다
나의 경우 이문제를 풀 때 &&의 순서를 잘못 써서 문제를 제출했을 때 틀렸었다

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int arr[50][50];
bool isVisited[50][50];
queue<pair<int, int>> bfsq;
queue<pair<int, int>> visitedq;
int n, l, r;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int nx, int ny) {
	if (nx >= 0 && nx < n && ny>=0 && ny < n && !isVisited[nx][ny]) {
		if (abs(arr[nx][ny] - arr[x][y])>=l && abs(arr[nx][ny] - arr[x][y])<=r) {
			return true;
		}
		return false;
	}
	else {
		return false;
	}
}
bool bfs(int sX, int sY) {
	bfsq.push({ sX,sY });
	visitedq.push({ sX,sY });
	isVisited[sX][sY] = true;

	int cx, cy , nx, ny ,population, nationCount;
	int avrPop=0;
	population = arr[sX][sY];
	nationCount = 1;
	while (!bfsq.empty()) {
		cx = bfsq.front().first;
		cy = bfsq.front().second;
		bfsq.pop();
		for (int i = 0; i < 4; i++) {
			nx = cx + dx[i];
			ny = cy + dy[i];
			if (canGo(cx, cy, nx,ny)) {
				bfsq.push({ nx, ny });
				visitedq.push({ nx, ny });
				isVisited[nx][ny] = true;
				population += arr[nx][ny];
				nationCount += 1;
			}
		}
	}
	avrPop = population / nationCount;

	while (!visitedq.empty()) {
		arr[visitedq.front().first][visitedq.front().second] = avrPop;
		visitedq.pop();
	}

	if (nationCount > 1)
		return false;
	else {
		isVisited[sX][sY] = false;
		return true;
	}
}
int main() {
	cin >> n >> l >> r;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	while (true) {
		bool canBreak = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(!isVisited[i][j])
					canBreak=bfs(i, j)&&canBreak;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				isVisited[i][j] = false;
			}
		}
		if (canBreak)
			break;
		cnt += 1;
	}
	cout << cnt;

}

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

이 문제의 경우 처음에 이해하기 좀 어려웠었다

이  문제의경우 일단 이경우를 생각 해주어야 한다 길이 2짜리공간에 타일을 넣어서 채울 수 있는 경우의 수는 3이다 4짜리 타일을  채우는 경우의  수는 2가 더있다

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int dp[31] = { 0 };

    dp[0] = 1;
    dp[2] = 3;

    for (int i = 4; i <= n; i++)
    {
        dp[i] = dp[i - 2] * 3; 
        for (int j = 4; j <= i; j += 2)
        {
            dp[i] += dp[i - j] * 2; 
        }
    }

    cout << dp[n];
    return 0;
}