급하게임개발

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

반도체 회로가 얽이지 않기 위해서는
우리는 해당 회로의 LIS를 구하면 된다

이 문제는 내가 이전에 풀었던 LIS 문제를 dp가 아닌 이분탐색으로 푸는 문제이다

해당 이미지를 보고 우리는 LIS즉 이전 인덱스가 현재 인덱스보다 커지지 않게 해주면 된다

이문제의 풀이는 
첫번째로 LIS 배열을 만들어주고 LIS는 무조건 1이상 일것이다 이에 LIS[0]에 arr[0]를 넣어준다

그후 우리는 2

가지 규칙으로 해당 문제를 풀어주면 된다
현재 내가 보는 숫자가 LIS의 가장 나중 인덱스의값보다 크면  그 나중인덱스 + 1 위치에 해당 수를 넣어주고

작을 시에는 해당 LIS 배열에서 해당 수가 들어갈 적절한 위치를 이분탐색으로 찾아서 해당 위치에 해당수를넣어주면된다

#include <iostream>

using namespace std;

int arr[40000];
int lis[40000];

int binarySearch(int left, int right, int target) {
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (lis[mid] < target) {
			left = mid + 1;
		}
		else {
			right = mid;
		}
	}
	return right;
}
int n;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int j = 0;
	int i = 1;

	lis[0] = arr[0];

	while (i < n) {
		if (lis[j] < arr[i]) {
			lis[j + 1] = arr[i];
			j += 1;
		}
		else {
			int pos = binarySearch(0, j, arr[i]);
			lis[pos] = arr[i];
		}

		i += 1;
	}

	cout << j + 1;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int n;
vector<bool> initial, target;

// 스위치를 누르는 함수
void pressSwitch(vector<bool>& bulbs, int index) {
    if (index > 0) bulbs[index - 1] = !bulbs[index - 1];
    bulbs[index] = !bulbs[index];
    if (index < n - 1) bulbs[index + 1] = !bulbs[index + 1];
}

// 전구를 바꾸는 함수 (첫 번째 전구를 누를지 여부 선택 가능)
int solve(bool pressFirst) {
    vector<bool> bulbs = initial;
    int count = 0;

    // 첫 번째 전구를 누르는 경우
    if (pressFirst) {
        pressSwitch(bulbs, 0);
        count++;
    }

    // 앞에서부터 필요한 곳만 스위치 누르기
    for (int i = 1; i < n; i++) {
        if (bulbs[i - 1] != target[i - 1]) {
            pressSwitch(bulbs, i);
            count++;
        }
    }

    // 결과 확인
    if (bulbs == target) return count;
    return INT_MAX;  // 불가능한 경우
}

int main() {
    cin >> n;
    initial.resize(n);
    target.resize(n);

    // 초기 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        initial[i] = (ch == '1');
    }

    // 목표 전구 상태 입력
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        target[i] = (ch == '1');
    }

    // 두 가지 경우 비교
    int result = min(solve(false), solve(true));

    // 정답 출력
    if (result == INT_MAX) cout << -1;
    else cout << result;
}

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

이 문제를 풀 때 나는 현재 스위치를 기준으로 나와 양옆이 다르면 스위치를 누르려했으나 그게 아니었다 그냥 앞에서 부터 보면서 스위치를 기준으로 이전 전구가 다르면 스위치를 누르는데 0번스위치부터 할건지 1번스위치 부터 누를건지 2개의 경우의 수를 구해서 그중 최솟 값을 구하면 되는 거였다 0번스위치와 1번스위치로 나눈 이유는 0번 스위치의 값을 결정 할수 있는경우 지금 누르거나 다음에 누르거나 두가지 경우의수밖에없기 때문에 우리는 이전 상태를 비교함으로 0번스위치가 1일때의 시작과 0일때의 시작을 모두 비교해보는 것이다

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

이 문제는 m 으로 입력받아야하는데 n으로 입력받아서 로직으로는 맞는데 계속 틀린값이 나와서 멘탈나갈뻔했다 일단 이문제는 그냥 이제 i->j 로갈때의 첫번째 노드를 저장해놓는 배열을 따로 만들어 놓고 해당 배열을 통해 지속적으로 업데이트 해주면 되는 문제였다

#include <iostream>
using namespace std;
#define INF 200000000

// 여기는 경로 코스트 저장
int arr[201][201];
// 여기는 j로 가는 가장 먼저 방문해야 할 곳 저장
int arr2[201][201];

int n, m;

int main() {
    cin >> n >> m;
    int t1, t2, t3;

    // 거리 배열 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                arr[i][j] = 0;
            }
            else {
                arr[i][j] = INF;
                arr2[i][j] = j;  // 초기 방문 노드를 j로 설정
            }
        }
    }

    // 간선 정보 입력
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        arr[t1][t2] = t3;
        arr[t2][t1] = t3;
        arr2[t1][t2] = t2;
        arr2[t2][t1] = t1;
    }

    // 플로이드-워셜 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                    arr2[i][j] = arr2[i][k]; // i -> j로 가는 첫 방문 노드 업데이트
                }
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) cout << "- ";
            else cout << arr2[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}