작은시작

문제

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

문제

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

풀이

기본 그래프 문제처럼 풀었다. 알고리즘 분류 및 타 블로그에는 플로이드 와샬로 많이 푼 것 같다. 

하지만 기본 DFS 그래프 탐색으로도 풀 수 있을 것 같아서 그렇게 풀었다. 이런 그래프 문제는 2차원 배열 형식으로 풀기보단 Vector를 사용하는 것이 생각하기 좀 더 수월한 것 같다. 

visited배열을 활용하여 기본 Cycle방지 + 인덱스에 값을 할당하였다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N;
vector<int> map[101];
int visited[101];
void dfs(int k) {

	for (int i = 0; i < map[k].size(); i++) {
		if (visited[map[k][i]] == 0) {
			visited[map[k][i]] = 1; //다음칸
			dfs(map[k][i]);
		}
	}

}
int main() {
	cin >> N;
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int a;
			cin >> a;
			if(a==1)map[y].push_back(x);

		}
	}


	for (int i = 0; i < N; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i);
		
		for (int j = 0; j < N;	j++) {
			cout << visited[j] << " ";
		}
		cout << '\n';
	}

	return 0;
}

문제

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

풀이

기본 최대 힙 구성 문제였다.

C++의 Priority_queue 를 활용하였다.

최소힙 문법 문제는 아래를 참고하자. 

https://trevor522.tistory.com/89

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int> pq;
vector<int> result;
int  main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 0) {
			if (pq.empty()) {
				result.push_back(0);
			}
			else {
				result.push_back(pq.top());
				pq.pop();
			}


		}
		else {
			pq.push(a);
		}
		



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

	}



	return 0;
}

문제

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

풀이

최소힙 기본연습문제이다. 

C++ 의 Priority_queue를 활용하였다. 

최소 힙 같은경우  priority_queue<int,vector<int>,greater<int>> 를 사용하면 된다. 

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

priority_queue<int, vector<int>, greater<>> pq;
vector<int> result;
int  main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == 0) {
			if (pq.empty()) {
				result.push_back(0);
			}
			else {
				result.push_back(pq.top());
				pq.pop();
			}


		}
		else {
			pq.push(a);
		}
		



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

	}



	return 0;
}