급하게임개발

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

이 문제는 처음 보고 어떻게 풀어야지라는 생각이 너무들었다 골드 3부터는 여러알고리즘이 섞여 어떻게 딱풀어야지라고 생각이 안나는 거같다

이 문제는 일단 조합으로 우리는 2차원 배열에서 원소를 뽑아줄것이다 원소를 뽑을 때는 1차원 배열이라고 생각해서 뽑아야한다

즉 위표와 같이 0,0 은 0번 0,1은 1번 이라고 생각해야한다 이거를 구하는 방법은 다음과 같다
행/5 + 열%5 를 하면 몇번짼지 우리는 알수 있다 이를 바탕으로 우리는 일차원 배열에서 7개를 뽑은 후 해당 7개의 원소가 서로 이어져 있고 S의 갯수가 4보다 많은지만 검사하면 된다

검사는 우리가 조합으로 뽑은 7개의 원소를 bfs 로 검사한다 즉 bfs로 특정 방향들을 탐색 한다 만약 끊어져있는 부분이 생기면큐에 원소가 들어가지 않을 테니 연속되지 않음을 우리는 알수 있다 전체 코드는 아래와 같다

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

char grid[5][5];
int ans = 0;
bool isConnected(vector<int> selected) {
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    int cnt = 1;
    bool isVisited[25] = { false, };
    bool sel[25] = { false, };

    for (int i = 0; i < 7; i++) {
        sel[selected[i]] = true;
    }

    queue<int> bfsQ;
    bfsQ.push(selected[0]);
    isVisited[selected[0]] = true;

    while (!bfsQ.empty()) {
        int cur = bfsQ.front();

        int r = cur / 5;
        int c = cur % 5;

        bfsQ.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i];
            int nc = c + dy[i];
            if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5)
                continue;
            int nxt = nr * 5 + nc;


            if (!isVisited[nxt] && sel[nxt]) {
                isVisited[nxt] = true;
                bfsQ.push(nxt);
                cnt++;
            }
        }
    }

    return cnt == 7;
}
void dfs(int start, int count, int sCount, vector<int> selected) {
    if (count == 7) {
        if (sCount >= 4 && isConnected(selected)) {
            ans += 1;
        }
        return;
    }
    if (sCount + (7 - count) < 4)
        return;

    for (int i = start; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;

        selected.push_back(i);

        if (grid[r][c] == 'S') {
            dfs(i + 1, count + 1, sCount + 1, selected);
        }
        else {
            dfs(i + 1, count + 1, sCount , selected);
        }

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

    // 5x5 격자 입력 받기
    for (int i = 0; i < 5; i++) {
        string line;
        cin >> line;
        for (int j = 0; j < 5; j++) {
            grid[i][j] = line[j];
        }
    }

    vector<int> selected;
    dfs(0, 0, 0, selected);
    cout << ans << "\n";

    return 0;
}

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

}