코딩생존기

https://school.programmers.co.kr/learn/courses/30/lessons/42890

조합을 통해 키를 조합한 후 이에 대한 유일성과 최소성을 만족시키는 값을 찾아야한다.

유일성 : 유일한 값 

최소성 : 여러 속성을 조합해 만든 키가 유일성을 가질 때, 한 속성을 제외해도 유일성이 유지되면 최소성을 만족하지 않는다.

어떻게 검사할까 찾아보다가 비트마스크 방법으로 조합과 유일성 최소성 검사를 하는게 직관적이라는 것을 알게 되었다. 

조합

각 열을 하나의 비트로 나타내면, 비트마스크의 각 비트는 열의 포함 여부를 나타낼 수 있다. 

예를 들어, 열이 3개인 경우:

• 000: 아무 열도 포함하지 않음
• 001: 첫 번째 열만 포함
• 010: 두 번째 열만 포함
• 011: 첫 번째와 두 번째 열 포함
• 100: 세 번째 열만 포함
• 101: 첫 번째와 세 번째 열 포함
• 110: 두 번째와 세 번째 열 포함
• 111: 모든 열 포함

이런식으로 표현할 수 있다. 

이 방법을 통해 조합을 생성하려면 2^열의 수로 순회하면 된다. 

조합

 // 모든 가능한 속성 조합을 생성
    for (int comb = 1; comb < (1 << columns); comb++) {
        // 유일성과 최소성 검사
        if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
            // 유일성과 최소성을 만족하는 경우 후보키로 추가
            candidateKeys.push_back(comb);
        }
    }

유일성 검사

유일성 검사또한 비트마스크를 통해 열 포함여부를 검사해준다. 

// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
    set<string> uniqueCheck;
    for (int i = 0; i < relation.size(); i++) {
        string key = "";
        for (int j = 0; j < columns; j++) {
            // comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
            if (comb & (1 << j)) {
                key += relation[i][j] + " ";
            }
        }
        // 유일성 검사: 이미 존재하는 키라면 false 반환
        if (uniqueCheck.find(key) != uniqueCheck.end()) {
            return false;
        }
        uniqueCheck.insert(key);
    }
    return true;
}

이때 직접적인 검사는  if (comb & (1 << j)) 부분에서 이루어진다. 

comb & (1 << j) 이 부분에서 어떻게 계산이 이루어지는지는 예시를 통해 알아보자

• comb의 j번째 비트가 1인지 검사하려면, 1 << j를 사용하여 j번째 비트만 1인 숫자를 만든다.
• comb & (1 << j)를 수행하면, comb의 j번째 비트가 1일 때만 결과가 1이 됩니다. 그렇지 않으면 결과가 0이 된다.
• comb = 5 (0101)
• 열의 개수 columns = 4

• j = 0:
  • 1 << 0는 0001
  • comb & 0001은 0101 & 0001이므로 결과는 0001 (참)
• j= 1:
  • 1 << 1은 0010
  • comb & 0010은 0101 & 0010이므로 결과는 0000 (거짓)

• j = 2:
  • 1 << 2은 0100
  • comb & 0100은 0101 & 0100이므로 결과는 0100 (참)
• j = 3:
  • 1 << 3은 1000
  • comb & 1000은 0101 & 1000이므로 결과는 0000 (거짓)

j = 0과 j = 2에서 조건이 참이므로, 첫 번째와 세 번째 열의 값이 key에 추가

최소성 검사 

기존 후보키로 만들어진 것이 현재 조합의 부분집합에 포함된다면 후보키가 아니다.

// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
    // 기존의 후보키들에 대해 검사
    for (int key : candidateKeys) {
        // 기존의 후보키가 현재 조합에 포함되는지 검사
        if ((comb & key) == key) {
            // 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
            return false;
        }
    }

    // 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
    return true;
}

전체코드 

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
    set<string> uniqueCheck;

    // 각 튜플(행)에 대해 검사
    for (int i = 0; i < relation.size(); i++) {
        string key = "";

        // comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
        for (int j = 0; j < columns; j++) {
            if (comb & (1 << j)) {
                // comb의 j번째 비트가 1이면 해당 열을 key에 추가
                key += relation[i][j] + " ";
            }
        }

        // 유일성 검사: 이미 존재하는 키라면 false 반환
        if (uniqueCheck.find(key) != uniqueCheck.end()) {
            return false;
        }

        // 새로운 키를 set에 추가
        uniqueCheck.insert(key);
    }

    // 모든 튜플에 대해 유일성을 만족하면 true 반환
    return true;
}

// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
    // 기존의 후보키들에 대해 검사
    for (int key : candidateKeys) {
        // 기존의 후보키가 현재 조합에 포함되는지 검사
        if ((comb & key) == key) {
            // 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
            return false;
        }
    }

    // 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
    return true;
}

int solution(vector<vector<string>> relation) {
    int rows = relation.size();     // 튜플(행)의 개수
    int columns = relation[0].size(); // 속성(열)의 개수
    vector<int> candidateKeys;     // 후보키를 저장할 벡터

    // 모든 가능한 속성 조합을 생성
    for (int comb = 1; comb < (1 << columns); comb++) {
        // 유일성과 최소성 검사
        if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
            // 유일성과 최소성을 만족하는 경우 후보키로 추가
            candidateKeys.push_back(comb);
        }
    }

    // 후보키의 개수 반환
    return candidateKeys.size();
}

int main() {
    vector<vector<string>> relation = {
        {"100", "ryan", "music", "2"},
        {"200", "apeach", "math", "2"},
        {"300", "tube", "computer", "3"},
        {"400", "con", "computer", "4"},
        {"500", "muzi", "music", "3"},
        {"600", "apeach", "music", "2"}
    };

    cout << solution(relation) << endl;  // 출력: 2
    return 0;
}

https://school.programmers.co.kr/learn/courses/30/lessons/150368

할인율을 정하고 이에 대한 모든 이모티콘을 dfs로 탐색해서 시뮬레이션을 돌리면 된다. 

중요한 부분은

할인율을 정하고 dfs 돌리는 부분

  for (int i = 0; i < 4; i++) {
        price[cnt].first = (100 - dis[i]) * emoticons[cnt] / 100;  // 할인된 가격
        price[cnt].second = dis[i];  // 할인율
        dfs(cnt + 1, n, users, emoticons);
    }

한 할인율을 이모티콘들에 다 적용했을 때의 이윤계산 

if (cnt == n) {  // 모든 이모티콘에 할인율을 대입했을 때 
        int plus = 0, sum = 0;
        for (int i = 0; i < users.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < n; j++)
                if (users[i][0] <= price[j].second) // 원하는 할인율 이상이면 구매
                    tmp += price[j].first;  
            if (tmp >= users[i][1]) // 구매값이 정해진 가격 이상이면 이모티콘플러스 가입
                plus++;  
            else
                sum += tmp;  // 이윤++
        }
        if (plus > answer[0]) {  // 가입자수가 더 많으면
            answer[0] = plus;
            answer[1] = sum;
        } else if (plus == answer[0] && sum >= answer[1])
            answer[1] = sum;  // 가입자수가 같고 이윤이 크면
        return;
    }

전체코드

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

int dis[4] = {40, 30, 20, 10};  // 할인율
vector<pair<int, int>> price(7, {0, 0});  // 할인된 가격, 할인율
vector<int> answer(2, 0);

void dfs(int cnt, int n, vector<vector<int>> users, vector<int> emoticons) {
    if (cnt == n) {  // 모든 이모티콘에 할인율을 대입했을 때 
        int plus = 0, sum = 0;
        for (int i = 0; i < users.size(); i++) {
            int tmp = 0;
            for (int j = 0; j < n; j++)
                if (users[i][0] <= price[j].second) // 원하는 할인율 이상이면 구매
                    tmp += price[j].first;  
            if (tmp >= users[i][1]) // 구매값이 정해진 가격 이상이면 이모티콘플러스 가입
                plus++;  
            else
                sum += tmp;  // 이윤++
        }
        if (plus > answer[0]) {  // 가입자수가 더 많으면
            answer[0] = plus;
            answer[1] = sum;
        } else if (plus == answer[0] && sum >= answer[1])
            answer[1] = sum;  // 가입자수가 같고 이윤이 크면
        return;
    }
    for (int i = 0; i < 4; i++) {
        price[cnt].first = (100 - dis[i]) * emoticons[cnt] / 100;  // 할인된 가격
        price[cnt].second = dis[i];  // 할인율
        dfs(cnt + 1, n, users, emoticons);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    dfs(0, emoticons.size(), users, emoticons);
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/131130

문제가 정말 길다. 

하지만 우리가 봐야할 것은

입력에서 주어지는 나열된 상자를 보면 된다.

이 상자를 순회하면서 문제에서 주어진 방식대로 상자 안의 숫자로 계속 상자를 방문처리하면서 그룹을 나누고 만약 그룹이 2개보다 작다면 0점이고 아니라면 그룹 수 중에 제일 많은 수와 그 다음으로 많은 수를 곱해서 반환해주면 된다. 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 특정 시작점에서 그룹의 크기를 찾는 함수
int find_group(int start, vector<int>& cards, vector<bool>& visited) {
    int group_size = 0;  // 그룹 크기 초기화
    int current = start;  // 현재 상자를 시작 상자로 설정
    while (!visited[current]) {  // 현재 상자가 방문되지 않은 동안 반복
        visited[current] = true;            //방문처리 
        current = cards[current] - 1;  // 상자 안의 숫자를 통해 다음 상자 선택
        group_size += 1;  // 그룹 크기를 증가시킴
    }
    return group_size;  
}

int solution(vector<int> cards) {
    int n = cards.size();  // 상자의 수
    vector<bool> visited(n, false);  // 방문 여부를 저장
    vector<int> group_sizes;  // 각 그룹의 크기를 저장

    // 모든 상자에 대해 그룹을 찾음
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {  // 현재 상자가 방문되지 않았다면
            int group_size = find_group(i, cards, visited);  // 그룹의 크기를 찾음
            group_sizes.push_back(group_size);  // 그룹 크기를 벡터에 추가
        }
    }

    // 그룹 크기를 내림차순으로 정렬
    sort(group_sizes.rbegin(), group_sizes.rend());

    // 최대 점수를 계산
    if (group_sizes.size() < 2) {  // 그룹이 2개 미만이면
        return 0;  // 점수는 0
    } else {
        return group_sizes[0] * group_sizes[1];  // 가장 큰 두 그룹의 크기를 곱한 값이 최대 점수
    }
}

x값을 따른 원사이에 있는 최소y값과 최대 y을 계산하고 이를 대칭성을 통해 계산하면 되는 문제이다. 

#include <string>
#include <vector>
#include <cmath>
using namespace std;
//한 사분면의 값을 찾아서 4배 시켜주기 
long long solution(int r1, int r2) {
    long long answer = 0;
    
    for(int i=1;i<=r2;i++){
        int maxY = floor(sqrt((long long)r2 * r2 - (long long)i * i));            //최대 Y값 내림해야 경계안쪽의 값까지 구할 수 있다.
        int minY = ceil(sqrt((long long)r1 * r1 - (long long)i * i));             //최소 Y값 올림해야 경계바로 바깥쪽까지의 값을 구할 수 있다.
        
        if(r1<i) minY=0;            //x값이 r1보다 크면 사이이여서 최소y는 0부터 시작
        
        answer+=(maxY-minY+1);      // 
        
    }
    return answer*4;
}

https://school.programmers.co.kr/learn/courses/30/lessons/176962

이 문제에서 중요한 점은

1.시간순으로 과제를 정렬

2.stack 안에 pair 자료형으로 멈춰진 과제를 저장할 변수를 지정

3.과제를 진행하면서 멈춘 과제를 저장하고 할 수 있는 과제를 진행

-> stack과 pair를 적절히 잘 써야한다.

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int Timecalc(string  t) {
    return (60 * stoi(t.substr(0, 2))) + stoi(t.substr(3));
}
//시간순으로 넣고 만약 겹치는거 처리
bool cmp(vector<string> a, vector<string> b) {
    return Timecalc(a[1]) < Timecalc(b[1]);
}
vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<pair<string, int>> pause_plan;

    sort(plans.begin(), plans.end(), cmp);        //시간순으로 정렬

    int curTime = Timecalc(plans[0][1]);
    int nextTime = Timecalc(plans[1][1]);
    int SumSub = 0;           //지금까지 수행한 과제합
    while (SumSub < plans.size() || !pause_plan.empty()) {
        //만약 정지해둔 과제가 있다면
        if (!pause_plan.empty()) {
            //만약 마지막순서의 과제까지 다 했다면 멈춰둔 과제 수행
            if (SumSub == plans.size()) {
                answer.push_back(pause_plan.top().first);
                pause_plan.pop();
                continue;
            }
            //만약 다음에 수행해야할 과제까지 시간이 남아있다면
            if (curTime < nextTime) {
                int pauseTime = pause_plan.top().second;      //과제 수행해야하는 시간
                int availableTime = nextTime - curTime;        //과제 수행가능 시간

                if (pauseTime <= availableTime) {       //만약 남은 시간동안 멈춘과제를 수행가능하다면
                    answer.push_back(pause_plan.top().first);
                    pause_plan.pop();
                    curTime += pauseTime;
                }
                else {
                    pause_plan.top().second = pauseTime - availableTime;
                    curTime = nextTime;
                }
                continue;
            }
        }
        curTime = Timecalc(plans[SumSub][1]) + stoi(plans[SumSub][2]);      //과제수행
        nextTime = SumSub + 1 >= plans.size() ? 1440 : Timecalc(plans[SumSub + 1][1]);

        if (curTime > nextTime) {       //만약 과제수행하는 중에 새로운 과제가 들어온다면
            pause_plan.push({ plans[SumSub][0],curTime - nextTime });       //과제명 : 과제수행완료까지 남은시간
            curTime = nextTime;
        }
        else {
            answer.push_back(plans[SumSub][0]);
        }

        SumSub++;
    }


    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/140107

최대점 0,d d,0 안에서 정의되는 점의 개수를 구하면 되는 문제이다.

생각해보자면 d인 원안에서 정의되는 정수 점의 개수를 구하면 된다. 

이때 x를 k의 배수로 d까지 순회하면서 피타고라스 정리를 통해 y의 최댓값을 구하고 이에 따른 정수 점이 몇개나오는 지 몫 나눗셈을 통해 구하면된다.

이때 y가 0일때도 고려해야해서 마지막에 1을 더해준다. 

#include <string>
#include <vector>
#include <cmath>

using namespace std;
//최대점 0,d d,0 안에서 정의되는 점의 개수 
long long solution(int k, int d) {
    long long answer = 0;
    for(long long x=0;x<=d;x+=k){           //x에 따른 y값 계산
        int maxy=sqrt((long long)d*d-(long long)x*x);       //x값에 따른 y의 최대값 계산-> 피타고라스 정리
        answer+=(maxy/k)+1;         //y의 최대값에 따른 x의 갯수 계산-> 좌표 개수 
        //+1의 이유: y가 0일때도 포함시키려고
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/134239

문제가 길어서 잘 읽어야한다.

과정을 정리하자면

1. 우박수열을 계산

2. 우박수열에 해당하는 값에 따른 각각의 넓이 계산

3. 주어진 범위에 따른 넓이의 합으로 정적분 계산

조건 : 시작값이 끝점보다 커서 유효하지 않은 구간인지 검사 

나는 여기서 우박수열이 수행된 횟수만큼만 넓이를 계산하고 계산을 정적분 범위도 이 값을 통해 계산해주었다.

#include <string>
#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    vector<double> tmp;
    vector<double> sum;
    int n=k;
    int cnt=0;          //우박수열이 수행된 횟수
    tmp.push_back(n);
    //우박수열 계산
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
            cnt++;
        } else {
            n = n * 3 + 1;
            cnt++;
        }
        if(n<1){
            break;
        }else{
           tmp.push_back(n); 
        }  
    }
    //각가의 넓이 계산
    for(int i=0;i<cnt;i++){
        sum.push_back((tmp[i]+tmp[i+1])/2);
    }
    //정적분 계산
    for(int i=0;i<ranges.size();i++){
        double tmpsum=0;
        if(ranges[i][0]<=cnt+ranges[i][1]){
             for(int j=ranges[i][0];j<cnt+ranges[i][1];j++){
            tmpsum+=sum[j];
            }
            answer.push_back(tmpsum);
        }else{
            answer.push_back(-1);
        }  
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/172927

처음에는 다이아 - 철 - 돌 순이여서 그냥 순회하면서 캐면 되는 건줄 알았는데

곡괭이마다 다른 광석에 대한 피로도 계산을 해줘야 하기때문에 DFS로 하는게 맞다고 한다. 

DFS를 통해 좋은 곡괭이로 캘 수 있는 모든 광석을 캐주고 다음 곡괭이로 넘어가면 된다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
map<string, int> m; 
int fatigue[3][3] = {{1,1,1}, {5,1,1}, {25,5,1}}; // [곡괭이로][해당 광물 캘 때] = 드는 피로도
//하나의 곡괭이로 계속해서 캐야함 => DFS
void DFS(vector<int> &picks, vector<string> &minerals, int &answer, int sum, int location) {
    // 광물을 다 캤거나 곡괭이를 다 썼을 때 피로도를 갱신
    if (location == minerals.size() || (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)) {
        answer = min(answer, sum);
        return;
    }
    
    // 0~2 곡괭이 방문
    for (int i = 0; i < 3; i++) {
        // i 곡괭이가 있다면
        if (picks[i] != 0) {
            picks[i]--;
            
            int tmpIdx = location; //캐야 할 광물의 현재위치
            int tmpSum = sum; // 광물을 캐며 누적된 피로도
            for (; tmpIdx < location + 5 && tmpIdx < minerals.size(); tmpIdx++) { // 5개를 캐거나 끝까지 캘 때까지
                tmpSum += fatigue[i][m[minerals[tmpIdx]]]; // 계속 광물을 캐기 피로도 누적
            }
            
            DFS(picks, minerals, answer, tmpSum, tmpIdx);
            
            picks[i]++;
        }
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = (25 * 50) + 1; // 최고 피로도 * 최대 광물 개수
    
    m.insert({"diamond", 0});
    m.insert({"iron", 1});
    m.insert({"stone", 2});
    
    DFS(picks, minerals, answer, 0, 0);
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/62048

기하학과 수학적인 접근이 중요한 문제이다 

입출력 예 그림을 보면 가로는 8개만큼 겹치고 세로는 12개만큼 대각선에서 겹친다 

교차점은 중간에 보면 4개로 최대공약수 만큼 발생한다.

따라서 대각선에서 겹치는 부분에서 중복되는 교차점을 빼주면 되는 것이다.

중요한건 패턴을 찾고 수학적으로 기술하는게 중요할 것 같다.

#include <cmath>
using namespace std;
//대각선은 w개의 가로 격자선과 h개의 세로 격자선을 통과 따라서 W+H개의 경계선을 지나게 된다.
//교차점 최대공약수만큼 발생
//경계선- 중복된 교차점
int getGCD(long long w,long long h){
    int small,big;
    if(w>h){
        big=w;
        small=h;
    }else{
        big=h;
        small=w;
    }
    int mod=big%small;
    while(mod>0){
        big=small;
        small=mod;
        mod=big%small;
    }
    
    return small;
}

long long solution(int w,int h) {
    long long answer;
    long long W=w;
    long long H=h;
    
    int gcd=getGCD(W,H);  
    long long total=W*H;
    answer=total-(W+H-gcd);
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/60057

1개부터해서 단위를 늘려가면서 압축했을 때의 문자열과 비교하면서 가장 짧은 문자열을 찾으면 된다.

중요한 점은 자르는 단위가 문자열의 절반까지가 최대값이고 

순회를 할때 반복되는 부분이 만약 2개 이상이 있다면 숫자를 붙여서 압축해주고 아니라면 그냥 문자열에 붙여서 압축 문자열을 만들어준다. 

 for(int i=1;i<=s.size()/2;i++){                //i는 문자열을 자르는 길이
        int cnt=1;                  //겹치는거 숫자
        string tmp="",a="";        //압축된 숫자, 자른 숫자
        a=s.substr(0,i);
        for(int j=i;j<s.size();j+=i){           //자른만큼 순회
            if(a==s.substr(j,i)) cnt++;             //만약 겹치는게 있다면 
            else{
                if(cnt>1) tmp+=to_string(cnt);
                tmp+=a;
                a=s.substr(j,i);                //다음에 검사할 부분
                cnt=1;                  //압축했으면 다시 겹치는거 찾기위해 1로 초기화
            }
        }

그리고 단위마다 압축문자열만들기 과정 후에 길이를 비교하고 짧은 것은 정답으로 저장해준다.

#include <string>
#include <vector>
//순회하면서 자르는 수를 증가시키면서 문자열 비교
using namespace std;
int solution(string s) {
    int answer = s.size();
    for(int i=1;i<=s.size()/2;i++){                //i는 문자열을 자르는 길이
        int cnt=1;                  //겹치는거 숫자
        string tmp="",a="";        //압축된 숫자, 자른 숫자
        a=s.substr(0,i);
        for(int j=i;j<s.size();j+=i){           //자른만큼 순회
            if(a==s.substr(j,i)) cnt++;             //만약 겹치는게 있다면 
            else{
                if(cnt>1) tmp+=to_string(cnt);
                tmp+=a;
                a=s.substr(j,i);                //다음에 검사할 부분
                cnt=1;                  //압축했으면 다시 겹치는거 찾기위해 1로 초기화
            }
        }
        if(cnt>1) tmp+=to_string(cnt);
        tmp+=a;
        if(answer>tmp.size())answer=tmp.size();   
    }
    return answer;
}