기록을

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

bool cmp(int a, int b) { //정렬
	//return a > b;
	if (a > b)
		return true;
	else
		return false;
}

void vectorPrac(){ //벡터
	vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(-1);

	sort(v.begin(), v.end(), cmp); //정렬 함수 사용자 정의

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

	v.erase(v.begin() + 1); //특정 인덱스 원소 제거

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}


	vector<string> strv;
	strv.push_back("abc\n");
	cout << strv[0];

	string a = "abcdef";
	string subs = a.substr(1, 3); //1번째부터 시작해서 길이 3만큼
	cout << subs << '\n';
}


void stackPrac(){ //스택
	stack<int> stk;
	stk.push(1);
	stk.pop();
	stk.push(5);
	stk.push(4);
	cout << "스택크기 = " << stk.size() << '\n';
	while(!stk.empty()){
		cout << stk.top() << ' ';
		stk.pop();
	}
	cout << '\n';
}

void queuePrac(){ //큐
	queue<int> q;
	q.push(1);
	q.push(2);
	cout << "큐 크기 = " << q.size() << '\n';
	while(!q.empty()){
		cout << q.front() << ' ';
		q.pop();
	}
	cout << '\n';
}

void mapPrac(){
	map<string, int> mp;
	mp.insert({"abc", 1});
	mp.insert({"def", 2});
	mp.insert({"abc", 3}); //이미 존재하는 key에 대해서 insert 하면 무시된다
	mp["abc"] = 3; //하지만 이렇게 수정하면 반영된다.
	for(auto itr = mp.begin() ; itr != mp.end() ; itr++){
		cout << itr->first << " " << itr->second << '\n';
		cout << itr->first << " " << mp[itr->first] << '\n';
	}
	cout << "맵 크기 = " << mp.size() << '\n';
	
}

void setPrac(){
	vector<int> v = {4,4,4,5,1,1,1,2,3};
	for(int i = 0 ; i < v.size() ; i++){
		cout << v[i] << ' ';
	}
	cout << '\n';
	
	set<int> st;
	for(int i = 0 ; i < v.size() ; i++){
		st.insert(v[i]);
	}
	for(auto itr = st.begin() ; itr != st.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
	
	set<int, greater<int> > bigSt;
	for(int i = 0 ; i < v.size() ; i++){
		bigSt.insert(v[i]);
	}
	for(auto itr = bigSt.begin() ; itr != bigSt.end() ; itr++){
		cout << *itr << ' ';
	}
	cout << '\n';
}
void priority_queuePrac(){
	priority_queue<int, vector<int>, less<int> > pq; //내림차순으로 나오는
	pq.push(9);
	pq.push(1);
	pq.push(4);
	pq.push(5);
	pq.push(2);
	while(!pq.empty()){
		cout << pq.top();
		pq.pop();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vectorPrac();
	stackPrac();
	queuePrac();
	mapPrac();
	setPrac();
	priority_queuePrac();
	
}

https://programmers.co.kr/learn/courses/30/lessons/12953

최소공배수(LCM), 최대공약수(GCD) 활용 문제이다.

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

long long gcd(int a, int b){
    long long c;
    while(b != 0){
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm(int a, int b){
    return (a*b) / gcd(a, b);
}
long long solution(vector<int> arr) {
    
    int answer = 1;
    for(int i = 0 ; i < arr.size() ; i++){
        answer = lcm(arr[i], answer);
    }
    
    return answer;
}

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

전형적인 Union-Find 문제이다. 또는 분리 집합 유형이라고 불린다.

n이 포함된 집합을 나타내는 정수 배열로 r[n]을 사용하자.

먼저 0부터 n까지, r[n]을 자기 자신으로 초기화한다.

그리고 주어지는 명령에 따라서 union과 find를 구현한다.

0, a, b가 주어지면 a가 속한 곳을 b가 속한 곳으로 수정해준다.

가령, a가 속한 집합이 3이고, 3이 속한 집합이 2라면 r[3]이 b가 속한 집합으로 수정되어야 하기 때문에,

r[getParent(a)] = getParent(b) 의 로직을 사용한다.

getParent의 경우, r[n]=n이 나올 때까지, 즉 최상단 부모노드일 때까지 getParent가 실행되어야 한다.

#include<iostream>
using namespace std;

int r[1000001];
int n, m;

int getParent(int num) { //find
	if (r[num] == num)
		return num;
	else{
		return r[num] = getParent(r[num]);
	}
}

void join(int a, int b) { // union
	//a의 부모를 b의 부모로 수정
	r[getParent(a)] = getParent(b);



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i <= n; i++) {
		r[i] = i;
	}

	while (m--) {
		int cmd, a, b;
		cin >> cmd >> a >> b;

		if (cmd == 0) {
			join(a, b);
		}
		else {
			if (getParent(a) == getParent(b))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

	return 0;
}

https://programmers.co.kr/learn/courses/30/lessons/17677

먼저 map을 이용해서 {특정문자열, 존재하는 개수}의 형태로 주어지는 string에 대하여 map을 만들어준다. (코드에서 makeMap 함수)

만들기 전에, 대소문자는 구분하지 않는다는 조건을 처리하기 위해서 주어지는 문자열을 모두 소문자로 변환한다.

대문자로 변환해도 무관하다.

그리고 공집합인 경우를 처리한다.

교집합의 경우, 비어있는 map을 생성하고, 한 문자열에 대한 map의 원소가 다른 문자열의 map 원소에 존재하는지 확인하면서, 존재하는 경우에만 새로운 map에 추가해주면 된다.

이 때, 교집합에서는 특정원소의 존재하는 개수는 min 값을 사용하기 때문에, 더 작은 값을 넣어주면 된다.

합집합의 경우, 특정 문자열의 map에 다른 문자열 map의 원소를 합쳐주면 된다. 따라서 존재하지 않는 경우에는 새롭게 추가해주고, 존재하는 경우에는 더 큰 개수의 값을 넣어주면 된다.

#include<bits/stdc++.h>
using namespace std;
map<string, int> mp1, mp2;

map<string, int> makeMap(string str){
    map<string, int> mp;
    
    for(int i = 0 ; i < str.length()-1 ; i++){
        
        // 알파벳 아닌 문자 거르기
        if(!('a' <= str[i] && str[i] <= 'z'))
            continue;
        else if(!('a' <= str[i+1] && str[i+1] <= 'z'))
            continue;
        
        string key = str.substr(i, 2);
        if(mp.find(key) == mp.end()){
            mp.insert({key, 1}); //map에 없으면 추가
        }
        else{
            mp[key]++; //있으면 개수 증가
        }
    }
    return mp;
}
int solution(string str1, string str2) {
    int answer = 0;
    
    // 전부 소문자로 바꾸기
    transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
    transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
    
    mp1 = makeMap(str1); //집합 생성
    mp2 = makeMap(str2);
    
    if(mp1.size() == 0 && mp2.size() == 0){ // 공집합이라 연산 불가능
        return 65536;
    }

    
    int down = 0, up = 0; //분자, 분모
    map<string, int> res; //합집합
    for(auto itr1 = mp1.begin() ; itr1 != mp1.end() ;itr1++){
        string cur = itr1->first;
        
        if(mp2.find(cur) != mp2.end()){
            //있으면(없으면 처리할 게 없음)
            res.insert({cur, min(itr1->second, mp2[cur])});
        }
        up += res[cur];
    }
    
    //교집합
    for(auto itr2 = mp2.begin() ; itr2 != mp2.end() ; itr2++){
        string cur = itr2->first;
        if(mp1.find(cur) != mp1.end()){
            // 있으면
            mp1[cur] = max(itr2->second, mp1[cur]);
        }
        else{
            //없으면
            mp1.insert({cur, itr2->second});
        }
    }
    
    //분모계산(교집합)
    for(auto itr1 = mp1.begin() ; itr1 != mp1.end() ;itr1++){
        down += itr1->second;
    }
       
    answer = up*65536/down;
    return answer;
}