'알고리즘/바킹독의 실전 알고리즘' 카테고리의 글 목록 (2 Page) :: erikanes's Macchiato

알고리즘/바킹독의 실전 알고리즘

PREV 이전 1 2 3 4 5 6 NEXT 다음

[0x18] 그래프

2022. 8. 7. 21:26

정점과 간선으로 이루어진 자료구조

차수 : 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수

방향 그래프 : 두 정점 사이에 진출차수(indegree)와 진입차수(outdegree)가 존재하는 그래프

무방향 그래프 : 두 정점 사이에 방향이 존재하지 않는 그래프

순환 그래프 : 사이클이 존재하는 그래프

비순환 그래프 : 사이클이 존재하지 않는 그래프

완전 그래프 : 모든 정점끼리 간선으로 연결된 그래프

연결 그래프 : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프

단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

그래프는 꼭 연결되어 있을 필요도 없고, 두 정점 사이의 간선이 반드시 1개 이하일 필요도 없으며 간선이 반드시 두 정점을 연결해야 할 필요도 없다.

그래프의 표현법

정점이 V개, 간선이 E개일 때,

인접 행렬 : 어떤 두 정점이 연결되어 있는지를 O(1)에 알 수 있다. 2차원 배열을 사용하므로 O(V²)의 공간을 필요로 한다.

어떤 정점에 연결되어 있는 모든 정점의 목록을 알아내고 싶을 때도 개수와 무관하게 O(V)의 시간복잡도를 가진다.

연결여부를 많이 확인할 때, 혹은 간선의 개수가 V²에 가까울 때 효율적이다.

인접 리스트 : O(V+E)의 공간을 필요로 한다.

특정 정점에 연결된 모든 정점들을 자주 확인할 때, 혹은 간선의 개수가 V²보다 훨씬 적을 때 효율적이다.

일반적인 그래프 문제에서 두 정점이 연결되어있는지를 반복적으로 확인해야 하는 경우는 잘 없다.

BFS

진행 순서

시작하는 정점을 큐에 넣고 방문했다는 표시를 남긴다
큐에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행한다
해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다
큐가 빌 때 까지 2번을 반복한다

모든 정점이 큐에 최대 한번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V²)의 시간복잡도를 가진다.

// 연결 그래프에서의 순회
vector<int> adj[10];
bool vis[10];
void bfs() {
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& nxt : adj[cur]) {
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
		}
	}
}

// 연결 그래프에서 1번 정점과의 거리
vector<int> adj[10];
int dist[10];
void bfs() {
	fill(dist, dist + 10, -1);
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& nxt : adj[cur]) {
			if (dist[nxt] != -1) continue;
			q.push(nxt);
			dist[nxt] = dist[cur]+1;
		}
	}
}

// 연결 그래프가 아닐 때 순회
vector<int> adj[10];
bool vis[10];
int v = 9; // 정점의 수
void bfs() {
	queue<int> q;
	for (int i = 1; i <= v; ++i)
	{
		if (vis[i]) continue;
		q.push(1);
		vis[1] = true;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			cout << cur << ' ';
			for (auto& nxt : adj[cur]) {
				if (vis[nxt]) continue;
				q.push(nxt);
				vis[nxt] = true;
			}
		}
	}
}

1926: 그림 문제를 해결할 때 사용한 방법을 그대로 가져오면 된다.

DFS

진행 순서

시작하는 정점을 스택에 넣고 방문했다는 표시를 남긴다
스택에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행한다
해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문햤다는 표시를 남기고 해당 칸을 스택에 삽입한다
스택이 빌 때 까지 2번을 반복한다

모든 정점이 스택에 최대 한번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V²)의 시간복잡도를 가진다.

비재귀적으로 구현하는것은 bfs에서 큐를 스택으로 바꾸면 된다.

// 연결 그래프에서의 순회, 재귀
vector<int> adj[10];
bool vis[10];
void dfs(int cur) {
	vis[cur] = true;
	cout << cur << ' ';
	for (auto& nxt : adj[cur])
	{
		if (vis[nxt]) continue;
		dfs(nxt);
	}
}

스택 메모리의 제한이 별도로 작게 설정된 곳에서는 재귀 대신 스택을 써서 구현해야 한다.

비재귀 DFS는 순회를 잘 수행하지만 엄밀히 말해서 관념적으로 생각하는 DFS와 방문 순서가 다르다.

재귀 DFS와 방문순서를 같게 하려면 방문 전에 방문표시를 남기고 push를 수행해야 한다

// 연결 그래프에서의 순회, 비재귀 (재귀와 같은 방문순서)
vector<int> adj[10];
bool vis[10];
void dfs() {
	stack<int> s;
	s.push(1);
	while (!s.empty())
	{
		int cur = s.top();
		s.pop();
		if (vis[cur]) continue;
		vis[cur] = true;
		cout << cur << ' ';
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt]) continue;
			s.push(nxt);
		}
	}
}

코딩테스트 레벨에서는 bfs대신 dfs를 써야하는 상황이 별로 없다.

연습 문제

11724: 연결 요소의 개수

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1002];
bool vis[1002];
int v, e, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (vis[i]) continue;
		queue<int> q;
		q.push(i);
		vis[i] = true;
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();
			for (auto& elem : adj[cur])
			{
				if (vis[elem]) continue;
				q.push(elem);
				vis[elem] = true;
			}
		}
		ans++;
	}
	cout << ans;

	return 0;
}

무방향 그래프이므로 양쪽에 push_back을 해주어야 한다.

1260: DFS와 BFS

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1002];
bool bvis[1002];
bool dvis[1002];
int n, m, v;

void dfs(int s)
{
	dvis[s] = true;
	cout << s << ' ';
	for (auto& elem : adj[s])
	{
		if (dvis[elem]) continue;
		dfs(elem);
	}
}

void bfs(int& s)
{
	queue<int> q;
	q.push(s);
	bvis[s] = true;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& elem : adj[cur])
		{
			if (bvis[elem]) continue;
			q.push(elem);
			bvis[elem] = true;
		}
	}
	cout << '\n';
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> v;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for (int i = 1; i <= n; ++i)
		sort(adj[i].begin(), adj[i].end());

	dfs(v);
	cout << '\n';
	bfs(v);

	return 0;
}

스택은 재귀방식으로 편하게 구현해봤다

기본 문제

2606: 바이러스

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[101];
bool vis[101];
int v, e, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
			ans++;
		}
	}
	cout << ans;

	return 0;
}

기초적인 bfs 문제

5567: 결혼식

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[501];
int vis[501];
int v, e, ans;

void bfs(int st)
{
	fill(vis + 1, vis + v + 1, -1);
	queue<int> q;
	q.push(st);
	vis[st] = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt] != -1) continue;
			vis[nxt] = vis[cur] + 1;
			q.push(nxt);
			if (vis[nxt] > 2) return;
			ans++;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	bfs(1);
	cout << ans;

	return 0;
}

차수가 2 이하인 간선과 연결된 정점만 카운트

11403: 경로 찾기

#include <bits/stdc++.h>
using namespace std;

int adj[101][101];
int ans[101][101];
int v;

void bfs(int& st)
{
	bool vis[101] = {};
	queue<int> q;
	q.push(st); // 순환할수도 있으므로 여기서 방문처리를 하지 않는다
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i = 1; i <= v; ++i)
		{
			if (vis[i] && cur == i)
			{
				ans[st][i] = 1;
				continue;
			}
			if (adj[cur][i] && !vis[i])
			{
				q.push(i);
				vis[i] = true;
				ans[st][i] = 1;
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v;

	for (int i = 1; i <= v; ++i)
	{
		for (int j = 1; j <= v; ++j)
		{
			cin >> adj[i][j];
		}
	}

	for (int i = 1; i <= v; ++i) bfs(i);
	for (int i = 1; i <= v; ++i)
	{
		for (int j = 1; j <= v; ++j) cout << ans[i][j] << ' ';
		cout << '\n';
	}

	return 0;
}

2660: 회장뽑기

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int adj[51][51];
int v;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v;

	for (int i = 1; i <= v; ++i)
	{
		fill(adj[i] + 1, adj[i] + v + 1, INF);
		adj[i][i] = 0;
	}

	while (true)
	{
		int a, b;
		cin >> a >> b;
		if (a + b < 0) break;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}

	for (int k = 1; k <= v; ++k)
	{
		for (int i = 1; i <= v; ++i)
		{
			for (int j = 1; j <= v; ++j)
			{
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
				adj[j][i] = adj[i][j];
			}
		}
	}

	map<int, vector<int>> m;
	for (int i = 1; i <= v; ++i)
	{
		int mx = 0;
		for (int j = 1; j <= v; ++j) mx = max(mx, adj[i][j]);
		m[mx].push_back(i);
	}

	auto& t = m.begin()->second;
	sort(t.begin(), t.end());
	cout << m.begin()->first << ' ' << t.size() << '\n';
	for (auto& i : t) cout << i << ' ';

	return 0;
}

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x1A] 위상 정렬 (0)	2022.08.08
[0x19] 트리 (0)	2022.08.08
[0x17] 우선순위 큐 (0)	2022.08.07
[0x16] 이진 검색 트리 (0)	2022.08.06
[0x15] 해시 (0)	2022.08.06

[0x17] 우선순위 큐

2022. 8. 7. 02:33

우선순위 큐

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

원소의 추가 O(logN)

우선순위가 가장 높은 원소의 확인 O(1)

우선순위가 가장 높은 원소의 제거가 O(logN)

원소가 들어오면 정점의 왼쪽 자식부터 채워지기 때문에 항상 균형이 잘 맞는 이진 트리가 된다.

최대 힙, 최소 힙이 있다.

가장 크거나 작은값의 확인은 O(1)에 확인이 가능하지만 N번째의 크거나 작은값의 확인은 불가능하다.

STL priority_queue

기본적으로 최대 힙이다.

최소 힙으로 사용하려면 선언시 priority_queue<int, vector<int> greator<int>>로 선언하면 된다.

priority_queue에서 할 수 있는건 set에서도 할 수 있고 시간복잡도도 동일하지만 set보다 수행속도가 빠르고 공간을 적게 차지한다.

custom compare를 사용할 때 주의할점은 vector 등의 동적 배열에서의 sort custom compare는 컨테이너의 front가 의도한 대로의 최소/최대값이 되지만 우선순위 큐에서는 top이 컨테이너의 back이기 때문에 반대로 사용해야 한다.

pop을 하면 back이 튀어나오는 것이다.

그렇기 때문에 최대/최소값을 top에 두고싶으면 false를 반환해서 뒤로 계속 보내야 한다. (vector는 true)

내림차순 정렬시 앞의 원소보다 뒤의 원소보다 크다면 false, 오름차순 정렬시 true를 반환해야 한다.

sort와 우선순위 큐의 custom compare가 함수와 구조체로 다른 이유는 sort는 함수지만 우선순위 큐는 컨테이너이기 때문이다.

struct comp
{
	bool operator()(const int& a, const int& b)
	{
		// return a > b; 최소힙
    		// return a < b; 최대힙
	}
};

연습 문제

11286: 절댓값 힙

#include <bits/stdc++.h>
using namespace std;

struct comp
{
	bool operator()(const int& a, const int& b)
	{
		const int ta = abs(a);
		const int tb = abs(b);
		if (ta == tb) return a > b;
		return ta > tb;
	}
};

priority_queue<int, vector<int>, comp> q;
int n, x;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--)
	{
		cin >> x;
		if (x != 0)	q.push(x);
		else
		{
			if (!q.empty())
			{
				cout << q.top() << '\n';
				q.pop();
			}
			else cout << 0 << '\n';
		}
	}

	return 0;
}

custom compare 함수의 조건을 잘 생각해야한다. sort의 custom compare와는 조건이 반대다.

1715: 카드 정렬하기

#include <bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>, greater<>> q;
int n, x, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	while (n--)
	{
		cin >> x;
		q.push(x);
	}
	while (q.size() > 1)
	{
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		ans += a + b;
		q.push(a + b);
	}
	cout << ans;

	return 0;
}

의외로 간단한 문제였는데 너무 생각을 짧게했는지 해답에 도달하지 못했음

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x19] 트리 (0)	2022.08.08
[0x18] 그래프 (0)	2022.08.07
[0x16] 이진 검색 트리 (0)	2022.08.06
[0x15] 해시 (0)	2022.08.06
[0x14] 투 포인터 (0)	2022.08.05

[0x16] 이진 검색 트리

2022. 8. 6. 23:41

트리의 정의

정점(=노드) : 각각의 원소

루트 : 가장 꼭대기에 있는 정점

리프 : 자식이 없는 정점

간선 : 정점끼리 연결하는 선

서브트리 : 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리

이진트리 : 각 노드의 자식이 2개 이하인 트리

이진 검색 트리

왼쪽 서브트리의 모든 값은 부모의 값보다 작고, 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리

이진 검색 트리를 이용하면 insert, erase, find, update 모두 O(logN)에 처리할 수 있다.

이진 검색 트리를 사용해야 하는 문제가 있다면 map/set을 사용하면 된다.

보통 unordered_map/set이 조금더 빠르지만 해시충돌이 빈번하게 일어난다면 얘기가 달라지므로 언제나 O(logN)을 보장해주는 map/set을 이용하는게 낫다.

하지만 O(logN)중에서도 느린편이다.

코딩 테스트에서 STL을 사용하지 못하는 경우 이진 검색 트리로 풀 수 있을것 같은 문제라 하더라도 해시나 이분 탐색과 같은 다른 방법을 이용하는 풀이를 고민해야 한다.

연습 문제

7662: 이중 우선순위 큐

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		multiset<int> h;
		int k;
		cin >> k;
		while (k--)
		{
			char a;
			int b;
			cin >> a >> b;
			if (a == 'I')
				h.insert(b);
			else
			{
				if (h.empty()) continue;
				if (b == 1)	h.erase(prev(h.end()));
				else h.erase(h.begin());
			}
		}
		if (!h.empty()) cout << *h.rbegin() << ' ' << *h.begin();
		else cout << "EMPTY";
		cout << '\n';
	}
}

삭제할 때 prev(h.end())가 아니라 h.rbegin()을 넣어봤더니 reverse_iterator는 erase 할 수 없었다.

iterator로 변환해주는 base()를 쓰게되면 해당 iterator 그대로 변환되는게 아니라 이전 iterator가 반환된다.

또한 iterator가 아닌 참조한 값을 지우게 되면 중복값이 싸그리 지워지기 때문에 이 문제에서는 적합하지 않다.

1202: 보석 도둑

아직 내가 쉽게 이해할만한 문제가 아니라 패스함

기본 문제

21939: 문제 추천 시스템 Version 1

#include <bits/stdc++.h>
using namespace std;

int n, m;
map<int, set<int>> h;

int main(void)
{
	cin >> n;
	while (n--)
	{
		int a, b;
		cin >> a >> b;
		h[b].insert(a);
	}

	cin >> m;
	while (m--)
	{
		string s;
		cin >> s;
		if (s == "recommend")
		{
			int a;
			cin >> a;
			if (a == 1)	cout << *(prev(h.end())->second.rbegin()) << '\n';
			else cout << *h.begin()->second.begin() << '\n';
		}
		else if (s == "add")
		{
			int p, l;
			cin >> p >> l;
			h[l].insert(p);
		}
		else
		{
			int a;
			cin >> a;
			for (auto& it : h)
			{
				if (it.second.find(a) != it.second.end())
				{
					it.second.erase(a);
					if (it.second.empty()) h.erase(it.first);
					break;
				}
			}
		}
	}
}

map에 set을 쳐박아놔서 find->remove를 수행할 때 이점을 다 날려버리고 선형탐색을 시도해서 시간이 오래걸린다.

정답 코드는 set과 배열 두개를 사용해서 따로 관리하는 방법을 썼음

23326: 홍익 투어리스트

#include <bits/stdc++.h>
using namespace std;

int n, q;
set<int> p;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
	{
		int a;
		cin >> a;
		if (a) p.insert(i);
	}

	int cur = 1;
	while (q--)
	{
		int a;
		cin >> a;
		if (a == 1)
		{
			cin >> a;
			if (p.find(a) != p.end()) p.erase(a);
			else p.insert(a);
		}
		else if (a == 2)
		{
			cin >> a;
			cur = (cur + a - 1) % n + 1;
		}
		else
		{
			if (p.empty()) cout << -1 << '\n';
			else
			{
				auto it = p.lower_bound(cur);
				if (*it >= cur) cout << *it - cur << '\n';
				else cout << n - cur + *p.begin() << '\n';
			}
		}
	}
}

입출력 버퍼 부분 쥐도새도 모르게 지워져서 계속 시간초과 뜨길래 뇌정지옴

해답코드랑 비교해보니 쿼리가 2일때 cur값 주는 부분만 조건식을 썼냐 안썼냐 차이였음

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x18] 그래프 (0)	2022.08.07
[0x17] 우선순위 큐 (0)	2022.08.07
[0x15] 해시 (0)	2022.08.06
[0x14] 투 포인터 (0)	2022.08.05
[0x13] 이분탐색 (0)	2022.08.05

[0x15] 해시

2022. 8. 6. 02:00

키에 대응되는 값을 저장하는 자료구조이다.

insert, erase, find, update 모두 O(1)에 할 수 있다.

해시 자료구조에서는 해시 함수라는게 쓰인다.

*해시 함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

unordered_multimap은 자주 쓰이지 않는다.

*충돌 : 서로 다른 키가 같은 해시 값을 가지게 될 경우 발생한다.

충돌이 발생하는 것 자체는 달리 막을 방법이 없다. 하지만 충돌이 발생했을 때 회피하는 방법이 존재한다.

크게 Chaining과 Open Addressing으로 나뉜다.

Chaining

각 인덱스마다 연결 리스트를 둬서 충돌 회피를 하는 방법. STL의 해시 자료구조는 Chaining을 이용한다.

이상적인 상황에서는 O(1)이지만 충돌이 빈번하게 일어날수록 성능이 저하되고 최악의 상황에는 O(N)이다.

Open Addressing

해시 충돌 발생시 다음 인덱스들 중에 비어있는 인덱스를 이용한다.

find는 해당 값의 인덱스부터 비어있는 칸을 만날때까지 탐색을 한다.

erase의 경우 그냥 값을 지워버리면 find시 문제가 발생하기 때문에 삭제시 더미데이터로 교체한다.

insert는 빈칸 혹은 더미데이터가 있는 칸에 삽입할 수 있다.

*Linear Probing

장점 : Cache hit rate가 높다

단점 : Clustering이 생겨서 성능에 안좋은 영향을 준다

*Quadratic Probing

장점 : Cache hit rate가 나쁘지 않다. Clustering을 어느정도 회피할 수 있다.

단점 : 해시 값이 같을 경우 여전히 Clustering이 발생한다.

*Double Hashing : 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식

장점 : Clustering을 효과적으로 회피할 수 있다.

단점 : Cache hit rate가 낮다.

구현

Load factor = 원소의 개수 / 테이블의 크기

삽입의 최대 횟수가 곧 해시 테이블에 들어있는 원소의 최대 개수가 된다.

Chaining의 경우 어느정도의 충돌을 감수하고 Load factor를 1 이하가 되게끔 한다.

Open Addressing의 경우 Load factor를 0.75 이하로 둔다. (1.33배 정도)

테이블의 크기를 M이라고 하면 정수에 대한 해시 함수는 M으로 나눈 나머지로 정할 수 있다.

문자열에 대한 해시 함수는 롤링 해시를 사용하면 된다.

const int M = 1000003;
const int a = 1000;
int my_hash(string& s)
{
	int h = 0;
	for (auto x : s)
		h = (h * a + x) % M;
	return h;
}

my_hash("abc") = ('a'×1000²+'b'×1000¹+'c'×1)%M

추후 추가로 작성예정

연습 문제

7785: 회사에 있는 사람

#include <bits/stdc++.h>

using namespace std;

int n;
unordered_set<string> h;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	while (n--)
	{
		string name, s;
		cin >> name >> s;
		if (s == "enter")
			h.insert(name);
		else
			h.erase(name);
	}

	vector<string> ans(h.begin(), h.end());
	sort(ans.begin(), ans.end(), greater<>());

	for (auto& a : ans)
		cout << a << '\n';

	return 0;
}

해시를 이용해 편하게 푼 코드. sort의 greater<>() 는 내림차순 정렬을 위한 임시 객체이다.

기본적으로 오름차순 정렬인데, 명시적으로 써줄 경우 less<>()로 명시할 수 있다.

1620: 나는야 포켓몬 마스터 이다솜

#include <bits/stdc++.h>

using namespace std;

int n, m;
unordered_map<string, int> h1;
unordered_map<int, string> h2;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; ++i)
	{
		string s;
		cin >> s;
		h1.insert({ s, i });
		h2.insert({ i, s });
	}

	while (m--)
	{
		string s;
		cin >> s;
		if (isdigit(s[0])) cout << h2[stoi(s)] << '\n';
		else cout << h1[s] << '\n';
	}

	return 0;
}

h2를 쓰지 않고 string배열을 하나 더 만들어서 사용해도 된다.

기본 문제

13414: 수강 신청

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> h;

int k, l;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> k >> l;
	for (int i = 0; i < l; ++i)
	{
		string s;
		cin >> s;
		h[s] = i;
	}
	vector<pair<string, int>> v(h.begin(), h.end());
	sort(v.begin(), v.end(), [](auto& a, auto& b) { return a.second < b.second; });

	for (int i = 0; i < k; ++i)
	{
		if (i >= v.size()) break;
		cout << v[i].first << '\n';
	}

	return 0;
}

17219: 비밀번호 찾기

#include <bits/stdc++.h>
using namespace std;

unordered_map<string, string> h;
int n, m;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		string s1, s2;
		cin >> s1 >> s2;
		h.insert({ s1, s2 });
	}
	for (int i = 0; i < m; ++i)
	{
		string s;
		cin >> s;
		cout << h[s] << '\n';
	}

	return 0;
}

9375: 패션왕 신해빈

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		unordered_map<string, int> h;
		int n, answer = 1;
		cin >> n;

		for (int i = 0; i < n; ++i)
		{
			string s1, s2;
			cin >> s1 >> s2;
			h[s2]++;
		}

		for (auto& elem : h)
			answer *= elem.second + 1; // 단독인 경우도 포함돼서 +1
		cout << answer - 1 << '\n'; // 알몸인 경우 제외
	}

	return 0;
}

30분정도 삽질하다가 도저히 답이 안나와서 정답코드 보고 조금 이해함

16165: 걸그룹 마스터 준석이

#include <bits/stdc++.h>
using namespace std;

int n, m;
unordered_map<string, string> h1;
unordered_map<string, vector<string>> h2; // multimap보다 훨씬 간결하게 구현 가능

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> m;
	while (n--)
	{
		string a;
		int b;
		cin >> a >> b;

		while (b--)
		{
			string st;
			cin >> st;
			h1[st] = a;
			h2[a].push_back(st);
		}
		sort(h2[a].begin(), h2[a].end());
	}

	while (m--)
	{
		string a;
		int b;
		cin >> a >> b;
		if (b)
			cout << h1[a] << '\n';
		else
			for (auto& elem : h2[a]) cout << elem << '\n';
	}
	return 0;
}

11478: 서로 다른 부분 문자열의 개수

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	string str;
	set<string> answer;
	cin >> str;

	for (int i = 0; i < str.length(); ++i)
	{
		for (int j = 1; j <= str.length() - i; ++j)
			answer.insert(str.substr(i, j));
	}

	cout << answer.size();

	return 0;
}

19583: 사이버 개강총회

#include <bits/stdc++.h>
using namespace std;

string s, e, q;
unordered_set<string> a;
unordered_set<string> b;
int answer = 0;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	cin >> s >> e >> q;

	while (true)
	{
		string s1, s2;
		cin >> s1 >> s2;
		if (s1 == "" && s2 == "") break;

		if (s1 <= s) a.insert(s2);
		else if (s1 >= e && s1 <= q) b.insert(s2);
	}

	for (auto& i : a)
		if (b.find(i) != b.end()) answer++;
	cout << answer;
	return 0;
}

30분정도 떠올려도 도무지 떠오르지 않아서 구글링으로 해답을 찾아봤음. 사고가 유연하지 않다는걸 또 한번 깨달음. 나는 빡대가리다..

범위와 형식이 00:00:00~23:59:59이기 때문에 따로 문자열 parsing을 하지 않고 바로 비교를 해도 문제가 없다.

개강총회 시작전에 포함된 인원과 종료시간 사이에 포함된 인원이 겹치면 출석 인정.

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x17] 우선순위 큐 (0)	2022.08.07
[0x16] 이진 검색 트리 (0)	2022.08.06
[0x14] 투 포인터 (0)	2022.08.05
[0x13] 이분탐색 (0)	2022.08.05
[0x12] 수학 (0)	2022.08.05

[0x14] 투 포인터

2022. 8. 5. 21:45

배열에서 원래 이중 반복문으로 O(N²)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 많다. 반대로 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우도 많다.

구현할 때 가장 많이 실수하는게 인덱스 하나 차이로 어긋나는 것들이다.

연습 문제

2230: 수 고르기

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[100001];
int st, en;
int answer = 1<<30;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	sort(arr, arr + n);

	while (en < n)
	{
		if (arr[en] - arr[st] >= m)
		{
			answer = min(answer, arr[en] - arr[st]);
			st++;
		}
		else
			en++;
	}

	cout << answer;

	return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[100001];
int answer = 1<<30;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	sort(arr, arr + n);

	int en = 0;
	for (int st = 0; st < n; ++st)
	{
		while (en < n && arr[en] - arr[st] < m) en++;
		if (en == n) break;
		answer = min(answer, arr[en] - arr[st]);
	}

	cout << answer;

	return 0;
}

바킹독님의 풀이

1806: 부분합

#include <iostream>

using namespace std;

int n, s, tot;
int arr[100001];
int answer = 100001;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> s;
	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	tot = arr[0];
	int en = 0;
	for (int st = 0; st < n; ++st)
	{
		while (en < n && tot < s)
		{
			en++;
			if (en != n) tot += arr[en];
		}
		if (en == n) break;
		answer = min(answer, en - st + 1);
		tot -= arr[st];
	}

	// 아무것도 찾지 못해 답이 0인 경우가 있음
	if (answer == 100001) answer = 0;

	cout << answer;

	return 0;
}

위의 문제와 다르게 해가 없을수도 있어서 예외처리가 마지막에 필요하다.

기본 문제

1644: 소수의 연속합

#include <iostream>
#include <vector>

using namespace std;

int n, tot, answer;
vector<int> prime;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	if (n == 1)
	{
		cout << 0;
		return 0;
	}

	vector<bool> b(n + 1, true);
	for (int i = 2; i * i <= n; ++i)
	{
		if (!b[i]) continue;
		for (int j = i * i; j <= n; j += i)
			b[j] = false;
	}

	for (int i = 2; i <= n; ++i)
		if (b[i]) prime.push_back(i);

	auto si = prime.begin();
	auto ei = prime.begin();
	tot = prime.front();

	while (ei != prime.end())
	{
		if (*si == n && *ei == n)
		{
			answer++;
			break;
		}
		if (tot == n)
		{
			answer++;
			tot -= *si;
			si++;
		}
		else if (tot < n)
		{
			ei++;
			if (ei != prime.end())
				tot += *ei;
		}
		else
		{
			tot -= *si;
			si++;
		}
	}

	cout << answer;

	return 0;
}

2003: 수들의 합 2

#include <iostream>

using namespace std;

int n, m, tot, answer;
int arr[10001];
int st, en;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
		cin >> arr[i];

	tot = arr[0];

	while (en < n)
	{
		if (tot == m)
		{
			answer++;
			tot -= arr[st];
			st++;
		}
		else if (tot > m)
		{
			tot -= arr[st];
			st++;
		}
		else
		{
			en++;
			if (en < n) tot += arr[en];
		}
	}

	cout << answer;

	return 0;
}

tot으로 매번 합해서 값을 가지고 있어도 되고 prefix sum을 이용해도 된다.

저작자표시

'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글

[0x16] 이진 검색 트리 (0)	2022.08.06
[0x15] 해시 (0)	2022.08.06
[0x13] 이분탐색 (0)	2022.08.05
[0x12] 수학 (0)	2022.08.05
[0x11] 그리디 (0)	2022.08.04

PREV 이전 1 2 3 4 5 6 NEXT 다음

+ Recent posts

Powered by Tistory, Designed by wallel

티스토리툴바