급하게임개발

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

이  문제의경우 LIS 를 사용할 줄 알면 쉬운 문제이다
그후 LIS의 값과 뒤의 인덱스부터의 LIS

#include <iostream>
using namespace std;
int arr[1000] = { 0, };
int n;
int ascendingNum[1001];
int descendingNum[1001];
int maxNum=0;
void getAsc() {
	for (int i = 1; i <= n; i++) {
		ascendingNum[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) {
				ascendingNum[i]=max(ascendingNum[j] + 1,ascendingNum[i]);
			}
		}
	}
}


void getDsc() {
	for (int i = n; i > 0; i--) {
		descendingNum[i] = 1;
		for (int j = n; j > i; j--) {
			if (arr[i] > arr[j]) {
				descendingNum[i] = max(descendingNum[j] + 1, descendingNum[i]);
			}
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	getAsc();
	getDsc();
	for (int i = 1; i <= n; i++) {
		if (ascendingNum[i]+descendingNum[i] > maxNum) {
			maxNum = ascendingNum[i] + descendingNum[i];
		}
	}

	cout << maxNum-1;
}

의 값의 합이 최댓값이 되는 부분을 고른후 -1 해주면 된다 -1을 하는 이유는 해당 방식으로 순열을 고르면 그 범위에서  수가 겹침으로 1개를 빼주는 것이다 41퍼대에서 에러가났는데 그 이유는 dp 배열을 1001로해야하는데 1000으로 해서 틀렸었다

LIS 를 설명 하자면
우리 의 테스트 케이스를 리스트로 넣어보자

이렇게 될것이다 왼쪽 아래에 0을 넣은 이유는 1이전에는 증가하는 수열이 0이기 때문에 넣었다

그리고 1까지 가장 긴  증가하는 순열을 1이다

5일 때는 2이다

자 이제 2일 때를 보자 2일때 가장 증가하는 부분순열은 나 이전에 나보다 작은 애까지의 부분순열의 최댓값을 넣어 주면 된다 즉 나의 이전에 값들중 나보다 작은 값들의 증가하는 부분순열의 최대값들을 더하는 것이다 예시로 더 설명 하도록 하겠다

완성된 그림을 보자 뒤에서 부터 2번째의 5를 보자 얘보다 작은 애들중 가장  큰인덱스는 8번째인덱스의  4이다 해당인덱스의 나를 붙이면 해당 사이즈의 +1이 되기에 5이다

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

솔직히 이 문제는 못 풀었다 풀이를 보고나서 이해를 할 수 있었다 이 문제의 코드는 그리 길지 않지만 하나의  로직을 아는사람이 풀 수 있었다.  핵심로직은 내가 어떠한 무게추를 들고 있다고 가정하자 일단 1이라는 무게추가 있다고 가정 하자 1이라는 무게추가 있을 때 다음 무게추가 지금 내가 가지고 있는 무게추의 무게보다 크게 되면 사이 무게인 2를 만들 수없다.

다른 예시로 현재 내가 1,1,2 이렇게 총 3개의 무게추를 가지고 있는데 다음 무게추로 6이 들어오게 되면 나는 4를 만들 수  없다

즉 현재 내가 가지고 있는 총 무게추의 무게보다 작은 무게들을 다 만들 수 있을 때 다음에 사용할 무게추는 내가 가지고 있던 총 무게보다 작아야 한다.

해당  로직이 이문제를 풀 수 있게 하는 핵심 로직이었다

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

int N;
int arr[1000];

int main() {

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

    sort(arr, arr + N);

    int res = 1;
    for (int i = 0; i < N; i++) {
        if (arr[i] > res) {
            break;
        }
        res += arr[i];
    }

    cout << res;
}

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

이 문제는 투 포인터 문제이다 이중 포문으로도 구현이 가능하나 해당 방식으로 할경우 시간 복잡도가 커진다 이에 루프문 한개로 해당 문제를 해결하는 게 핵심이다

이 문제의 로직은 일단 이어지는 선들을 최대한 길게 이어진  후 끊어졌을 때 부터 선을 다시 쭉 길게 이어서 이 선 2개의 길이의 합을 구하는 것이다

주어진 테스트 케이스를 v1.first를 기준으로 정렬하면 해당 그림 처럼 된다. 아래칸은 시작점 위에 칸은 끝나는 점을 의미한다. 이 리스트는 오름차순 정렬을 했다고 가정했기에 첫번째로 나오는 선은 1부터 시작해서 길게 늘일 것이다 즉 첫번째 상태일때

이렇게 된다 그후에 2부터 5까지를 비교했을 때 이 두선은 이어짐으로 start는 그대로 두고 end를 5로 바꿔준다 

그 다음 3부터 5까지도 이 선과 끝점은 같지만 시작점이 다름으로 기존에 있던 선임으로 포함을 시키지 않는다 아직도 start는 1 end 는 5이다
그 후 6과 7을 만났을때는 아래그림처럼 된다

6과 7을 만났을 때는 새  선임으로 기존에 있던 선의 길이를 일단 값을 누적시켜준후 리스틀 끝나지 탐색한후 해당 start와 end값을 다시 더해준다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	int sum = 0;
	cin >> n;

	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int n1, n2;
		cin >> n1>>n2;
		v.push_back({ n1,n2 });
	}
	sort(v.begin(), v.end());
	int start = v[0].first;
	int end = v[0].second;
	for (int i = 1; i < n; i++) {
	

		if (end > v[i].first) {
			end = max(v[i].second, end);
		}
		else {
			sum += end - start;
			start = v[i].first;
			end = v[i].second;
		}

	
	}
	sum += end - start;
	cout << sum;
}

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

이 문제의 경우 그리디와 비트 마스킹  문제이다 처음에는 while문으로 코드를 작성했으나 해당 문제를 해결 하려했으나 실패 했다. 이에 비트  마스킹을 사용해서 문제를 풀어야 함을 깨달았다. 이 문제를 풀기 위한 생각은 

3리터짜리 물병을 생각해 보면 2리터 물병 하나 1리터 물병이 있다고 가정 하자. 얘를  물병 한개짜리를 만드는 방법은 1리터짜리 물병을 하나더해서 2리터짜리를 만든후 4리터 물병을 만드는 방법이다

즉 이문제를 풀기  위해서는 가장 작은 물병들을 계속 그다음 큰 물병들로 만들면서 진행 해야한다 자 대표적인 예로
2번째 테스트 케이스를 예시로 생각해봅시다

이 문제의 경우 0번째  칸에 있는 1리터짜리 물병을 일단 큰물병으로 만들어보자 1+1 해서 2리터로 만든다 그 후 최소 물병과 다른  물병의 갯수를 저장해놓고 일단  계속 가장 작은 물병을 다음 큰 물병으로 변경시켜 가면서 물병을 합치면서 크기를 늘리면서 갯수를 줄이는 로직이다 그후 최소 물병의  갯수를  만족하면 로직진행을 끝내면 된다

#include<bitset>
#include<iostream>
using namespace std;
int main() {
	int n, k;
	int ans=0;
	cin >> n >> k;
	while (true) {
		int temp = n;
		// 현재 1을 못만났다는 의미
		int firstOnidx = -1;
		//  내가  가지고 있는 물병의 갯수
		int cnt=0;
		// 내가 비교하려는 인덱스의 번호
		int idx = 0;
		
		//현재 물병의 수를 세는 로직
		while (temp) {
			if (temp & 1) {
				if (firstOnidx == -1)
					firstOnidx = idx;
				cnt++;
			}
			idx++;
			//다음 번째 인덱스를 비교하기 위해 오른쪽으로 1칸 이동
			temp >>= 1;
		}
		//
		if (cnt <= k) {
			break;
		}
		else {
			//가장 작은 양이 담겨져 있는 물병을 합쳐서 다음  크기의 물병을 만들기 위함 반복하다보면 원래있던 더큰 크기의 물병과 합쳐지면서 크기가 줄어듬
			n += (1 << firstOnidx);
			//산 물병의  갯수 크기2짜리 물병은 1개짜리 물병 2개 합친것
			ans += (1 << firstOnidx);
		}

		
	}
	cout << ans;
}

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

이 문제의 경우 그리디 문제이다 이 문제의 경우 Priority Queue로 풀면 쉽게 풀리는  문제였다. 일단 나는 이 문제를 보고 냅색문제 와 비슷 하다고 생각했다. 

일단 나는 이문제의 숙제의 중요도를 숙제의 점수 라고 생각 했다 이에 우선순위 큐에 과제를 끝냈을 때의 점수가 가장 높은것들 순으로 나열 시켰다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

우리의 테스트 케이슬 중요도 즉 과제를 맞췄을 때의 점수를 해당로직대로 내림차순 정렬 하게 되면 아래 그림 처럼 된다

우리가 실제로 과제를 한다 생각 해 보자 우리는 당연히 가장 중요한걸 될 수 있는  한 최대한 미룰 것이다 즉 첫번째 4,60은 아직 4일 차에 내가 할 일이 없으므로 60에 중요도를 가진 과제를 한다.

그후 오는 2,50은 아직 2일차에 아무일도 없으므로 50에 일을 한다 

그 후 4,40의 일은 4일 안에만 하면 되나 4일차에는 60의 일이 있으므로 4일보다 앞에 배정한다 그래서 3일 차에 40의  일을 한다

그후 3,30은 이미 3일차에 40의 일을 하였으니 3일안에 내가 할수 있는 요일은 1일차 밖에 없다 이에 30의 일은 1일 차에 한다

그후 1,20의 일은 이미 1일차에 30의 일을 하니 하지 않는다

그후 4,10의   일도 이미 4일 안에 진행 하는 일들은 다 중요도 가 높으므로 진행 하지않는다
그후 6,5는 6일차는  비어 있으므로 넣는다

즉 이문제의 풀이는 날짜를 최대한 미루데 중요한거를 우선 해서 리스트에 넣어야 한다 이에 만약 내가 4,40의 일을 한다고 가정했을 때 지금 업무를 완료했을 때의점수순으로 나열했기에 후에 나보다 낮은 일수가 나온다고 해도 점수가 높지 않고 일수도 낮고 점수도 낮은게 나올 수가 없으므로 빈공간에 채워주는 식으로 로직을 진행해야 한다

#include<iostream>
#include<queue>
using namespace std;
int day[1001] = {};
struct Compare {
    bool operator()(pair<int, int> const& p1, pair<int, int> const& p2) {
        return p1.second < p2.second;
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;
int main() {
    int N;
    cin >> N;
    int num1, num2;
    int maxIdx=0;
    int result = 0;
    for (int i = 0; i < N; i++) {
        cin >> num1 >> num2;
        if (num1 > maxIdx) {
            maxIdx = num1;
        }
        pq.push({ num1,num2 });
    }

    while (!pq.empty()) {
        int x, y;
        x = pq.top().first;
        y = pq.top().second;
        pq.pop();
        if (day[x]== 0) {
            day[x] = y;
        }
        else {
            for (int i = x - 1; i > 0; i--) {
                if (day[i] == 0) {
                    day[i] = y;
                    break;
                }
            }
        }

    }
    for (int i = maxIdx; i > 0; i--) {
        result += day[i];
    }
    cout << result;
}

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

이 문제의 경우 DP중에 LCS라는 것에 공부해보았으면 풀 수 있는 문제 였다 처음 보고 나서 부분 순서가 아닌 부분수열로 보아서 틀렸었다 이에 LCS 알고리즘에 대해  공부한 푸니 그리 어렵지 않은 문제였다

#include <iostream>
#include <cstring>
using namespace std;
#define max(a, b) (a > b ? a : b)

int LCS[1002][1002];
char str[1003];
char str2[1003];

int main()
{
	cin >> str >> str2;
	int i, j;
	i = 1;
	while (i <= strlen(str))
	{
		j = 1;
		while (j <= strlen(str2))
		{
			if (str2[j - 1] == str[i - 1])
			{
				LCS[i][j] = LCS[i - 1][j - 1] + 1;
			}
			else
			{
				LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
			}
			j++;
		}
		i++;
	}
	printf("%d", LCS[i - 1][j - 1]);
}

맨 처음 

아래 와 같은 표를 만들준다 만들어 주게 되면 7X7 배열이 될텐데 이는 비교하지 않았을 때 에 대한 값 0을 넣어주기 위함이다.

이에 우리가 각 행 마다 채워넣어줄 것은 각각 행까지의 문자들을 열까지의 문자들과 비교했을 때 최대로 나오는 부분 수열의 크기를 넣어줘야한다 이를 바탕으로 다음 수열의 최댓값을 찾을 것이다

즉 C를 열들의 문자와 비교한다 1행 1열이 0인이유는 C를 A까지 비교했을떄 나오는 부분수열이 없기 떄문이다 그후 C를 A C라는 문자열과 비교했을 때 부분수열로 나온것은 C이니 1 지금 집합 C에서의 부분수열이 1밖에 나올수 없으므로 1만채워주게 된다 

그 후 두번째 줄은 C A에서의 부분수열값과 A의 부분수열값을 비교해주게 되는데 C A와 A는 하나의 부분수열 만 공유한다 C A와 A C 도마찬가지이다 C혹은 A만을 공유하기에 1이다 단 이제 C A와 A C A를 비교해주게 되면 현재 C A로 부분수열이 만들어진다 이것은 즉이것은 C만을 비교했을 때 이미 부분수열이 1이었고 그다음 A를 비교했을 때 이부분이 현재 같으므로 이전에  가져왔던 값에 +1을 해주게 된다
그림을 완성 하게 되면 

이런식으로 된다 즉 이  문제를 푸는 핵심은 x축으로의 문자열 과 y축으로 문자열을 비교해서 즉 y 인덱스 까지의 수열에서  행의 문자열들과 몇개가 유사한지를 찾는 것이다 이 부분에서 사용되어야 할게 나의 이전에 문자이다 . 예로 
A C A  와 C A를  비교했다고 가정하자 이미 C를 검사했을 때 x축의 C 의 이후 문자들에서는 무조건 1개의 부분수열이 발생한다는 의미이고  C A와 검사했을 때 C까지 이미 1인 부분수열이 있었으므로 A를 만났을 때  A의 이전까지의 최대 부분수열의 갯수와 지금 일치한 대각선의 값이 +1되게 하여 증가시키는 것이다 즉 A C 와 C를 비교했을 때 이미 1개의 부분수열이 존재함으로 A C A 와 C A 를 비교했을때 +1을 해주게 되는 것이

결국에 이식의 점화식은

LCS[i][j] = LCS[i - 1][j - 1] + 1;

LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);

이렇게 2개가 되는데 
같은 문자를 발견했을 때는 나의 이전 문자까지  비교했을 때의 최대 부분수열의 구성요소 갯수 +1을 해야함으로 i-1과 j-1인덱스의 값에서 +1을 증가시킨다

반대로 틀릴경우에는 즉 y축에서의 나의 이전의 값을 가져오거나 나까지 비교하기전에 최대 부분수열의 인덱스를 가져오게 된다

#include <queue>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int a, b;
bool visited[10000];
int logicD(int num) {
    return (num * 2) % 10000;
}

int logicS(int num) {
    return num - 1 < 0 ? 9999 : num - 1;
}

int logicL(int num) {
    return (num % 1000) * 10 + (num / 1000);
}

int logicR(int num) {
    return num / 10 + (num % 10) * 1000;
}
void bfs()
{
    queue<pair<int, string>> q;
    q.push(make_pair(a, ""));
    visited[a] = true;

    while (!q.empty())
    {
        int cur_num = q.front().first;
        string cur_op = q.front().second;
        q.pop();

        if (cur_num == b)
        {
            cout << cur_op << '\n';
            return;
        }

        int D, S, L, R;
        D = logicD(cur_num);
        if (!visited[D])
        {
            visited[D] = true;
            q.push(make_pair(D, cur_op + "D"));
        }
        S = logicS(cur_num);
        if (!visited[S])
        {
            visited[S] = true;
            q.push(make_pair(S, cur_op + "S"));
        }
        L = logicL(cur_num);
        if (!visited[L])
        {
            visited[L] = true;
            q.push(make_pair(L, cur_op + "L"));
        }
        R = logicR(cur_num);
        if (!visited[R])
        {
            visited[R] = true;
            q.push(make_pair(R, cur_op + "R"));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;

    while (T--)
    {
        cin >> a >> b;
        memset(visited, false, sizeof(visited)); // 초기화
        bfs();
    }

    return 0;
}

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

이 문제는 최소시간을 구하는 것이기에 BFS로 조건을 만족시켰을 경우 바로 출력할 수있도록 코드를 작성하여야 합니다

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

이 문제의 경우 그냥 쉬운 DFS였다 골드 4라고하기에는 많이 애매한 문제라고 생각되어진다.
DFS와 단짝인 백트래킹과 조건 검사식만 설정해주면 되는 문제였다.

#include<iostream>
using namespace std;
int isVisited[20][20];
bool isUsed[26];
char arr[20][20];
int maxNum = 0;
int GetIdxOfAlphabet(char ch);
bool isCanGo(int idxX, int idxY) {
	if (idxX < 0 || idxY < 0 || idxX>19 || idxY > 19 || (isVisited[idxX][idxY] == true) || (isUsed[GetIdxOfAlphabet(arr[idxX][idxY])]==true)) {
		return false;
	}

	return true;
}
void dfs(int startX, int startY, int cnt) {
	if (!isCanGo(startX, startY)) {
		if (cnt-1 > maxNum) {
			maxNum=cnt-1;
			return;
		}
	}
	else {
		isUsed[GetIdxOfAlphabet(arr[startX][startY])] = true;
		isVisited[startX][startY] = true;
		dfs(startX + 1, startY, cnt + 1);
		dfs(startX -1, startY, cnt + 1);
		dfs(startX, startY+1, cnt + 1);
		dfs(startX, startY-1, cnt + 1);
		isUsed[GetIdxOfAlphabet(arr[startX][startY])] = false;
		isVisited[startX][startY] = false;
	}
}

int GetIdxOfAlphabet(char ch) {
	if (ch >= 'A' && ch <= 'Z') {
		int position = ch - 'A';
		return position;
	}
	else
		return 0;
}
int main() {
	int r, c;
	cin >> r >> c;
	char inputString[21];
	for (int i = 0; i < r; i++) {
		cin >> inputString;
		for (int j = 0; j < c; j++) {
			arr[i][j] = inputString[j];
		}
	}
	dfs(0, 0, 1);
	cout << maxNum;
	return 0;
}

이 문제의 경우 입력 string으로 받을 시 문제가 생겨서 해당 부분을 char 배열을 입력받도록 변경하였습니다.
또한 항상 이전에 dfs를 풀때 조건식을 위에다가사용했을 때 너무 복잡해지는 현상이 있어 함수로 해당 부분을 따로 정ㄴ리해 놓았습니다

DFS에서 항상 중요한건 방문했다가 나오면 다시 배열들을 초기화 해줘야 한다는 것입니다