// 최대공약수
auto gcd(long long A, long long B){
if (B == 0)
return A;
else
return gcd(B, A%B);
}
// 최소공배수
auto lcm (long long A, long long B){
return A*B/gcd(A,B);
}
§my solution
#include <iostream>
#include <algorithm>
using namespace std;
// 최대공약수
auto gcd(long long A, long long B){
if (B == 0)
return A;
else
return gcd(B, A%B);
}
// 최소공배수
auto lcm (long long A, long long B){
return A*B/gcd(A,B);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
long long A, B; cin >> A >> B;
cout << lcm(A,B);
}
백만자리라는 문제를 안읽고 풀어서 틀렸다. lon long을 써줘야 함.
§my solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
auto gcd(long long a, long long b){
if (b == 0)
return a;
else
return gcd(b, a%b);
}
auto lcm(long long a, long long b){
return a*b / gcd(a, b);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int num; cin >> num;
vector<long long> v1;
vector<long long> v2;
for (int i = 0; i < num; i++) {
int a, b; cin >> a >> b;
v1.push_back((a));
v2.push_back((b));
}
for (int i = 0; i < num; i++) {
cout << lcm(v1.at(i), v2.at(i)) << '\n';
}
}
1. 먼저 vector에 include 되어 있는 pair를 선언해 입력을 받으면 다음과 같다.
vector< pair<int, int> > p;
for (int i = 0; i < num; i++) {
int n1, n2; cin >> n1 >> n2;
p.push_back(make_pair(n1, n2));
}
2. 그 후 sort를 해줘야 하는데, 이때 문제는 sort를 해주면 p.first를 기준으로 정렬 된다는 것.
그래서 사용자가 만든 함수로 sort(v.begin(), v.end(), custom_func) 의 custom_func에 넣어서
p.second 기준으로 정렬되도록 해야한다. 이때, custom_func의 결과값은 0, 1이 나와야 하며 보통 bool type이다.
bool compare(pair<int, int> a, pair<int, int> b) {
if (a.second == b.second)
return a.first < b.first; // a.first가 작으면 true. 즉 작은게 앞에 배치가 된다.
return a.second < b.second; // a.second가 더 작으면 true. 즉 작은게 앞에 배치가 된다.
}
sort(p.begin(), p.end(), compare);
\
§my solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
if (a.second == b.second)
return a.first < b.first; // a.first가 작으면 true. 즉 작은게 앞에 배치가 된다.
return a.second < b.second; // a.second가 더 작으면 true. 즉 작은게 앞에 배치가 된다.
}
int main() {
ios_base::sync_with_stdio(0);
int num; cin >> num;
vector< pair<int, int> > p;
for (int i = 0; i < num; i++) {
int n1, n2; cin >> n1 >> n2;
p.push_back(make_pair(n1, n2));
}
sort(p.begin(), p.end(), compare);
for (auto x:p) {
cout << x.first << " " << x.second << '\n';
}
}
size가 capacity를 넘으면 2배정도의 크기를 늘려 이동하는 방식으로 구현되어 있다.
§ reserve(N)
- vector의capacity를 N으로 설정하는 것.
- N이현재 capacity보다 클 때만 작동, 작으면 아무 일도 발생X
- N이 현재 capacity보다 크다면 모든 원소 reference와 iterator가 전부 무효화(invalidate)된다.
§ resize(N) / resize(N, value)
-size > N인 경우,원소의 개수를 줄인다.
-size < N인 경우, 입력된value가 없으면 default값인 0으로 할당한다.있다면 value로 할당.
그 후,size가 N이 되도록 늘린다.
§my solution
총 3가지 방식으로 해결하였다.
1. 배열과 배열의 포인터(주소값)로 sort 후 해결 (메모리 9708KB / 시간 636ms)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M; cin >> N >> M;
int arr[N+M];
for (int i = 0; i < N+M; i++) {
cin >> arr[i];
}
sort(arr, arr+N+M);
for (const auto& x:arr) {
cout << x << " ";
}
}
2. 배열을 벡터로만 바꿈 (메모리 9836KB / 시간 688ms)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M; cin >> N >> M;
vector<int> v(N+M);
for (int i = 0; i < N+M; i++)
cin >> v[i];
sort(v.begin(), v.end());
for (int i = 0; i < N+M; i++) {
cout << v[i] << " ";
}
}
3. 정말 벡터 2개를 생성, 합친 후 정렬! (메모리 17656KB / 시간 644ms)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M; cin >> N >> M;
vector<int> v1(N);
vector<int> v2(M);
for (int i = 0; i < v1.size(); i++){
cin >> v1[i];
}
for (int i = 0; i < v2.size(); i++){
cin >> v2[i];
}
vector<int> v3;
v3.reserve(v1.size() + v2.size());
v3.insert(v3.end(), v1.begin(), v1.end());
v3.insert(v3.end(), v2.begin(), v2.end());
sort(v3.begin(), v3.end());
for (const auto& x:v3) {
cout << x << " ";
}
}
4. 2개의 vector를 merge와 sort를 이용해 정렬(메모리 24684KB / 시간 544ms)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vector<int> v1;
vector<int> v2;
int N, M; cin >> N >> M;
for (int i = 0; i < N; i++) {
int num; cin >> num;
v1.push_back(num);
}
for (int i = 0; i < M; i++) {
int num; cin >> num;
v2.push_back(num);
}
vector<int> v3;
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));
sort(v3.begin(), v3.end());
for (const auto& x:v3) {
cout << x << " ";
}
}
