// 최대공약수
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: 사람의 경험에 의해 어느 바다에서 어떤 물고기가 더 잘 잡히는지에 대한 연평균 데이터 - 옵션2: 자동적인 system [전처리-특징추출-classification]
class
X1 (Lightness)
X2 (Width)
Y (target)
Fish 1 Fish 2 . . . Fish n
. .
.
. .
.
Sea Bass Salmon
Salmon
위의 class에 대해 우리는 분류를 해야하며 이때, Bayesian Classifier를 사용할 수 있는데, 다른 model들과 Bayesian이 가장 확연히 다른 점이 하나 있다. 아래 수식을 살펴보자. 먼저 Bayesian의 공식은 조건부확률로 이루어져 있다.
Bayes' Formula
여기서 가장 중요한 것은 Prior이다.
다른 머신러닝 모델들과 확연히 다른 Bayesian 만이 갖는 특징으로 사용자 주관이 개입될 수 있다는 점이다.
예를 들어 어떤 바다에서 물고기를 잡았을 때, 70%정도가 salmon이라 판별된다면, 이런 자연적인 분포비율을 model에 집어넣을 수 있다는 뜻이다. 예를 들어, 모델이 fish5에 대해 salmon일 확률을 0.3이라 예측했다면, 70%의 주관의 개입으로 모델의 분류효과를 달리할 수 있다는 점이다.
Likelihood만으로 측정한 결과값이 왼쪽이라면, 이 값에&nbsp; prior를 추가해 오른쪽과 같은 값을 만들 수 있으며 좀 더 세밀한 분류도 가능해진다.
※ Generative vs Discriminative // Parametric vs Non-parametric
§ Generative vs Discriminative
▶ Generative - modeling의 결과로부터 data를 만들 수 있다. - Output: 확률 분포 (Probability distribution)
▶ Discriminative - data를 모아 판별함수를 찾을뿐, 생성하지는 못하는 함수 (Just looking for a discriminant function)
§ Parametric vs Non-parametric
▶ Parametric - 미리 지정된 모델의 파라미터를 최적화함 (optimize pre-defined parameters in a model)
▶ Non-parametric - 모델에 파라미터자체가 없음 (no parameters in a model)
※ Parameter Estimation_ Discriminant Function for Decision Boundary
#include <iostream>
using namespace std;
int main(){
int x, y; cin >> x >> y;
int result = 1;
for (int i = 0; i < y; i++)
result *= x;
cout << result;
}
§ 하지만 <cmath>의 내장함수인 exp2나 pow함수를 이용하면 매우 짧은 코드로 답을 낼 수 있어 유용하다.
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int x, y; cin >> x >> y;
cout << pow(x,y);
}
#include <iostream>
#include <cmath>
using namespace std;
int main(){ // x값 2 한정
int y; cin >> y;
cout << exp2(y);
}
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 << " ";
}
}
