프로그래밍

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://www.acmicpc.net/problem/12919

[난이도] Gold5
[유형] 브루트포스

[풀이]
S에서 T를 만드려고 하면 모든 문자에서 두가지 연산을 다 해봐야 하기 때문에 시간초과가 발생합니다.
역으로 T에서 S로 원복시키는 방식으로 하면 각 연산을 적용할 수 없는 경우가 생기기 때문에
많은 케이스가 가지치기 됩니다.
그러므로 재귀함수로 T에서 S를 만들 때 가능한 모든 경우의 수를 구해서 체크해주면 됩니다.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string S,T;
bool ok;
void sol(string s){
    if(s==S){
        ok=1;
        return;
    }
    if(s.size()<=S.size()) return;
    if(s.front()=='B'){
        string tmp = s;
        reverse(tmp.begin(),tmp.end());
        tmp.pop_back();
        sol(tmp);
    }
    if(s.back()=='A'){
        s.pop_back();
        sol(s);
    }
}
int main(){
    cin >> S >> T;
    sol(T);
    cout << ok;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/12919.cpp

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

[난이도] Gold5
[유형] DFS

[풀이]
무거운 구슬을 u, 가벼운 구슬을 v로 입력 받았을 때,
인접행렬을 이용해 adj[u][v]=1, adj[v][u]=2 와 같이 u->v 방향 edge는 1, v->u 방향 edge는 2로
표시해줍니다.

그 뒤 각 구슬에서 dfs를 1,2방향에 대해 돌려주면서 몇 개의 구슬을 방문할 수 있는지 체크해줍니다.
1 방향 edge 탐색으로 자신보다 가벼운 구슬의 개수를 찾을 수 있고,
2 방향 edge 탐색으로 자신보다 무거운 구슬의 개수를 찾을 수 있습니다.

이 두 값 중 N/2를 넘는 값이 있으면 정답에 추가해줍니다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,visit[100],adj[100][100],ans;
int dfs(int cur,int k){
    visit[cur]=1;
    int ret=1;
    for(int i=1;i<=N;i++){
        if(!visit[i]&&adj[cur][i]==k) ret+=dfs(i,k);
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=1;
        adj[v][u]=2;
    }
    for(int i=1;i<=N;i++){
        int v = dfs(i,1);
        memset(visit,0,sizeof(visit));
        if(v-1>N/2) {
            ans++;
        } else {
            v = dfs(i,2);
            if(v-1>N/2) ans++;
        }
        memset(visit,0,sizeof(visit));
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2617.cpp

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

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

[풀이]
보드가 3x3 밖에 되지 않으므로 백트래킹을 이용해
나올 수 있는 모든 경우의 수를 해보면서 게임이 끝나는 보드의 모양이 나올 때, 정답 set에 넣어주면 됩니다.

#include <iostream>
#include <string>
#include <cstring>
#include <set>
using namespace std;
int a[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
int board[3][3];
string s;
set<string> ans;
bool check(string t,int i){
    if(t[a[i][0]]=='.') return 0;
    for(int j=1;j<3;j++){
        if(t[a[i][0]]!=t[a[i][j]]) return 0;
    }
    return 1;
}
void sol(int n){
    string tmp;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[i][j]==1) tmp+='X';
            else if(board[i][j]==2) tmp+='O';
            else tmp+='.';
        }
    }
    for(int i=0;i<8;i++){
        if(check(tmp,i)){
            ans.insert(tmp);
            return;
        }
    }
    if(n==9) {
        ans.insert(tmp);
        return;
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(board[i][j]!=0) continue;
            board[i][j] = n%2+1;
            sol(n+1);
            board[i][j]=0;
        }
    }
}
int main(){
    sol(0);
    while(1){
        cin >> s;
        if(s=="end") return 0;
        if(ans.find(s) !=ans.end()) puts("valid");
        else puts("invalid");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/7682.cpp