erikanes's Macchiato :: erikanes's Macchiato

전체 글

[0x16] 이진 검색 트리 2022.08.06
[0x15] 해시 2022.08.06
[0x14] 투 포인터 2022.08.05
[0x13] 이분탐색 2022.08.05
[0x12] 수학 2022.08.05

PREV 이전 1 ···58 59 60 61 62 63 64 ···77 NEXT 다음

[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

[0x13] 이분탐색

2022. 8. 5. 01:52

이분탐색

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방식.

이분탐색의 주의 사항

주어진 배열은 반드시 오름차순으로 정렬되어 있어야 한다.
무한 루프에 빠지지 않게 mid 값을 정해야 한다.

정렬된 배열에서 중복된 데이터를 제거할 땐 unique와 erase를 이용한다.

2개의 값들을 묶거나 어느 한쪽의 값을 이분탐색으로 찾아서 시간복잡도를 낮추는 아이디어는 이분탐색 관련 응용문제에서 핵심적으로 많이 나온다.

Parametric Search (매개 변수 탐색)

조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

최적화 문제를 결정 문제로 바꿀 수 있는지 생각하고 그 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인지를 따져봐야 한다.

문제에서 최소/최대 얘기가 있고 범위가 무지막지하게 크거나 시간 복잡도에서 값 하나를 로그로 떨어트리면 될 것 같을때 Parametric Search 풀이를 고민할 수 있다.

연습 문제

1920: 수 찾기

#include <iostream>
#include <algorithm>

int arr[100001];
int n, m;

int bsearch(int &t)
{
	int st = 0;
	int en = n - 1;

	while (st <= en) {
		int mid = (st + en) / 2;

		if (arr[mid] > t) en = mid - 1;
		else if (arr[mid] < t) st = mid + 1;
		else return 1;
	}
	return 0;
}

using namespace std;

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

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);
	cin >> m;
	while (m--)
	{
		int t;
		cin >> t;
		cout << bsearch(t) << '\n';
	}

	return 0;
}

10816: 숫자 카드 2

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

	vector<int> cards;	
	int n, m, data;

	cin >> n;

	while (n--)
	{
		cin >> data;
		cards.push_back(data);
	}

	sort(cards.begin(), cards.end());

	cin >> m;

	while (m--)
	{
		cin >> data;
		cout << upper_bound(cards.begin(), cards.end(), data) - lower_bound(cards.begin(), cards.end(), data) << " ";
	}

	return 0;
}

lower_bound와 upper_bound의 결과를 pair로 반환해주는 equal_range라는 함수가 있다.

이 경우 second - first로 더 간단하게 표현할 수 있다.

18870: 좌표 압축

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1000001];
vector<int> ans;

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

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
		ans.push_back(arr[i]);
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	for (int i = 0; i < n; ++i)
	{
		cout << lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin() << ' ';
	}

	return 0;
}

2295: 세 수의 합

추후 풀어볼 예정

1654: 랜선 자르기

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int k, n;
int arr[1000001];

// 핵심 메소드
bool cut(int v)
{
	ll ans = 0;
	for (int i = 0; i < k; ++i)
		ans += arr[i] / v;
	return ans >= n;
}

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

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

	sort(arr, arr + k);

	ll st = 0;
	ll en = (1<<31)-1;
	while (st < en)
	{
		ll mid = (st + en + 1) / 2;
		if (cut(mid)) st = mid;
		else en = mid - 1;
	}
	cout << st;

	return 0;
}

Parametric Search의 대표 문제.

최적화 문제 : N개를 만들 수 있는 랜선의 최대 길이

->결정 문제 : 랜선의 길이가 X일 떄 랜선이 N개 이상인가 아닌가?

기본 문제

10815: 숫자 카드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int v1[500001];
int v2[500002];

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

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

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

	sort(v1, v1 + n);

	for (int i = 0; i < m; ++i)
		cout << binary_search(v1, v1 + n, v2[i]) << ' ';

	return 0;
}

1822: 차집합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m;
ll arr1[500001];
ll arr2[500001];
vector<ll> answer;

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 >> arr1[i];
	for (int i = 0; i < m; ++i)
		cin >> arr2[i];

	sort(arr1, arr1 + n);
	sort(arr2, arr2 + m);

	for (int i = 0; i < n; ++i)
		if (!binary_search(arr2, arr2 + m, arr1[i])) answer.push_back(arr1[i]);

	cout << answer.size() << '\n';
	for (auto& elem : answer)
		cout << elem << ' ';

	return 0;
}

16401: 과자 나눠주기

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m;
int arr[1000001];

// 이 함수를 잘 기억해야 한다
bool cut(int v)
{
	if (v == 0) return true;
	ll ans = 0;
	for (int i = 0; i < m; ++i)
		ans += arr[i] / v;
	return ans >= n;
}

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

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

	sort(arr, arr + m);

	int st = 0;
	int en = 1000000000;
	while (st < en)
	{
		int mid = (st + en + 1) / 2;
		if (cut(mid)) st = mid;
		else en = mid - 1;
	}
	cout << st;

	return 0;
}

Parametric Search

최적해가 없는 경우에 0을 출력해야 하므로 cut 메소드에서 0일때도 true를 반환하도록 한다.

저작자표시 (새창열림)

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

[0x15] 해시 (0)	2022.08.06
[0x14] 투 포인터 (0)	2022.08.05
[0x12] 수학 (0)	2022.08.05
[0x11] 그리디 (0)	2022.08.04
[0x10] 다이나믹 프로그래밍 (0)	2022.08.03

[0x12] 수학

2022. 8. 5. 01:03

소수

소수 판정법

합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다.

2부터 √N까지의 수로 나누어지지 않으면 소수이다.

sqrt는 실수값으로 반환되므로 오차가 생길수 있어서 사용하지 않는게 좋기때문에 i의 루프 범위를 i*i <= n으로 잡아주면 된다.

범위 내에서의 소수 판정법 - 에라토스테네스의 체

vector<int> sieve(int n) {
	vector<int> primes;
	vector<bool> state(n + 1, true);
	state[1] = false; // 없어도 됨
	for (int i = 2; i <= n; ++i) {
		if (!state[i]) continue;
		for (int j = 2*i; j <= n; j += i)
			state[j] = false;
	}
	for (int i = 2; i <= n; ++i)
		if (state[i]) primes.push_back(i);
	return primes;
}

시간복잡도 개선안

vector<int> sieve(int n) {
	vector<int> primes;
	vector<bool> state(n + 1, true);
	state[1] = false; // 없어도 됨
	for (int i = 2; i*i <= n; ++i) {
		if (!state[i]) continue;
		for (int j = i*i; j <= n; j += i)
			state[j] = false;
	}
	for (int i = 2; i <= n; ++i)
		if (state[i]) primes.push_back(i);
	return primes;
}

시간복잡도는 O(NloglogN) 이다.

짤막한 팁) bool type을 vector로 사용하면 1바이트가 아닌 1비트로 저장되어 공간을 줄일 수 있다.

소인수 분해

N을 i로 나눌수 있으면 i로 나누어지지 않을 때 까지 i를 소인수 목록에 추가하고 N을 i로 나눈다(i >= 2)
i로 나누어지지 않으면 i를 증가시킨다.
N이 1이 될 때까지 1~2를 반복한다.

소인수 목록에 들어간 수는 반드시 소수이다.

위와 같은 방식의 시간복잡도는 O(N) 이지만 시간복잡도를 개선한 소수 판별법처럼 O(√N)으로 줄일 수 있다.

i의 루프 범위를 i <= N이 아닌 i*i <= N로 잡고 N이 1이 아닐 경우 그 수를 소인수 목록에 추가해주면 된다.

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

	int n;
	cin >> n;
	
	for (int i = 2; i * i <= n; ++i)
	{
		while (n % i == 0)
		{
			cout << i << '\n';
			n /= i;
		}
	}
	if (n != 1)
		cout << n;

	return 0;
}

최대 공약수와 최소 공배수

약수 : 어떤 수를 나누어 떨어지게 하는 수

vector<int> divisor(int n) {
	vector<int> div;
	for (int i = 1; i * i <= n; ++i) {
		if (n % i == 0) div.push_back(i);
	}
	for (int j = (int)div.size() - 1; j >= 0; --j) {
		if (div[j] * div[j] == n) continue;
		div.push_back(n / div[j]);
	}
	return div;
}

시간복잡도는 O(√N) 이다.

최대 공약수(GCD) : 두 자연수의 공통된 약수 중 가장 큰 약수

유클리드 호제법을 이용하면 매우 빠르고 간단하게 구할 수 있다.

두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 하면 GCD(A,B) = GCD(B,r)이다.

int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b, a%b);
}

최소 공배수(LCM)

A×B = GCD(A,B)×LCM(A,B)

int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

본래의 식은 (a*b) / gcd(a,b) 이지만 a,b의 값이 10^9라면 a*b는 int overflow가 발생하기 때문에 예방차원에서 계산의 순서를 바꾼 것이다.

연립합동방정식

이항계수

nCk = (n-1)C(k-1) + (n-1)Ck

저작자표시 (새창열림)

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

[0x14] 투 포인터 (0)	2022.08.05
[0x13] 이분탐색 (0)	2022.08.05
[0x11] 그리디 (0)	2022.08.04
[0x10] 다이나믹 프로그래밍 (0)	2022.08.03
[0x0F] 정렬 II (0)	2022.08.02

PREV 이전 1 ···58 59 60 61 62 63 64 ···77 NEXT 다음

+ Recent posts

Powered by Tistory, Designed by wallel

티스토리툴바