코딩생존기

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

현재 남은 병사에서 만약 막을 수 있다면 막으면서 해당 값을 최대값으로 저장한다. 

그후 만약 저장된 값을 검사해서 

1.만약 기존 값이 크다면 전의 걸 무적권을 쓰고 해당 수만큼 병사를 돌려받는다.

2.만약 기존 값이 현재의 수보다 작을 때 막을 수 있으면 막고

3.아닐 때 저장된 큰 값이 없는 경우는 무적권을 쓰거나 게임오버

#include <string>
#include <vector>
#include <queue>

using namespace std;
//큰값 저장 및 검사
int solution(int n, int k, vector<int> enemy) {
    priority_queue<int> pq;
    int answer = 0;
    for(int i=0;i<enemy.size();i++){
        if(n>=enemy[i]){        //만약 현재가진 병사로 막을 수 있다면
            n-=enemy[i];
            pq.push(enemy[i]);      //최대적 수 저장
        }else{
            if(k>0){            //무적권이 남아있다면
               if(!pq.empty()&&pq.top()>enemy[i]){  //만약 전에 최대였던 수가 현재적보다 크다면
                   n+=pq.top();                              //무적권을 사용해서 돌려받기
                   pq.pop();
                   pq.push(enemy[i]);
                   n-=enemy[i];                 //전에 무적권을 쓰고 지금꺼는 병사로 막기
                }
                k--;
            }else
                return i;
        }
    }
    
    return enemy.size();
}

하노이의 탑은 유명한 재귀 문제이다.

매번 볼때마다 어렵긴하지만 그냥 외우는게 답일 것 같다.

한개만 남아있을 때는 옮겨야하는기둥에 바로 옮기면 되고 

n-1가 남아있을 때는 sub기둥에 n-1를 옮겨두면 된다.

그리고 sub기둥에 있는 것도 end로 하나씩 옮기면 된다.

핵심 코드 

  if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }

전체코드

#include <string>
#include <vector>

using namespace std;
void hanoi(int n,int start,int end,int sub,vector<vector<int>> &answer){
    
    vector<int> v;
    if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }
    
    return;
}


vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    hanoi(n,1,3,2,answer);
    
    return answer;
}