급하게임개발

#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에서 항상 중요한건 방문했다가 나오면 다시 배열들을 초기화 해줘야 한다는 것입니다

우리가 충돌 알고리즘을 사용할 때 가장 간단 한  버전의 충돌 알고리즘이다 AABB 알고리즘이란 특정 좌표계에서 사각형혹은 직육면체 형태의 범위에 대한 충돌을 검증 할 때 사용한다

이렇게 4각형이 2개 겹쳐 있을 때 수식을 이용해서 충돌 여부를 구하는 방식이다 이방식은 3차원에서도 비슷하게 사용이 가능하다. 근데 유니티에서 제공하는 함수를 사용 하면 offset 즉 범위 확장이 불가능 했었다. 이에 해당 기능을 직접 구현했어야 했다.

구현하면서 시행착오 겪었던 내용은 Bound의 Min값과 Max값을 계속 가져왔는데 이 좌표계가 매우 이상했다 분명 다른  위치에 있는데 같은좌표를 반화하는것을 보고 Bound의 Min값과 Max값이 local position임을 깨달았다. 이에 해당 사항들을 world position으로 변경 해줘야 한다
이에 TrasnformPorint 함수를 사용해준다

    public void UpdateCoordinate()
    {
        if (meshFilter == null)
        {
            return;
        }
        MeshCollider meshCollider = GetComponent<MeshCollider>();
        Mesh mesh = meshCollider.sharedMesh;
        Bounds meshBounds = mesh.bounds;

        minCdepusOffset = transform.TransformPoint(meshBounds.min);
        maxCdepusOffset = transform.TransformPoint(meshBounds.max);
        Debug.Log(maxCdepusOffset);
        Debug.Log(minCdepusOffset);
    }
    public  void ResizeCoordinate(int offsetx, int offsety, int offsetz)
    {
        maxCdepusOffset.x += offsetx/2;
        maxCdepusOffset.y += offsety/2;
        maxCdepusOffset.z += offsetz/2;
        minCdepusOffset.x -= offsetx / 2;
        minCdepusOffset.y -= offsety / 2;
        minCdepusOffset.z -= offsetz / 2;
        Debug.Log(maxCdepusOffset);
        Debug.Log(minCdepusOffset);
    }

이렇게 2가지 함수를 작성하였다 첫번째 함수는 내가 offset을 부여하기 전에 나의 Min과 Max를 업데이트 한다.
그후 2번째 함수는 Max와 Min에 Offset을 추가해준다
그후 해당 좌표를  비교해준다 

    public bool CheckInterSect(Vector3 min1, Vector3 max1, Vector3 min2, Vector3 max2)
    {
        return (min1.x <= max2.x && max1.x >= min2.x) &&
       (min1.y <= max2.y && max1.y >= min2.y) &&
       (min1.z <= max2.z && max1.z >= min2.z);
    }

이 공식을 이용하여 세좌표로 만들어지는 영역이 겹치는 지 아닌지 확인한다

https://school.programmers.co.kr/learn/courses/30/lessons/250136

이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다 
일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다

#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}
int solution(vector<vector<int>> land) {
    int answer = 0;
    oilMap = land;
    sizeOfLandX = land.size(); //열의 길이
    sizeOfLandY = land[0].size(); //행의 길이

    for (int i = 0; i < sizeOfLandX; i++) {
        for (int j = 0; j < sizeOfLandY; j++) {
            if (isVisited[i][j] == false && land[i][j] == 1) {
                BFS(i, j);
            }
        }
    }

    for (int j = 0; j < sizeOfLandY; j++) {
        set<int> oilSet;
        int sumOfOil=0;
        for (int i = 0; i < sizeOfLandX; i++) {
            oilSet.insert(oilMap[i][j]);
        }
        set<int>::iterator iter;
        for (auto it : oilSet) {
            sumOfOil += sizeOfOil[it];
        }
        answer = max(answer, sumOfOil);
    }

    return answer;
}

일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다

자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에

void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}

BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다.
즉 map<key, value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .

이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에

for (auto iter = m.begin() ; iter !=  m.end(); iter++)
{
	cout << iter->first << " " << iter->second << endl;
}
cout << endl;

의 형태와

for (auto iter : m) {
	cout << iter.first << " " << iter.second << endl;
}

의 형태의 두가지 형태로 map을 순환 할 수 있습니다.
이에 필자는 두번째 형태로 사용하였습니다. 

이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다.
Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다
이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.

그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다

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

이 문제의 경우 전형적인 BFS 문제이다

자기와 연결되어 있는 루트를 BFS로 계속 따라가며 이어져있는 모든 점에 대해 표시만 해주면 되는 쉬운 문제다

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int N;
int arr[100][100];
int ans[100][100];
void solution(int vertex) {
	queue<pair<int, int>> bfsq;
	for (int i = 0; i < N; i++) {
		if (arr[vertex][i] == 1) {
			bfsq.push({ vertex, i });
			ans[vertex][i] = 1;
			while (!bfsq.empty()) {
				int start = bfsq.front().first;
				int end = bfsq.front().second;
				bfsq.pop();
				for (int j = 0; j < N; j++) {
					if (arr[end][j] == 1 &&ans[vertex][j]==0) {
						bfsq.push({ end,j });
						ans[vertex][j] = 1;
					}
				}
				
			}
		}
		
	}

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

	for (int i = 0; i < N; i++) {
		solution(i);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << ans[i][j]<<" ";
		}
		cout << endl;
	}
}

solution 함수를 설명을 하자면 solution  함수를 실행하면 매게변수로 vertex 즉 시작점이 넘어간다

그 후 arr를 참고하여 나와 연결되어있는 애들을 차례로 큐에 넣어준 후 차례로 pop시키며 그 애들과 연결된 애들을
계속 push한다 함과 동시에 ans배열에 값을 1로 바꿔준다.

예를들어 input으로

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

이렇게 들어 갔다고 치자 solution(1)을 실행시키면

현재 큐에 나와 연결되어 있는 0,4가 큐에 들어간다.

그후 0,4가 pop 되며 4와 연결되어 있는 4,5와 4,6이 들어간다

이와 동시에 ans[0][5]와 ans[0][6]의 값을 1로 바꿔준다.

그후 다시 4,5를 pop하면서

5,1을 큐에 넣어준다 그후 ans[0][1]을 1로 바꿔준다

그후 4,6을 pop한다

그후 6,7을 푸쉬하면서 ans[0][7]을 1로 바꿔준다

이러한 방식을 반복하면서 진행이된다. 

그럼 이런식으로 해당 Vertex와 연결되어 있는 부분을 나타내주는 배열이 만들어진다

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

이 문제의 경우 BFS기본 문제이다 그냥 2가지 BFS를 만들어 주면 된다.

첫번째는 시작점과 같은 색깔만을 가진 영역만을 BFS로 탐색하여 영역을 카운트 해주면 된다

두번째는 시작점의 색이 R이나 G일 경우 색깔이 R이나 G인영역을 BFS로 탐색하게 해주면 된다.

#include<iostream>
#include<queue>
using namespace std;
int N;
char arr[100][100];
bool normalVisited[100][100];
bool weakVisited[100][100];
int normalBFS() {
	queue<pair<int, int>> bfsQ;
	char color;
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (normalVisited[i][j])
				continue;
			color = arr[i][j];
			normalVisited[i][j]== true;
			bfsQ.push({ i,j });
			count += 1;
			while (!bfsQ.empty()) {
				int x, y;
				x = bfsQ.front().first;
				y = bfsQ.front().second;
				bfsQ.pop();
				if (x-1>=0&&!normalVisited[x - 1][y] && arr[x - 1][y] == color) {
					bfsQ.push({ x - 1,y });
					normalVisited[x - 1][y] = true;
				}
				if (x + 1 < N && !normalVisited[x + 1][y] && arr[x + 1][y] == color) {
					bfsQ.push({ x + 1,y });
					normalVisited[x + 1][y] = true;
				}
				if (y - 1 >= 0 && !normalVisited[x][y-1] && arr[x][y-1] == color) {
					bfsQ.push({ x,y-1 });
					normalVisited[x][y-1] = true;
				}
				if (y + 1 < N && !normalVisited[x][y + 1] && arr[x][y + 1] == color) {
					bfsQ.push({ x,y + 1 });
					normalVisited[x][y + 1] = true;
				}

			}
			
		}
	}
	return count;
}
int WeakBFS() {
	queue<pair<int, int>> bfsQ;
	char color;
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (weakVisited[i][j])
				continue;
			color = arr[i][j];
			weakVisited[i][j] == true;
			bfsQ.push({ i,j });
			count += 1;
			while (!bfsQ.empty()) {
				int x, y;
				x = bfsQ.front().first;
				y = bfsQ.front().second;
				bfsQ.pop();
				if (color == 'R' || color=='G') {
					if (x - 1 >= 0 && !weakVisited[x - 1][y] && (arr[x - 1][y] == 'R' || arr[x - 1][y] == 'G')) {
						bfsQ.push({ x - 1,y });
						weakVisited[x - 1][y] = true;
					}
					if (x + 1 < N && !weakVisited[x + 1][y] && (arr[x + 1][y] == 'R' || arr[x + 1][y] == 'G')) {
						bfsQ.push({ x + 1,y });
						weakVisited[x + 1][y] = true;
					}
					if (y - 1 >= 0 && !weakVisited[x][y - 1] && (arr[x][y-1] == 'R' || arr[x][y-1] == 'G')) {
						bfsQ.push({ x,y - 1 });
						weakVisited[x][y - 1] = true;
					}
					if (y + 1 < N && !weakVisited[x][y + 1] && (arr[x][y+1] == 'R' || arr[x][y+1] == 'G')) {
						bfsQ.push({ x,y + 1 });
						weakVisited[x][y + 1] = true;
					}
				}
				else {
					if (x - 1 >= 0 && !weakVisited[x - 1][y] && arr[x - 1][y] == color) {
						bfsQ.push({ x - 1,y });
						weakVisited[x - 1][y] = true;
					}
					if (x + 1 < N && !weakVisited[x + 1][y] && arr[x + 1][y] == color) {
						bfsQ.push({ x + 1,y });
						weakVisited[x + 1][y] = true;
					}
					if (y - 1 >= 0 && !weakVisited[x][y - 1] && arr[x][y - 1] == color) {
						bfsQ.push({ x,y - 1 });
						weakVisited[x][y - 1] = true;
					}
					if (y + 1 < N && !weakVisited[x][y + 1] && arr[x][y + 1] == color) {
						bfsQ.push({ x,y + 1 });
						weakVisited[x][y + 1] = true;
					}
				}

			}

		}
	}
	return count;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	cout <<normalBFS()<<" "<< WeakBFS();
}

이 문제의 경우 기본적인 BFS문제들을 여러문제 풀어봤으면 매우 쉽게 해결방법이 떠올랐을 문제이다

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

이 문제의 경우 생각해줘야할 게 많았다 일반 Bfs지만 문제를 잘 읽지 않으면 틀린다

이문제에서 간과하면 안될 조건이 있다.

1. 시작점에 사다리와 뱀이 여러개 놓일 수는 없지만 도착점은 상관없다.

2. 뱀과 사다리를 만나면 무조건 이동한다 이다 즉 발판을 밟지 못한다.

이 위를 생각하고 풀어야 빠른시간안에 풀 수 있었다 필자는 이 부분을 캐치하지 못 해 오랜시간이 걸렸다.

#include <iostream>
#include <queue>
using namespace std;
int arr[101];
int visited[101];
int radder[101];
queue<int> bfsq;
int solution() {
	bfsq.push(1);
	while (!bfsq.empty()) {
		int start = bfsq.front();
		bfsq.pop();
		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}
		if ((start + 5 <= 100) && !visited[start + 5]) {
			if (radder[start + 5] > 0) {
				if (visited[radder[start + 5]] == 0) {
					visited[radder[start + 5]] = visited[start] + 1;
					bfsq.push(radder[start + 5]);
				}
			}
			else if (radder[start + 5] == 0) {
				visited[start + 5] = visited[start] + 1;
				bfsq.push(start + 5);
			}
			if (start + 5 == 100)
				return visited[start + 5];
		}
		if ((start + 4 <= 100) && !visited[start + 4]) {
			if (radder[start + 4] > 0) {
				if (visited[radder[start + 4]] == 0) {
					visited[radder[start + 4]] = visited[start] + 1;
					bfsq.push(radder[start + 4]);
				}
			}
			else if (radder[start + 4] == 0) {
				visited[start + 4] = visited[start] + 1;
				bfsq.push(start + 4);
			}
			if (start + 4 == 100)
				return visited[start + 4];
		}
		if ((start + 3 <= 100) && !visited[start + 3]) {
			if (radder[start + 3] > 0) {
				if (visited[radder[start + 3]] == 0) {
					visited[radder[start + 3]] = visited[start] + 1;
					bfsq.push(radder[start + 3]);
				}
			}
			else if (radder[start + 3] == 0) {
				visited[start + 3] = visited[start] + 1;
				bfsq.push(start + 3);
			}
			if (start + 3 == 100)
				return visited[start + 3];
		}
		if ((start + 2 <= 100) && !visited[start + 2]) {
			if (radder[start + 2] > 0) {
				if (visited[radder[start + 2]] == 0) {
					visited[radder[start + 2]] = visited[start] + 1;
					bfsq.push(radder[start + 2]);
				}
			}
			else if (radder[start + 2] == 0) {
				visited[start + 2] = visited[start] + 1;
				bfsq.push(start + 2);
			}
			if (start + 2 == 100)
				return visited[start + 2];
		}
		if ((start + 1 <= 100) && !visited[start + 1]) {
			if (radder[start + 1] > 0) {
				if (visited[radder[start + 1]] == 0) {
					visited[radder[start + 1]] = visited[start] + 1;
					bfsq.push(radder[start + 1]);
				}
			}
			else if (radder[start + 1] == 0) {
				visited[start + 1] = visited[start] + 1;
				bfsq.push(start+1);
			}
			if (start + 1 == 100)
				return visited[start + 1];
		}
	}
}
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N+M; i++) {
		int from, to;
		cin >> from>> to;
		radder[from] = to;
	}

	cout << solution();
}

코드가 길지만  사실 실제로 보면 얼마 안되는 양이다.

일단 주목해야할 부분은

		if ((start + 6 <= 100) && !visited[start + 6]) {
			if (radder[start + 6] > 0) {
				if (visited[radder[start + 6]] == 0) {
					visited[radder[start + 6]] = visited[start] + 1;
					bfsq.push(radder[start + 6]);
				}
			}
			else if (radder[start + 6] == 0) {
				visited[start + 6] = visited[start] + 1;
				bfsq.push(start + 6);
			}
			if (start + 6 == 100)
				return visited[start + 6];
		}

이 부분이다 이부분의 경우느 일단 우리가 방문할려는 지점이 방문되었는지 또한 우리가 방문할 발판이 100을 넘었는지를 검사한다. 넘으면 실행 하지 않는다 그후 사다리나 뱀이 있다면 그 발판을 밟지 않고 이어져있는 발판을 밟는다 그 후 이를 bfs에 넣는다. 만약 사다리나 뱀이없으면 해당 발판을 밟는다. 이게 풀이 로직이었다. 

코테에서 항상 중요한 점은 빠른시간안에 반례체킹을 하는 것인거 같다.

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

이 문제는 나의 부족한 머리로는 혼자 생각 할 수 없는 알고리즘이었다.

하지만 이번 문제를 푼 것을 계기로 똑같은 유형의 문제는 틀리지 않아야 겠다.

일단 풀이는 우선순위 큐 2개로 중간 값을 구하는 방법을 알아야 한다

이게 알파이자 오메가였다.

우선순위 큐로 2개의 값을 구하는 방법은

1. MaxHeap은 무조건 MinHeap보다 사이즈가 하나 커야 한다.

2. MaxHeap의 최대값은 MinHeap의 최솟값 보다 작아야 한다. 이 조건을 만족하지 않을 시

maxHeap의 최대값과 MinHeap의 최솟값을 swap해준다.

이 법칙을 지키면 MaxHeap의 최대값은 항상 중간값이 된다.

이 풀이를 위의 문제에서 주어진 예제에 대해서 대입해보겠다.

이런 순서대로 트리가 차면서 항상 Maxheap의 최대값이 중간값을 나타내고 있다. 

코드는 아래와 같다

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,less<int>> maxq;
priority_queue<int, vector<int>, greater<int>> minq;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N;
	cin >> N;
	int inputNum;
	cin >> inputNum;
	maxq.push(inputNum);
	cout << maxq.top() << '\n';
	for (int i = 1; i < N; i++) {
		cin >> inputNum;
		if (maxq.size() == minq.size())
			maxq.push(inputNum);
		else {
			minq.push(inputNum);
		}
		if (!maxq.empty() && !minq.empty() && !(maxq.top() < minq.top())) {
			int a = maxq.top();
			int b = minq.top();

			maxq.pop();
			minq.pop();

			minq.push(a);
			maxq.push(b);
		}
		cout << maxq.top()<<'\n';
	}
}