급하게임개발

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

이 문제는 내가 처음 접한 외판원 순회 문제이다 처음에는 브루트포스와 백트래킹을 사용하여 모든 경우의 수를 돌면서 최소의 값을 출력하려고 했으나 시간복잡도가 오바가 될것으로 판단되어 다른사람들의 풀이를 보니 비트마스킹과 dp를 조합하여 이미 방문한  노드의 대해서는 검사하지 않는 다는 것을 파악한 상태로 알고리즘을 구현하였다.

int n, map[16][16];
int dp[16][1 << 16];

n은 우리가 input 받을 노드의 수다
그리고 dp 배열에 우리는 [1<<16]을 해주는데  이것의 의미는 0번 부터 15번을 방문 하지 않았다고 초기화 시켜 놓는 것이다

우리는 깊이 우선 탐색을 통해 해당 알고리즘을 풀것이다 자 이런 외판원 문제는 무조건 사이클을 갖고 있다 그럼으로 어느 한지점을 start 및 Endpoint로 잡아도 값이 똑같이 나온다 필자는 0을 StartPoint를 두고 풀겠다

    if (visit == (1 << n) - 1) { //탐색 완료
        if (map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

자 이조건 부터 보자 visit의 값 즉 우리가 어느 노드를 방문했는지를 나타내는 visit값이 2의 n승 -1은 n-1 번까지 다 1이된다 즉 0부터  n-1  노드까지 n개의 노드를 다 방문 했다는 것을 의미한다 다 방문했는데 map[cur][0]은 0번으로 돌아갈수 있는 길이 없다는 것을  의미한다. 이럴경우 이동이 불가능 하다

자 이조건을 통과한후

    if (dp[cur][visit] != -1) 
        return dp[cur][visit];

이 조건을 보자 이조건의 의미는 이미 방문한 상태값을 가지고 이미 탐색한적이 있으면 더이상 탐색하지 않는다는 얘기다
즉 우리가 이전에 dp를 초기화 -1 로 초기화 시켜놓았는데 dp[cur][0101] 이 -1이 아니면 우리는 0번과 2번을 방문한 상태에서의 dfs를 돌렸다는 얘기이다 이때 우리는  이를 다시 할 필요 없으므로 해당 값을 return 해준다  자 여기 까지 왔으면

    for (int i = 0; i < n; i++) {
        if (map[cur][i] == 0) //길 X
            continue;
        if ((visit & (1 << i)) == (1 << i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1 << i));
    }

이 로직이 남았다 이 로직의 경우 현재 어디어디를 방문하고 현재 내위치에서 갈수 있는 영역을 탐색한다.
visit값을 통해 내가 앞으로 나아가야할 곳이 이미 내가 방문했다면 그 위치를 더 방문할 필요가없으니 continue를 한다
그후에는 min을 통해  현재까지 내가 찾은 최솟값과, 지금 내위치에서 다음위치로 갈 비용 + 다음 위치에서 찾은 min 값을 받으므로서  최솟 값을 갱신 해준다

전체 코드는 아래와 같다

#include <iostream>
#include <cstring>
using namespace std;
int n; int dp[16][1 << 16];
int map[16][16];
#define INF 987654321
int dfs(int cur, int visit) {
	if (visit == (1 << n) - 1) {
		if (map[cur][0] == 0) {
			return INF;
		}
		return map[cur][0];
	}

	if (dp[cur][visit] != -1) {
		return dp[cur][visit];
	}

	dp[cur][visit] = INF;

	for (int i = 0; i < n; i++) {
		if (map[cur][i] == 0)
			continue;
		if ((visit & (1 << i)) == (1 << i))
			continue;
		dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | (1 << i)));
	}
	return dp[cur][visit];
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 1);
}

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