작은시작

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N, M, X;
vector<pair<int,int>> node[2][1010];
int arr[2][1010];

void dijk(int a) {
	priority_queue<pair<int, int>> pq;
	arr[a][X] = 0;
	
	pq.push({ 0,X });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (arr[a][here] < cost) continue;


		for (int i = 0; i < node[a][here].size(); i++) { // 경유가 더 싼지 확인
			int via_cost = node[a][here][i].second + cost;
			if (via_cost < arr[a][node[a][here][i].first]) {
				arr[a][node[a][here][i].first] = via_cost;
				pq.push({ -via_cost , node[a][here][i].first });

			}
			

		}




	}


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


	for (int i = 1; i <= M; i++) {
		int a, b, ti;

		cin >> a >> b >> ti;

		node[0][a].push_back({ b,ti });
		node[1][b].push_back({ a,ti }); //역방향 만들어주기 

	}

	dijk(0); //정방향


	dijk(1); //역방향
	int max_cost = 0;
	int tmp = 0;
	for (int i = 1; i <= N; i++) {
		if (arr[0][i] + arr[1][i] > max_cost) {
			max_cost = arr[0][i] + arr[1][i];


		}

	}
	cout << max_cost;
	return 0;
}

문제

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

설명

4방향을 계속해서 체크해주면 되는 문제이며 아무 생각 없이 BFS를 떠올리지 말자

또한 여러 우선순위 조건이 있을 때는 Priority_queue를 쓰는 것도 좋은 방법인 것 같다.

마지막으로 for문 여러 개 중첩 시 순서를 잘 설계하고 코드 구현에 들어가자!! (+배열 인덱스 주의)

코드 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N;
int map[21][21];
bool visited[21][21];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };

struct Student {
	int num;
	int arr[4];

};
Student human[2000];
struct ABC {
	int blank;
	int like_num;
	int r;
	int c;

};
struct cmp {
	bool operator()(ABC a,ABC b) {
		//1,2,3 각각 우선순위 배정
		if (a.like_num == b.like_num) {

			if (a.blank == b.blank) {
				if (a.r == b.r) {
					return a.c > b.c;
				}

				return a.r > b.r;
			}
			return a.blank < b.blank;
		}
		return a.like_num < b.like_num;
	}
};
priority_queue<ABC, vector<ABC>, cmp> pq;
void findSit(int y,int x,int k) {
	int like_cnt = 0;
	int blank_cnt = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		for (int j = 0; j < 4; j++) {
			if (map[ny][nx] == human[k].arr[j]) {
				like_cnt++;
			}
		}
		
		if (map[ny][nx] == 0) {
			blank_cnt++;
		}
	}

	pq.push({ blank_cnt,like_cnt,y,x });

}
int main() {
	cin >> N;

	for (int i = 0; i < N * N; i++) {
		cin >> human[i].num;
		for (int j = 0; j < 4; j++) {
			cin >> human[i].arr[j];
		}

	}

	for (int i = 0; i < N * N; i++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (map[y][x] == 0) {
					findSit(y, x,i);
				}
			}
			
		}
		map[pq.top().r][pq.top().c] = human[i].num; //자리배정완료 
		//pq초기화 까먹지말자
		while (!pq.empty()) {
			pq.pop();
		}

	}
	//만족도조사
	int answer = 0;
	
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				int score = 0;
				for (int i = 0; i < N * N; i++) {
					if (map[y][x] == human[i].num) {

						for (int j = 0; j < 4; j++) {
							int ny = y + dy[j];
							int nx = x + dx[j];
							if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
							for (int k = 0; k < 4; k++) {
								if (map[ny][nx] == human[i].arr[k]) {
									score++;
								}
							}
						}

					}
				}

				if (score == 1) answer += 1;
				if (score == 2) answer += 10;
				if (score == 3) answer += 100;
				if (score == 4) answer += 1000;

			}

		}



	


	cout << answer;

	return 0;
}

문제

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

풀이

문제를 보면 입력값이 -4000부터 +4000까지 입력될 수 있다. 

이를 위해 입력부터 +4000을 해주고 max값 8000까지 배열을 할당하도록 하자.

최빈값 조건만 유의한다면 다음과 같이 풀 수 있다.

코드

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int N;
vector<int> arr;
vector<int> result;
int map[8002]; //-4000~8000
int main() {
	//N홀수 
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		arr.push_back(a);


	}
	// 산술평균
	int temp = 0;
	for (int j = 0; j < arr.size(); j++) {
		temp += arr[j];
	}
	result.push_back(round((double)temp / arr.size()));

	//중앙값
	sort(arr.begin(), arr.end());
	result.push_back(arr[arr.size() / 2]);

	//최빈값, 여러개 존재하면 두번째로 작은값`
	for (int i = 0; i < arr.size(); i++) {

		map[arr[i]+4000]++;

	}
	int max = 0;
	int check = 0;

	for (int i = 0; i < 8001; i++) {
		if (max < map[i]) {
			max = map[i];
			check = i;

		}
		
	}

	for (int j = check + 1; j < 8001; j++) { // 최빈값 여러개일경우
		if (map[j] == max) {
			check = j;
			break;
		}

	}

	result.push_back(check-4000);

	//범위
	result.push_back(arr[arr.size() - 1] - arr[0]);


	
	for (int k = 0; k < result.size(); k++) {
		cout << result[k] << '\n';
	}
	return 0;
}

문제

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

풀이

분할 재귀 방식의 문제였다. 분할, 재귀가 필요하다는 것을 보자마자 알 수 있었지만 구현하는데 까지는 시간이 좀 걸렸다.  타 블로그를 활용하였다. 

참고 블로그 : https://mygumi.tistory.com/284

중요한 점은 코드내에서 y, x는 항상 해당하는 사분면의 가장 왼쪽 위라고 판단하여 시작한다. 

또한 해당하는 사분면이 아니라고 판단시 size^2를 더해주고 다음 재귀를 타서 사분면을 이동시킨다.

또한, 주의해야할점은 원하는 좌표를 찾았을 때 바로 결괏값을 출력하고 리턴하여 끝내줘야 한다. 다시 main문으로 result를 끌고 오면 else문을 타고 돌아올 수 있어서 result값이 변경될 수 있다. 

코드 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, R, C;
int result;
void Z(int y, int x, int size) { //y,x는 각각 사분면 시작 왼쪽위,왼쪽아래를 향함

	if (y == R && x == C) {
		cout << result;
		return;
	}

	if (R < y+size && C < x+size && R >=y && C >= x) { // 사분면 내에 존재시

		//분할재귀
		Z(y, x, size / 2); // 1사분면
		Z(y, x+size/2, size / 2); // 2사분면
		Z(y+size/2, x, size / 2); // 3사분면
		Z(y+size/2, x+size/2, size / 2); // 4사분면

	}
	else { //사분면 내 존재 안할시 다음사분면 이동

		result += size * size;
	}
}
int main() {

	cin >> N >> R >> C;

	Z(0, 0, (1 << N));

	
	return 0;
}