프로그래밍

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

[난이도] level2
[유형] 구현

[풀이]
전체 합의 절반 값이 t일 때, queue1의 값을 t로 만들면 됩니다.
실제로 큐 두개를 선언하여 queue1,queue2에 넣고 현재 queue1 값들의 합을 sum이라고 했을 때,
sum의 값이 t보다 크면 queue1 에서 pop, t보다 작으면 queue2에서 pop 하는 방식으로 sum이 t가 될때까지 진행해줍니다.
최대 연산 횟수는 queue1,queue2의 초기 사이즈를 N이라고 했을 때,
queue1의 값을 모두 queue2로 옮겼다가 queue2에 있는 값을 다시 queue1으로 옮기는 경우 이므로 N+2*N = 3*N 이 됩니다.
연산 과정에서 무한히 반복될 수 있으므로 최대 3*N만큼만 루프를 돌려줍니다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
ll sum,sum2;
queue<int> q1,q2;
int N;
int solution(vector<int> a, vector<int> b) {
    for(int i=0;i<a.size();i++){
        sum+=a[i];
        sum2+=b[i];
        q1.push(a[i]);
        q2.push(b[i]);
    }

    if((sum+sum2)%2)return -1;
    ll t = (sum+sum2)/2;

    int i=0,j=0,ans=0,n=a.size()*3;
    while(n--){
        if(sum>t){
            ans++;
            int v = q1.front();
            sum-=v;
            q2.push(v);
            q1.pop();
        }else if(sum<t){
            ans++; 
            int v = q2.front();
            sum+=v;
            q1.push(v);
            q2.pop();            
        }else{
            return ans;
        }
    }
    return -1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/두_큐_합_같게_만들기.cpp

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

[난이도] level3
[유형] Min Max 게임

[풀이]
공식 풀이 :https://programmers.co.kr/learn/courses/30/lessons/92345

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int dy[4]={-1,1,0,0},N,M;
int dx[4]={0,0,1,-1};
pair<int,int> sol(int y,int x,int ty,int tx,vector<vector<int>> board){
    if(!board[y][x]) return {0,0};
    int minv=1e9,maxv=-1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=M||!board[ny][nx]) continue;
        auto b = board;
        b[y][x]=0; 
        auto [w,c] = sol(ty,tx,ny,nx,b);
        if(w) maxv = max(maxv,c);
        else minv = min(minv,c);
    }
    if(minv!=1e9) return {1,minv+1};
    if(maxv!=-1) return {0,maxv+1};
    return {0,0};
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
    N=board.size();
    M=board[0].size();
    return sol(aloc[0],aloc[1],bloc[0],bloc[1],board).second;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/사라지는_발판.cpp

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

[난이도] level3
[유형] 누적합

[풀이]
공식풀이 : https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

#include <string>
#include <vector>
using namespace std;
int sum[1002][1002],N,M;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    N=board.size();
    M=board[0].size();
    for(auto s : skill){
        int d=s[5];
        if(s[0]==1) d*=-1;
        sum[s[1]][s[2]]+=d;
        sum[s[3]+1][s[2]]+=-d;
        sum[s[1]][s[4]+1]+=-d;
        sum[s[3]+1][s[4]+1]+=d;
    }
    for(int i=0;i<N;i++)
        for(int j=1;j<M;j++) sum[i][j]+=sum[i][j-1];

    for(int i=0;i<M;i++)
        for(int j=1;j<N;j++) sum[j][i]+=sum[j-1][i];

    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(board[i][j]+sum[i][j]>0) answer++;

    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/파괴되지_않은_건물.cpp

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

[난이도] level3
[유형] 완전탐색

[풀이]
총 노드의 개수가 최대 17개밖에 되지 않기 때문에 방문할 수 있는 모든 경우의 수를 다해봐도 문제 해결이 가능합니다.

void sol(int n,set<int> s,int a,int b) 이라는 재귀함수를 만들어서 아래와 같이 정의하였습니다.
n : 현재 방문한 노드,
s : 다음에 방문할 수 있는 노드,
a : 현재 같이있는 양의 수,
b : 현재 같이있는 늑대의 수

현재 방문한 노드의 자식 노드들을 s에 추가해준 줍니다.
그러면 이제 s에 들어있는 노드들은 다음에 방문할 수 있는 모든 노드가 들어있게 됩니다.
s에 들어있는 노드들을 순차적으로 방문하는 재귀함수를 호출해주면서 a , b 값을 누적해가면
최댓값을 구할 수 있습니다.

#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,ans;
vector<int> adj[17],info;
void sol(int n,set<int> s,int a,int b){
    if(info[n]) b++;
    else a++;
    if(b>=a) return;
    s.erase(n);
    ans=max(a,ans);
    for(auto nxt : adj[n]) s.insert(nxt); 
    for(auto v : s) sol(v,s,a,b);
}
int solution(vector<int> _info, vector<vector<int>> edges) {
    N=info.size();
    info=_info;
    for(auto eg : edges) adj[eg[0]].push_back(eg[1]);
    sol(0,{0},0,0);
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/양과_늑대.cpp

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

[난이도] level2
[유형] 구현

[풀이]
주어진 조건에 맞게 잘 구현하는 문제입니다.
특별한 알고리즘은 없습니다..

#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
int t[10000];
vector<int> fees;
map<int,int> pay;
vector<string> split(string s){
    vector<string> ret;
    int idx;
    s+=' ';
    while((idx = s.find(' '))!=string::npos){
        ret.push_back(s.substr(0,idx));
        printf("%s ",s.substr(0,idx).c_str());
        s = s.substr(idx+1);
    }
    return ret;
}
vector<int> solution(vector<int> _fees, vector<string> records) {
    vector<int> answer;
    fees=_fees;
    memset(t,-1,sizeof(t));
    for(auto r : records){
        auto ret = split(r);
        int h,m,num=stoi(ret[1]);
        sscanf(ret[0].c_str(),"%d:%d",&h,&m);
        m+=h*60;
        if(t[num]==-1) {
            t[num]=m;
        }else{
            pay[num]+=m-t[num];
            t[num]=-1;
        }
    }
    for(int i=0;i<10000;i++){
        if(t[i]!=-1) pay[i]+=23*60+59-t[i];
    }
    for(auto [k,v] : pay){
        int total = fees[1];
        if(v>fees[0]) total+=ceil((double)(v-fees[0])/fees[2])*fees[3];
        answer.push_back(total);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/주차_요금_계산.cpp

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

[난이도] level2
[유형] 구현

[풀이]
n을 k진법으로 변환 시켜준 뒤, 0을 기준으로 나눠지는 모든 수에 대해 소수인지 판별해서
소수인 것의 개수를 구해주면 됩니다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
bool isPrime(ll v){
    if(v==1) return false;
    for(ll i=2;i<=sqrt(v);i++){
        if(v%i==0) return false;
    }
    return true;
}
int solution(int n, int k) {
    int answer = 0;
    string s;
    while(n/k>0){
        int m = n%k;
        s+=m+'0';
        n/=k;
    }
    s+=n+'0';
    reverse(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        if(s[i]=='0') continue;
        string t;
        int j=i;
        for(;j<s.size()&&s[j]!='0';j++) t+=s[j];
        i=j;
        answer+=isPrime(stol(t));
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/k진수에서_소수_개수_구하기.cpp

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

[난이도] level2
[유형] 백트래킹

[풀이]
라이언이 N개의 화살을 각 과녁에 쏠 수 있는 모든 경우의 수를 백트래킹으로 구해주면 됩니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<int> info,ans;
int ansv=-1,n;
void cmp(vector<int> v){
    int a=0,b=0;
    for(int i=0;i<=10;i++){
        if(info[i]==0&&v[i]==0) continue;
        if(info[i]>=v[i]){
            a+=10-i;
        }else{
            b+=10-i;
        }
    }
    if(b>a){
        if(ansv<b-a){
            ansv=b-a;
            ans=v;
        }else if(ansv==b-a){
            vector<int> rans=ans,rv=v;
            reverse(rans.begin(),rans.end());
            reverse(rv.begin(),rv.end());
            if(rv>=rans){
                ans=v;
            }
        }
    }
}
void sol(int m,int cur,vector<int> v){
    if(m==11){
        if(cur!=0) return;
        cmp(v);
        return;
    }
    for(int i=0;i<=cur;i++){
        v.push_back(i);
        sol(m+1,cur-i,v);
        v.pop_back();
    }
}
vector<int> solution(int _n, vector<int> _info) {
    info=_info;
    n=_n;
    sol(0,n,{});
    if(ansv==-1) ans={-1};
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/양궁대회.cpp

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

[난이도] level2
[유형] 수학

[풀이]
n이 3일 때, 아래와 같이
1(1,1) 2(1,2) 3(1,3)
2(2,1) 2(2,2) 3(2,3)
3(3,1) 3(3,2) 3(3,3)

row,column 중 최댓값이 행렬의 값이 됩니다.
그러므로 left~right 값을 (row,column)의 좌표로 변환해주기만 하면
쉽게 답을 구할 수 있습니다.
left~right의 임의의 값 i에 대해 (row,column) 은 (row/n+1,row%mod+1) 이 됩니다.

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
vector<int> solution(int n, ll left, ll right) {
    vector<int> answer;
    for(ll i=left;i<=right;i++){
        answer.push_back(max(i/n,i%n)+1);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/n^2_배열_자르기.cpp