급하게임개발

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

이 문제의  경우 풀이는 매우 쉽다.

우리는 중계기를 설치  할건데 이 중계기의 빈공간의 합이 최소가 되게 고르면 된다 그이유는 일단 중계기는 어떠한 점이 아닌 직선형의 중계기 이다 

빈 공간은 무조건 우리가 설치한 센서들의 갯수인 n-1 개 만 설치가 된다

즉 이 n-1개의 빈공간 들중 우리는 가장 큰 영역을 제외해주어야 한다 근데  센서 2개로 영역을 고른다고 가정 할 때 우리가 결국 포기해야하는 영역들 중 이영역을 k개로 나누기 위해서는 결국 k-1개의 공간은 포기를 해야한다

#include <iostream>
#include <algorithm>
#include <vector>
int n, k;
using namespace std;
vector<int> sensors;
vector<int> spaces;
int main() {
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		sensors.push_back(tmp);
	}

	sort(sensors.begin(), sensors.end());
	int beforeSensor = sensors[0];
	for (int i = 1; i<sensors.size(); i++) {
		spaces.push_back(sensors[i] - beforeSensor);
		beforeSensor = sensors[i];
	}
	
	sort(spaces.begin(), spaces.end());

	int sum = 0;
	
	for (int i = 0; i < (int)spaces.size() -  (k-1); i++) {
		sum += spaces[i];
	}

	cout << sum;
}

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

이 문제는 처음에 그리디를 어떤 방식으로 짜는지가 문제 풀이의 핵심이다

처음에 나는 숫자가나온 갯수에 따라 그리디를 선택 했지만
1700 에서 사용하는 스케줄링 방식은 가장 오랫동안 안쓰는 원소를 교체하는 방식으로 그리디를 작성 한다
이에 큐를 사용하여 나오는 위치를 저장해주고 이를 이용해서 비교해줌으로서 값을 출력하는 방식을 사용했다

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int arr[100];
int concent[100];
queue<int> useCount[101];
bool isUsed[100] = { 0, };
int main() {
	int cnt = 0;
	int input = 0;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> arr[i];
		useCount[arr[i]].push(i);
	}
	int i = 0;
	while (input < n && i < k) {
		if (!isUsed[arr[i]]) {
			isUsed[arr[i]] = true;
			concent[input] = arr[i];
			useCount[arr[i]].pop();
			i++;
			input++;
		}
		else {
			useCount[arr[i]].pop();
			i++;
		}
	}
	if (n > k) {
		cout << 0;
		return 0;
	}

	else {
		for (int j = i; j < k; j++) {
			int willPlug = arr[j];
			useCount[arr[j]].pop();
			int outConcnet=-1;
			int notUse=0;
			bool isIn = false;
			for (int l = 0; l < n; l++) {
				if (concent[l] == willPlug) {
					outConcnet = l;
					isIn = true;
					break;
				}
				
			}
			if (!isIn) {
				for (int l = 0; l < n; l++) {
					if (useCount[concent[l]].empty()) {
						outConcnet = l;
						break;
					}
					if (notUse < useCount[concent[l]].front()) {
						notUse = useCount[concent[l]].front();
						outConcnet = l;
					}
				}
			}
			if (concent[outConcnet] != willPlug) {
				concent[outConcnet] = willPlug;
				cnt += 1;
			}
		}
	}

	cout << cnt;
}

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

문제가 개노가다다 생각 하고 구현하기는 쉬운데 매우 귀찮다 로직은 간단 하다
위로 올릴 경우 내위에 애와 내가 같으면  위에 애를  *  2 하고 그리고 이동 시켰다고 체크 한후 
이동 시킨애는 위로 이동 됬을 거니 굳이 이후 배열에 값을 넣어 주지 않는다.

#include <iostream>
#include <algorithm>
#include <cstring> // For memset
using namespace std;

int n;
int arr[20][20];
int maxBlock = 0;

// 배열 이동 처리 (상하좌우)
void moveArray(int dir, int beforeArr[20][20], int afterArr[20][20]) {
    memset(afterArr, 0, sizeof(int) * 20 * 20); // 결과 배열 초기화
    bool isCombined[20][20] = { false }; // 블록 합쳐진 상태 확인

    if (dir == 0) { // 위로 이동
        for (int j = 0; j < n; j++) {
            int target = 0; // 이동 시킬 애
            for (int i = 0; i < n; i++) {
                if (beforeArr[i][j] == 0) continue;
                if (target > 0 && afterArr[target - 1][j] == beforeArr[i][j] && !isCombined[target - 1][j]) {
                    afterArr[target - 1][j] *= 2;
                    isCombined[target - 1][j] = true;
                }
                else {
                    afterArr[target++][j] = beforeArr[i][j];
                }
            }
        }
    }
    else if (dir == 1) { // 아래로 이동
        for (int j = 0; j < n; j++) {
            int target = n - 1; // 이동 시킬 애
            for (int i = n - 1; i >= 0; i--) {
                if (beforeArr[i][j] == 0) continue;
                if (target < n - 1 && afterArr[target + 1][j] == beforeArr[i][j] && !isCombined[target + 1][j]) {
                    afterArr[target + 1][j] *= 2;
                    isCombined[target + 1][j] = true;
                }
                else {
                    afterArr[target--][j] = beforeArr[i][j];
                }
            }
        }
    }
    else if (dir == 2) { // 왼쪽으로 이동
        for (int i = 0; i < n; i++) {
            int target = 0;// 이동 시킬 애
            for (int j = 0; j < n; j++) {
                if (beforeArr[i][j] == 0) continue;
                if (target > 0 && afterArr[i][target - 1] == beforeArr[i][j] && !isCombined[i][target - 1]) {
                    afterArr[i][target - 1] *= 2;
                    isCombined[i][target - 1] = true;
                }
                else {
                    afterArr[i][target++] = beforeArr[i][j];
                }
            }
        }
    }
    else if (dir == 3) { // 오른쪽으로 이동
        for (int i = 0; i < n; i++) {
            int target = n - 1; // 이동 시킬 애
            for (int j = n - 1; j >= 0; j--) {
                if (beforeArr[i][j] == 0) continue;
                if (target < n - 1 && afterArr[i][target + 1] == beforeArr[i][j] && !isCombined[i][target + 1]) {
                    afterArr[i][target + 1] *= 2;
                    isCombined[i][target + 1] = true;
                }
                else {
                    afterArr[i][target--] = beforeArr[i][j];
                }
            }
        }
    }
}

// 재귀적으로 모든 경우 탐색
void solve(int cnt, int beforeArr[20][20]) {
    if (cnt == 6) {
        // 최댓값 갱신
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxBlock = max(maxBlock, beforeArr[i][j]);
            }
        }
        return;
    }

    for (int dir = 0; dir < 4; dir++) { // 네 방향으로 이동
        int afterArr[20][20];
        moveArray(dir, beforeArr, afterArr);
        solve(cnt + 1, afterArr);
    }
}

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

    solve(0, arr);
    cout << maxBlock << endl;
    return 0;
}

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

이 문제는 내가 투포인터에 넣어놓은 LIS 문제에 이분탐색 버전이다 이전에 어떠한 코테 시험에서 봤을 때 LIS를 투포인터로 풀어서 시간 초과가 히든 테케에서 발생했었는데 이 방식으로 풀었어야 한거 같다

백준 에서 제공 하는 해당 테스트케이스를 예로 들어보자

일단 LIS를 저장하는 LIS 배열이 있다고 생각하자.

LIS 배열이 비었을 때 10을 넣을 수 가 있다

이렇게 되어있는 상황에서 20을 넣는다고 가정할 때 현재 10만 들어가 있는 LIS에서 가장 큰원소이자 마지막 원소인 10보다 20이 크기 떄문에 LIS 배열의 다음 인덱스에 20을 넣어준다

자 그후 10을 넣으려고 보면 10이 들어갈 자리는 10 과 20중에 자기 와 같은 크기의 원소인 10밖에 없다
그럼 으로 해당 10을 최근에 10으로 바꾼다
그후 30을 넣게 되면

자 이과정을 반복하면 우리는 LIS의 크기를 구할 수 있다
이문제를 풀때의 핵심은
1. LIS 배열이 비었을 때 그냥 원소 넣기
2. LIS 에 있는 원소보다 현재 집어넣을 원소가 클때 끝에 넣기
3. LIS 에 마지막원소(가장큰 원소) 보다 작을 떄 이분탐색으로 들어가야 할 위치 찾아서 넣기

이렇게 하면 결국에 LIS 배열의 크기는 LIS의 크기만큼만  된다

#include <iostream>
using namespace std;
int n;
int arr[1000000];
int lis[1000000];
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 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;
}

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

이 문제는 위상정렬 알고리즘을 사용하는 문제이다
https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093

해당 게시물을 참조하면 이해가 쉬울 것이다
즉 순서에 맞춰서 나열 하면 되는게 위상 정렬 이다

이 문제에서는 어떠한 노드 가 나로 올수 있는 점입차수 라는것을 들고 있어야 한다 점입차수가 0이면 먼저 뽑아도 무방한 노드라고 보면 된다 즉 우리는 이문제를 풀때 점입차수를 비교해가며 큐에 넣어서 pop 하면 되는 문제이다

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

int main() {
	int n, m;
	cin >> n >> m;
	int inCount[100001] = { 0, };
	vector<vector<int>> v(n + 1);
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		v[tmp1].push_back(tmp2);
		inCount[tmp2]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inCount[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		cout << q.front() << " ";
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			inCount[v[idx][i]] -= 1;
			if (inCount[v[idx][i]]<=0)
				q.push(v[idx][i]);
		}
		q.pop();
	}
}

일단 전체 코드는 이렇게 된다
입력 받을 때 어떠한 노드를 입력 받고 이노드가 갈수 있는 노드도 Vector에 넣어 놓느다 그후  연결 된 노드의 점입  차수를 1증가 시킨다  이렇게 입력 을 받은 후
우리는 해당 vector를 순회하면 서 일단 점입차수가 0인걸 queue에다가 넣는다
그후 while문으로 큐를 순회하면서 점입차수가 0인 걸 팝해주면 나와 연결된 노드들의 점입 차수를 1감소시켜준다 그렇게 점입차수가 0인 노드들을 지속적으로 queue에 넣었다 팝해주면 해당 문제는 풀린다

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

이 문제는 그리디이다 이문제는 얼피하면 그냥 정렬한후 처리처리 하게 하는거로 생각해서 틀릴 수가 있다 이문제의 경우 최소의 해를 그리디로 만족 시키기위해서는 큰 화물을 처리할 수 있는 화물은 최대한 큰것 부터 처리 해야한다는 것이다
백준에서 제공 하는 3번 input을 이용해서 보자

이렇게 테스트 케이스가 주어졌을때
Krane 을 처리 할 수 있는 무게에 따라 오름 차순 정렬해주면
23 25 28 32 이렇게 정렬이 된다
이제 화물을 오름 차순으로 정렬해보자
2 5 7 10 16 18 20 24 27 32 이렇게 정렬이 된다.

이후 3번째 크레인이 처리 할수 있는 최대 무게는 32 임으로 해당 크레인은 일단 32를 처리 한다
2번 째크레인은 27을 처리하고 1번째 크레인은 24를  0번째 크레인은 23을 처리한다
이렇게 처리하면 1초가 지나간다

그 후 크레인은 내가 현재 보고있는 화물이 이미 처리되어있으면 다음 화물을 처리하기 위해서 내가 지금 있는 위치에서 이전 위치까지 탐색하다 화물이 안처리되었으면 처리하면 된다 이렇게 로직이 가능한 이유는 오름차순 정렬을 했기 때문에 내가 처리한 화물 이전에 있는 화물들은 다처리 할 수 있기 때문이다

코드는 아래와 같다

#include<iostream>
#include<algorithm>
using namespace std;
int krane[50];
int cargo[10000];
int kraneidx[50];
bool isDo[10000];
// 각 Krane이 처리할수 있는 최대 무게의 index저장
int clear;
int n, m;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin>>krane[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin>>cargo[i];
	}
	sort(krane, krane + n);
	sort(cargo, cargo + m);
	if (krane[n - 1] < cargo[m - 1]) {
		cout << -1;
		return 0;
	}
	int maxKrane = n - 1; 
	for (int i = m - 1; i >= 0; i--) {
		if (maxKrane < 0)
			break;
		if (krane[maxKrane] >= cargo[i]) {
			kraneidx[maxKrane] = i;
			maxKrane--;
		}
	}
	for (int i = 0; i <= maxKrane; i++) {
		kraneidx[i] = -1;
	}
	int cnt = 0;
	maxKrane = kraneidx[n - 1];
	while (maxKrane > 0) {
		maxKrane = kraneidx[n - 1];
		for (int i = n - 1; i >= 0; i--) {
			if (kraneidx[i] < 0)
				continue;
			if (!isDo[kraneidx[i]]) {
				isDo[kraneidx[i]] = true;
			}
			else {
				while (isDo[kraneidx[i]] && kraneidx[i]>=0) {
					kraneidx[i] -= 1;
				}
				if(kraneidx[i] >= 0)
					isDo[kraneidx[i]] = true;
			}
		}
		if (kraneidx[n - 1] < 0)
			break;
		cnt += 1;
	}
	cout << cnt;
}

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

이 문제의 경우 비트 마스킹 문제 였다 정확히는 비트마스킹을 이용한 브루트 포스가 맞다
비트마스킹을 통해 모든 경우의 수에 대해 구한후 푸는 문제였다
각  재료의 사용 여부를 나타내는 표를 한번 그려보겠다

그릴시 이러한 이미지  가  만들어  진다 즉 사용하면 1 사용하지 않으면 0  위에표는 2번 4번을 사용하고 5개의 재료로 만들수 있는 32개의 경우의 수중 10번 조합이라고 보면된다 그이유는 이진수 01010은 10이기 때문이다
여기 까지 구했으면 우리는 각 조합마다의 재료의 합과 비용의 합을 구한다

그 다음 조건을 만족했을 경우 Map 에다가 가격과 해당 가격에 대한 조합들을  저장해준다 그후 만족한 조합의 최소 가격의 map에서 vector에 조합들이 저장되어 있을 것이고 해당 조합을 오름 차순으로 정렬하여 출력해 주면 된다

#include<bitset>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define INF 200000000
using namespace std;
int n;
map<int, vector<vector<int>>> nutritient_map;
int mp_sum, mf_sum, ms_sum, mv_sum, mc_sum;
int costMax = INF;
struct nutritient {
	int p, f, s, v, c;
};
int main() {
	int mp, mf, ms, mv;
	cin >> n >> mp >> mf >> ms >> mv;
	nutritient arr[15];
	for (int i = 0; i < n; i++) {
		cin >> arr[i].p >> arr[i].f >> arr[i].s >> arr[i].v >> arr[i].c;
	}
	for (int i = 1; i <  (1 << n); i++) {
		mp_sum = mf_sum = ms_sum = mv_sum = mc_sum = 0;
		vector<int> v;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				mp_sum += arr[j].p;
				mf_sum += arr[j].f;
				ms_sum += arr[j].s;
				mv_sum += arr[j].v;
				mc_sum += arr[j].c;
				v.push_back(j + 1);
			}
		}

		if (mp_sum >= mp && mf_sum >= mf && ms_sum >= ms && mv_sum >= mv) {
			if (costMax >= mc_sum) {
				costMax = mc_sum;
				nutritient_map[costMax].push_back(v);
			}
		}
	}
	if (costMax == INF) {
		cout << -1 << endl;
	}
	else {
		cout << costMax << endl;
		sort(nutritient_map[costMax].begin(), nutritient_map[costMax].end());
		for (int i : nutritient_map[costMax][0]) {
			cout << i << " ";
		}
	}
}

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

이 문제의 경우 브루트 포스긴 하나 모든 경우의 수에 대해 bfs를 이용해서 푸는 문제였다 bfs를 브루트포스하여 푸는 문제니 부르트포스 문제일 수도 있고 bfs 문제일 수도 있다 이문제의 경우 bfs를 구현할 줄 알면 큰  문제가 없다 본인의 경우 2%의  오류가 났었는데 해당 이유는 처음 bfs를 실행할 때 해당 위치가 'W'인지를 검사 하지 않아서 발생 했었다

#include<iostream>
#include<queue>
using namespace std;
int n, m;
char arr[50][50];
int isVisited[50][50] = { 0, };
int maxLength=0;
queue<pair<int, int>>bfsQ;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m && !isVisited[x][y] && arr[x][y]=='L')
		return true;
	else
		return false;
}
void bfs(int sx, int sy) {
	bfsQ.push({ sx,sy });
	isVisited[sx][sy] = 1;
	while (!bfsQ.empty()) {
		int sx = bfsQ.front().first;
		int sy = bfsQ.front().second;
		int distance = isVisited[sx][sy];
		bfsQ.pop();
		for (int i = 0; i < 4; i++) {
			if (canGo(sx + dx[i], sy + dy[i])) {
				bfsQ.push({sx + dx[i],sy + dy[i]});
				isVisited[sx + dx[i]][sy + dy[i]] = distance + 1;
			}
		}
	}
}
int getMaxValue() {
	int maxValue=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			maxValue=max(maxValue, isVisited[i][j]);
		}
	}
	return maxValue-1;
}
void InitIsVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			isVisited[i][j] = 0;
		}
	}
}
int main() {
	cin >> n >> m;
	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 (canGo(i, j)) {
				bfs(i, j);
				maxLength = max(maxLength, getMaxValue());
				InitIsVisited();
			}
		}
	}
	cout << maxLength;
}