작은시작

#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/1620

풀이

• unordered_map은 해쉬 테이블로 구현한 자료구조로 탐색 시간 복잡도는 O(1)입니다.
• map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)입니다.

저는 2개의 unordered_map을 선언하여 string,int를 구분지어서 만들었습니다.

조심해야 할 점은 count() 선언을 까먹지 말고 써주지 않고 직접 배열을 찾는 방식 (num [i]) 은 그 자체로 노드가 선언되므로 count()를 사용합시다!

코드

#include<iostream>
#include<vector>
#include<unordered_map>
#include<queue>
#include<string>
using namespace std;
int N, M;
unordered_map<string, int> st;
unordered_map<int,string> num;
int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		string a;
		cin >> a;
		st.insert({ a,i });
		num.insert({ i,a });

	}
	vector<string>result;
	//M입력찾기
	for (int j = 0; j < M; j++) {
		
		string arr;
		cin >> arr;
		
		if (arr[0] < 'A') { //숫자라면
			if (num.count(stoi(arr))>0) {
				result.push_back(num[stoi(arr)]);
			}
		}
		else { //영어 
			if (st.count(arr) > 0) {
				result.push_back(to_string(st[arr]));
			}
		}
		

	}

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

	return 0;
}