급하게임개발

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

이 문제는 처음에 조건을 잘못 읽었다 처음에 머리<가슴<배 순인 줄알았지

가슴 > 배 , 머리<배 를 만족하는 조건을 찾는 거였다

이에 일단 이문제는 배사이즈를 정해놓고 적절한 머리와 배를 나누는 구간을 찾는 방식으로 문제를 풀어야했다

당연히 배가 머리+가슴 보다 사이즈가 커지게된다면 조건을 만족하게 나눌수 없기에 이부분은 계산 하지 않는다

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

이 함수를 보자 우리는 bellyW 즉 배의 영역의 총합이랑 머리 가슴 영역의 값을 비교해줄것이다
즉 머리 가슴 영역이 bellyw와 조건을 만족 할 수 있도록 즉 머리가 최대한 크지만 배보다 작게 가슴은 최대한 작지만 배보다 큰 idx를 구한다 이 idx를 ans값이라고 하겠다 이것보다 작은값은 다 정답임으로 경우의 수를 반환한다

전체 코드는 아래와 같다

#include <iostream>
using namespace std;

long long arr[1000000];
int n;

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    arr[0] = 0;
    long long sum = 0, tmp;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        sum += tmp;
        arr[i] = sum;
    }

    long long ans = 0;
    for (int i = n; i >= 2; i--) {
        long long bellyW = arr[n] - arr[i - 1];
        ans += binaryHeadBelly(i, bellyW);
    }

    cout << ans;
    return 0;
}

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

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

int arr[200][200];
bool visited[200][200][31] = { false }; // visited[row][col][사용한 말 이동 횟수]
int dx[4] = { 0, 0, -1, 1 };            // 상하좌우 이동
int dy[4] = { 1, -1, 0, 0 };
int hx[8] = { -2, -2, 2, 2, -1, -1, 1, 1 }; // 말(나이트) 이동
int hy[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };

int main() {
    int k, w, h;
    cin >> k >> w >> h;
    // h행, w열의 배열 입력 (문제에서 h가 행의 개수, w가 열의 개수임)
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> arr[i][j];
        }
    }

    // (현재 행, 현재 열)와 (이동 횟수, 사용한 말 이동 횟수)
    queue< pair< pair<int, int>, pair<int, int> > > bfsQ;
    bfsQ.push({ {0, 0}, {0, 0} });
    visited[0][0][0] = true;

    int minMoves = -1;
    while (!bfsQ.empty()) {
        pair< pair<int, int>, pair<int, int> > cur = bfsQ.front();
        bfsQ.pop();
        int x = cur.first.first;
        int y = cur.first.second;
        int moveCount = cur.second.first;
        int horseUsed = cur.second.second;

        // 목적지: (h-1, w-1)
        if (x == h - 1 && y == w - 1) {
            minMoves = moveCount;
            break;
        }

        // 4방향 이동 (상, 하, 좌, 우)
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                continue;
            if (arr[nx][ny] == 1)
                continue;
            if (!visited[nx][ny][horseUsed]) {
                visited[nx][ny][horseUsed] = true;
                bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed} });
            }
        }

        // 말 이동 (나이트 이동) 처리 (남은 말 이동 횟수가 있을 경우)
        if (horseUsed < k) {
            for (int i = 0; i < 8; i++) {
                int nx = x + hx[i];
                int ny = y + hy[i];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                if (!visited[nx][ny][horseUsed + 1]) {
                    visited[nx][ny][horseUsed + 1] = true;
                    bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed + 1} });
                }
            }
        }
    }

    cout << minMoves;
    return 0;
}

이 문제는 조금 어려운 BFS 였다 어렵다기 보다는 isVisited를 선언할 때 3차원 배열로 할수 있음이 있었다
즉 말움직임을 k번사용해서 방문했을 때의 대한 값을 저장해놓았다 그리고 해당 문제는 bfs 이기에 먼저 도착했을 경우 해당 값은 이미 방문처리가 되었기 때문에 방문 최소 횟수 를 저장해놓을 필요는 없는 문제였다

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

이 문제는 처음에는 역 다익스트라를 면접장에서 구해서 최소 면접점을 구해서 했는데 시간 복잡도가 나왔다

이문제를 풀면서 처음안건데 멀티소스다익스트라라는 것이 있었다 이 알고리즘은 다익스트라의 시작점에 여러개를 넣고 시작하는데 이때 distacneV 벡터에는 각 시작점들에서 부터 그지점까지 가는곳의 최솟 값이 저장된다 즉 어디서 왔는지에 대해서는 모르지만 여러시작점들중 나까지 오는데의 최소 거리는 알수 있다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 50000000001

int n, m, k;
vector<pair<int, long long>> edgeList[100001];  // 1번부터 n번까지 사용 (문제 constraints에 따라)
vector<long long> dist;  // 각 도시까지의 최단 거리

// 멀티 소스 다익스트라: 여러 시작점을 동시에 처리
void multiSourceDijkstra(const vector<int>& startNodes) {
    dist.assign(n + 1, INF);
    // (거리, 노드)를 저장하는 최소 힙
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    // 모든 면접 장소를 초기 노드로 넣고 거리를 0으로 설정
    for (int node : startNodes) {
        dist[node] = 0;
        pq.push({ 0, node });
    }

    while (!pq.empty()) {
        int cur = pq.top().second;
        long long curCost = pq.top().first;
        pq.pop();

        if (curCost > dist[cur])
            continue;

        // 인접 노드 업데이트
        for (auto& edge : edgeList[cur]) {
            int next = edge.first;
            long long nextCost = edge.second;
            if (dist[next] > curCost + nextCost) {
                dist[next] = curCost + nextCost;
                pq.push({ dist[next], next });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;

    // 도로 정보를 입력받으며, 문제의 조건에 맞게 간선의 방향을 반대로 저장합니다.
    int from, to;
    long long cost;
    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        // 인터뷰 장소로의 최단 경로를 구하기 위해 간선의 방향을 반대로 저장
        edgeList[to].push_back({ from, cost });
    }

    vector<int> interviewLocations(k);
    for (int i = 0; i < k; i++) {
        cin >> interviewLocations[i];
    }

    // 멀티 소스 다익스트라 실행
    multiSourceDijkstra(interviewLocations);

    // 각 도시에서 면접 장소까지의 최단 거리가 최대인 도시를 찾습니다.
    int answerCity = 0;
    long long maxDistance = -1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > maxDistance) {
            maxDistance = dist[i];
            answerCity = i;
        }
    }

    cout << answerCity << "\n" << maxDistance << "\n";

    return 0;
}

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

이 문제도 어느 게임회사 코테에 나왔던 문제였다 코테풀기전에 이문제를 풀었다면 좋았었을텐데 지금에서야 접했다

이문제는 사이클이 하나만 있다고 가정하고 그래프릍 탐색해서 순환 구조를 파악하는 문제이다 
첫 번째로 사이클을 탐색하는 규칙은 자신으로 왔을떄 자신의 이전 노드들을 저장하고 있는다 그리고 만약에 다음노드를 방문했을때 이노드가 방문되어있고 이노드에 저장되어있던 노드가 지금 노드와 다르다면 이노드는 순환구조를 만든 노드라고 파악한다

이에 대한 코드는 아래와 같다

void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}

이렇게 dfs를 통해 방문 한 노드에 대해서 이전노드들을 검사해준다 그후 순환 노드가 파악이되었으면 pre 배열을 통해 이전 노드들을 파악해서 cycle로 체크를 해준다


이제 cycle로부터 각 노드들이 얼만큼 떨어져 있는 지 계산한다

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}

bfs를 통해 판별한다

전체 코드는 아래와같다

#include <iostream>
#include <vector>
#include <queue>
#include<cstring>
using namespace std;
bool isVisited[3001];
int pre[3001];
bool cycle[3001];
int dist[3001];
vector<int> vertex[3001];
int n;
bool hasCycle;

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}
void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}
int main() {
	cin >> n;
	int tmp1, tmp2;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2;
		vertex[tmp1].push_back(tmp2);
		vertex[tmp2].push_back(tmp1);
	}
	findCycle(1);
	memset(isVisited, false, 3001);
	bfs();
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << ' ';
	}
}

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

이 문제는 dp를 활용한 0-1 냅색 문제이다 즉 어떠한 원소를 사용할지 말지에 대해서 dp로 계속 값을 갱신해주는 것이다

예제를 표로 나면 이렇게 된다  

여기를 주목해보자 30과 10까지만 사용해서 5초를 만들었을의 최대무게는 40이였다 하지만 이제 20을 넣는다고 가정하자
여기서 5초로는 40밖에 이전에는 만들지 못했는데 20이 들어오게되면서 30과 10으로 만들었던 3초 더하기 현재 2초 5초를 만들면서 60이 된다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
int memory[101];
int cost[101];

// i번째 앱을 선택 했을 때의 비용 j dp[i][j]에는 이때의 최대 무게가 들어감
int dp[101][10001];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> memory[i];
	}
	int total = 0;
	for (int j = 1; j <= n; j++) {
		cin >> cost[j];
		total += cost[j];
	}
	int ans = 100001;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= total; j++) {
			// j가 현재 cost[i] 내가 넣으려는 cost보다 작으면 넣을 수 없으니 이전 값 사용
			if (j < cost[i])
				dp[i][j] = dp[i - 1][j];
			// 아닐 때느 나 이전까지만 넣은 애들 중에 현재 계산하려는 cost에서 나의 cost를 빼고 나의 무게를 더한거
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);

			if (dp[i][j] >= m)
				ans = min(ans, j);
		}
	}
	
	cout << ans;
}

코드로는 이렇게 된다

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

이 문제는 dfs를 통한 사이클을  검사한다 즉 dfs로 진행하면서 마무리전에는 진행 중으로 체크하다가 탐색하다가 진행중을 만나면 해당 영역은 사이클을 형성 한다 우리는 사이클의 갯수를 구해주면 된다

#include <iostream>

using namespace std;
const int MAX = 1000;

char arr[MAX][MAX];

int n, m;

int isVisited[MAX][MAX] = { 0, };

int dX[128]; int dY[128];
int cnt=0;
void dfs(int x, int y) {
	isVisited[x][y] = 1;
	int nx, ny;
	nx = x + dX[arr[x][y]];
	ny = y + dY[arr[x][y]];
	
	if (isVisited[nx][ny] == 0) {
		dfs(nx, ny);
	}
	else if (isVisited[nx][ny] == 1){
		cnt++;
	}
	isVisited[x][y] = 2;
}

int main() {
	cin >> n >> m;
	dX['U'] = -1; dY['U'] = 0;
	dX['D'] = 1; dY['D'] = 0;
	dX['R'] = 0; dY['R'] = 1;
	dX['L'] = 0; dY['L'] = -1;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (isVisited[i][j] == 0) {
				dfs(i, j);
			}
		}
	}

	cout << cnt;
}

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

이 문제는 이분탐색으로 LIS를 찾는 문제이다 이를 해결하는 과정은 해당 카테고리의 이전 게시물들을 참고하면 된다

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> lis;
int binary_search(int target) {
	int start = 0; 
	int end = lis.size() - 1;
	int mid = 0;
	while (start < end) {
		mid = (start + end) / 2;
		if (lis[mid] < target) {
			start= mid+1;
		}
		else {
			end = mid ;
		}
	}
	return start;
}

int main() {

	cin >> n;
	int idx = 0;
	int tmp;
	cin >> tmp;
	lis.push_back(tmp);
	for (int i = 1; i < n; i++) {
		cin >> tmp;
		if (tmp > lis[idx]) {
			lis.push_back(tmp);
			idx++;
		}
		else {
			lis[binary_search(tmp)] = tmp;
		}
	}

	cout << n-lis.size();

}

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

이 문제는 처음에 플로이드로 풀다가 시간초과  나서  djikstra로 변경하였다 이문제는 그냥 다익스트라를 세번 돌리면 되는데

       int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
       int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

이렇게 실제 거리와 g_h를 지나는 거리와 똑같다면 g -> h를 지나간다고 판별 할 수 있으니
이를 이용해서 목적지까지의 거리가 같으면 priority_queue에 넣은 후 차례로  pop하면 되는 문제였다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 1000000001

int t, n, m, d;
int s, g, h;
vector<pair<int, int>> edgeList[2001];
vector<int> distance_v;

void dijkstra(int start, vector<int>& dist) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist.assign(n + 1, INF);
    dist[start] = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int cur_cost = pq.top().first;
        int cur_vertex = pq.top().second;
        pq.pop();

        if (cur_cost > dist[cur_vertex])
            continue;

        for (auto next : edgeList[cur_vertex]) {
            int next_vertex = next.first;
            int next_cost = next.second;

            if (dist[next_vertex] > cur_cost + next_cost) {
                dist[next_vertex] = cur_cost + next_cost;
                pq.push({ dist[next_vertex], next_vertex });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    while (t--) {
        cin >> n >> m >> d;
        cin >> s >> g >> h;

        for (int i = 0; i <= n; i++) {
            edgeList[i].clear();
        }

        int g_h_cost = 0;
        for (int i = 0; i < m; i++) {
            int from, to, cost;
            cin >> from >> to >> cost;
            edgeList[from].push_back({ to, cost });
            edgeList[to].push_back({ from, cost });

            if ((from == g && to == h) || (from == h && to == g)) {
                g_h_cost = cost; // g-h 간선의 비용 저장
            }
        }

        // 다익스트라 실행
        vector<int> dist_s(n + 1), dist_g(n + 1), dist_h(n + 1);
        dijkstra(s, dist_s);
        dijkstra(g, dist_g);
        dijkstra(h, dist_h);

        priority_queue<int, vector<int>, greater<int>> destination_pq;
        for (int i = 0; i < d; i++) {
            int dest;
            cin >> dest;

            int route1 = dist_s[g] + g_h_cost + dist_h[dest]; // s -> g -> h -> dest
            int route2 = dist_s[h] + g_h_cost + dist_g[dest]; // s -> h -> g -> dest

            if (dist_s[dest] == route1 || dist_s[dest] == route2) {
                destination_pq.push(dest);
            }
        }

        // 결과 출력
        while (!destination_pq.empty()) {
            cout << destination_pq.top() << " ";
            destination_pq.pop();
        }
        cout << endl;
    }
}