기록을

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;
}

문제 출처:

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

조합, map을 이용해서 풀이할 수 있다.

코스요리를 이루는 메뉴의 개수가 곧 조합으로 뽑아야 할 개수에 해당하기 때문에, 뽑아주고, 2명이상의 사람에게 가장 많이 뽑힌 메뉴들을 개수별로 벡터에 저장하고, 오름차순으로 사전순 정렬을 해주면 된다.

문제 링크는 아래와 같다.

https://www.welcomekakao.com/learn/courses/30/lessons/42579

두 개의 map을 이용했으며, 하나의 map에는 장르별 전체 재생 횟수를 저장했다.

또 다른 map에는 key에 장르를, value에 pair 벡터를 저장했다. pair에는 노래의 재생 횟수와 인덱스가 들어가도록 했다.

map을 구하고 나면, 정렬을 용이하게 하기 위해서 vector를 이용한다.

문제의 조건에 따라 정렬 조건을 맞춰주고 답을 구해주면 된다.

#include <string>
#include <vector>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;

struct Info {
	string str;
	int cnt;
};

bool cmp(pii a, pii b) {
	if (a.first != b.first) 
		return a.first > b.first; //재생 횟수 따라 정렬
	else
		return a.second < b.second; //재생 횟수가 같으면 노래 번호 오름차순으로 정렬
}

bool cmp2(Info a, Info b) {
	return a.cnt > b.cnt; //총 재생 횟수 정렬
}

map<string, vector<pii> > mp; //장르별 노래 재생 횟수
map<string, int> cntMap; //총 재생 횟수

vector<int> solution(vector<string> genres, vector<int> plays) {
	vector<int> answer;

	int songNum = 0;
	for (int i = 0; i < genres.size(); i++) {
		if (mp.find(genres[i]) == mp.end()) {
			vector<pii> tmp;
			tmp.push_back({ plays[i], i }); //i번째 곡이 저만큼 플레이 됨
			mp.insert({ genres[i], tmp });
			cntMap.insert({ genres[i], plays[i] });
		}
		else {
			mp[genres[i]].push_back({ plays[i], i });
			cntMap[genres[i]] += plays[i]; //토탈 추가
		}
	}


	for (auto itr = mp.begin(); itr != mp.end(); itr++) 
		sort(itr->second.begin(), itr->second.end(), cmp); //노래 재생 횟수 내림차순 정렬
	
	

	vector<Info> sortVec; //정렬하기 위해 옮겨담기. <장르, 총재생수>

	for (auto itr = cntMap.begin(); itr != cntMap.end(); itr++) 
		sortVec.push_back({ itr->first, itr->second }); //정렬하기 편하게 벡터에 복사
	
	sort(sortVec.begin(), sortVec.end(), cmp2); //정렬

	for (int i = 0; i < sortVec.size(); i++) {
		string gen = sortVec[i].str;
		answer.push_back(mp.find(gen)->second[0].second);
		if (mp.find(gen)->second.size() > 1) //하나 이상인 경우에만 2번째까지
			answer.push_back(mp.find(gen)->second[1].second);
	}
	return answer;
}

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

1. 섬마다 인덱스를 부여한다. (각각의 섬들을 구분한다.)

2. 모든 경우에 다리를 놓아본다.

다리를 놓을 수 있는 조건에 맞춰서(길이 2이상)

3. 당연하게도 모든 섬을 최소의 간선으로 연결하는 경우, 간선의 수는 섬의 수 - 1이다.

하지만 다리마다 비용이 다 다르기 때문에, 많은 다리를 적은 비용을 놓고 연결하는 경우가 있을 것이다.

따라서 찾은 다리의 수가 k개라고 하고, 섬의 개수를 N개라고 한다면,

찾은 다리 k개 중에 (N-1개~K개)를 뽑아보고, 섬의 연결상태를 확인해서 모든 섬을 연결할 수 있는 경우에 답을 업데이트 해준다.

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

0~ 최대 높이까지 조합으로 뽑아준다.

뽑은 row들에 대하여 모든 경우로 A와 B로 바꿔주고 검사하는 작업을 해주면 된다.

#include<iostream>
#include<vector>
using namespace std;

int h, w, k, m[14][21], org[14][21], st = 0;

bool used[14], findAns = false;

vector<int> v;

void changeRow(int r, int val) {
    for (int j = 0; j < w; j++)
        m[r][j] = val;
}

void toOrg(int r) {
    for (int j = 0; j < w; j++)
        m[r][j] = org[r][j];
}

void dfs(int cnt) { //순열로
    if (cnt == (int)v.size()) {
        
        //투과율 검사 -> 만족하면 바로종료. 정답은 cnt
        for (int j = 0; j < w; j++) {
            int sameCnt = 0;
            bool contin = false;
            for (int i = 0; i < h-1; i++) {
                if (m[i][j] == m[i + 1][j]) sameCnt++;
                else sameCnt = 0;

                if (sameCnt == k - 1) {
                    contin = true;
                    break;
                }
                
                
            }
            if (!contin) return; //실패지점
            
            else if (contin && j == w - 1) 
                findAns = true; //정답 찾음
        }
        
        return;
    }

        for (int j = 0; j < 2; j++) {
            changeRow(v[cnt], j); //v[cnt]행을 i로 바꾸기
            dfs(cnt + 1);
            if (findAns) return; //정답 나옴
            toOrg(v[cnt]); //v[cnt]행 원상복구
        }
    
}

void pickRow(int cnt, int goal) { //조합
                                  
    if (cnt == goal) {
        
        dfs(0); //무조건 0아니면 1로
        return;
    }

    if (cnt == 0) st = 0;
    for (int i = st; i < h; i++) {
        if (!used[i]) {
            //row[cnt] = i;
            st = i;
            v.push_back(i);
            used[i] = true;
            pickRow(cnt + 1, goal);
            if (findAns) return;
            used[i] = false;
            v.pop_back();
        }
    }
}

void initMap() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            m[i][j] = org[i][j];
    }
}
int main(void) {

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> h >> w >> k;
        //a면 0, b면 1
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) {
                cin >> m[i][j];
                org[i][j] = m[i][j]; //원래 배열
            }

    
        int ans = 0;
        for (int i = 0; i < h; i++) {
            pickRow(0, i);
            //초기화
            if (findAns) {
                ans = i;
                break;
            }
            initMap();
        }

        cout << "#" << t << ' ' << ans << '\n';
         
        for (int i = 0; i < h; i++) 
            used[i] = false;

        v.clear();

        findAns = false;
        st = 0;
        
    }

    return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE

조건에 따라 공의 움직임을 구현해주면 된다.

출발 가능 지점에서 모든 방향으로 공을 출발시켜줬다.

웜홀의 위치는 STL map을 이용해서 기록했다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

문제 조건에 따라서 이미 전원이 들어와있는 코어를 제외한 모든 코어를, 모든 경우로 전원을 연결시켜주면서 만족하는 경우를 찾아주면 된다.

다만, DFS를 진행할 때, 어떠 코어에서, 4방향 어디로도 연결할 수 없어도, 전원에 연결하지 않고 다음 코어에 대한 탐색을 이어갈 수 있도록 처리해야한다.

일반적인 백트래킹이나 DFS에 더해서, 어디에도 연결되지 않는 경우 이어서 탐색하도록 구현해주면 된다.

가령 1 2 3 4 의 코어가 있다고 가정하면, 2번이 어디에도 연결될 수 없더라도, 2번을 제외한 1 3 4가 모두 전원이 들어와서, 답안으로 포함되는 경우가 있을 수 있기 때문에 이 부분도 고려해야 한다.