프로그래밍

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

[난이도] level4
[유형] 비트마스크

[풀이]
트랩에는 연결된 간선이 역방향인 경우와 정방향인 경우 두가지 상태가 있습니다.
간선이 역방향이려면 트랩에 홀수번 방문한 상태여야 하며, 정방향인 경우는 방문을 안했거나
짝수번 방문한 상태입니다.

트랩의 개수가 최대 10개밖에 되지 않으므로 10개의 비트로 아래와 같이 트랩의 상태를 저장할 수 있습니다.
0000000000(0)~1111111111(2^10-1) (0인 경우 정방향, 1인 경우 역방향)

이를 이용해 vector<pair<int,int>> adj[1025][1001] 형태의 adj[state][node] 2차원 인접리스트를 선언한 뒤
state에 따라 올바른 간선 방향을 가지는 인접 리스트를 각각 만들어줍니다.

트랩의 개수가 k개라면 인접 리스트는 총 2^k개가 나올 수 있습니다.
만약 어떤 노드 u,v를 연결하는 간선이 입력으로 주어질 때,
i)   u,v가 모두 정방향인 경우(둘다 트랩이 아니거나, 트랩이어도 state 비트마스크에서 두 트랩 모두 0)
      u,v는 u->v 방향 그대로 저장

ii)  u,v 둘중 하나가 트랩이면서 역방향인 경우
      간선을 뒤집어야 하므로 v->u 방향으로 저장

iii) u,v 모두 트랩이면서 역방향인 경우
      이 경우에는 간선이 u에 의해 한번 뒤집히고, v에 의해 또한번 뒤집히므로 결국 정방향인 상태가 됩니다.
      그대로 u->v 방향으로 저장

위와 같이 state에 따라서 간선이 역방향, 정방향인지 정할 수 있고
각 state마다 인접 리스트(그래프)가 생성되게 됩니다.

이를 이용해 int dist[1025][1001] 배열을 선언하여
dist[state][node] : 현재 트랩의 상태가 state 일때, node까지의 최단 거리를 업데이트 해주는 BFS를
이용하여 end node까지의 거리를 구할 수 있습니다.
시간 제한이 10초로 넉넉하여 다익스트라를 사용하지 않고 일반 BFS를 사용하여도 AC를 받았습니다.

현재 노드가 cur 일때, 연결된 다음 노드 nxt가 트랩이라면 nxt에 연결된 간선이 뒤집어져야 하므로
state 비트를 변경해주어야 합니다. 간단히 bit xor 연산으로 다음 state를 구할 수 있습니다.
현재 state가 bit이고 nxt가 i번째 trap 이라면 next_bit = bit ^ (1<<i) 이 됩니다. i번째 bit만 뒤집어주면 되기 때문입니다.

다익스트라로 구현하면 end 노드에 처음 도착한 순간이 최단거리 이지만
BFS로 구현하였기 때문에 항상 최적의 경로로 방문하는 것이 아니어서
더이상 방문할 노드가 없을 때까지 계속 방문하며 최솟값을 업데이트 해주어야 합니다.

#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int dist[1025][1001];
bool trap[1001];
map<int,int> trapidx;
vector<pair<int,int>> adj[1025][1001];
bool isFlip(int a,vector<int>& flag){
    return trap[a] && flag[trapidx[a]];
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    for(int i=0;i<traps.size();i++) {
        trap[traps[i]]=1;
        trapidx[traps[i]]=i;
    }
    for(int i=0;i<(1<<traps.size());i++){
        vector<int> flag(traps.size(),0);
        for(int j=1;j<=n;j++) dist[i][j]=9e8;
        for(int j=0;j<traps.size();j++) {
            if(i&(1<<j)) flag[j]=1;
        }
        for(auto& r : roads){
            int u=r[0],v=r[1],c=r[2];
            int cnt = isFlip(u,flag)+isFlip(v,flag);
            if(cnt==1) adj[i][v].push_back({u,c});
            else adj[i][u].push_back({v,c});
        }
    }
    queue<pair<int,int>> q;
    dist[0][start]=0;
    q.push({0,start});

    int ans=9e8;
    while(!q.empty()){
        auto [bit,cur] = q.front(); q.pop();
        if(cur==end) ans=min(ans,dist[bit][cur]);
        for(auto [nxt,d] : adj[bit][cur]){
            int nb = bit;
            if(trap[nxt]) {
                int i = trapidx[nxt];
                nb ^= (1<<i);
            }
            if(dist[nb][nxt] > dist[bit][cur]+d){
                dist[nb][nxt]=dist[bit][cur]+d;
                q.push({nb,nxt});
            }
        }
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/미로_탈출.cpp

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

[난이도] level1
[유형] 정렬

[풀이]
정렬시 필요한 변수들을 저장하는 구조체를 선언한 뒤 그곳에 필요한 값들을 저장하고
comparator를 정의하여 정렬해주면 됩니다.

코틀린으로 구현시 sortedBy 함수를 이용하면 comparator를 따로 정의하지 않고도 쉽게 정렬이 가능합니다.

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
struct P{
    int w,wl,b,c,idx;
};
P arr[1001];
bool cmp(const P& l,const P& r){
    if(l.w*r.wl > r.w*l.wl) return 1;
    else if(l.w*r.wl == r.w*l.wl) {
        if(l.b > r.b) return 1;
        else if(l.b==r.b) {
            if(l.c>r.c) return 1;
            else if(l.c==r.c){
                return l.idx < r.idx;
            }
        }
    }
    return 0;
}
vector<int> solution(vector<int> weights, vector<string> head2head) {
    vector<int> answer;
    N=weights.size();
    for(int i=0;i<N;i++){
        int w=0,l=0,ww=0;
        for(int j=0;j<N;j++){
            if(head2head[i][j]=='W') {
                w++;
                if(weights[j]>weights[i]) ww++;
            }
            else if(head2head[i][j]=='L') l++;
        }
        arr[i]={w,w+l,ww,weights[i],i};
    }
    sort(arr,arr+N,cmp);
    for(int i=0;i<N;i++) answer.push_back(arr[i].idx+1);
    return answer;
}

Kotlin

data class P(val w:Double,val ww:Int,val weight:Int,val idx:Int)
class Solution {
    fun solution(weights: IntArray, head2head: Array<String>): IntArray {
        val N=weights.size
        var arr = Array<P>(N){P(0.0,0,0,0)}
        for(i in 0..N-1){
            var w=0;
            var l=0;
            var ww=0
            for(j in 0..N-1) {
                if(head2head[i][j]=='W'){
                    w++
                    if(weights[j]>weights[i]) ww++
                }
                else if(head2head[i][j]=='L') l++
            }
            var wl = 0.0
            if(w+l!=0) wl = w.toDouble()/(w+l)
            arr[i] = P(wl,ww,weights[i],i)
        }
        return arr.sortedBy { it.idx }.sortedBy { -it.weight }.sortedBy { -it.ww }.sortedBy{-it.w}.map{it.idx+1}// .toIntArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level1/위클리_챌린지.cpp

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

[난이도] level4
[유형] 트리

[풀이]
트리의 지름을 이용하여 해결하는 문제입니다.
트리의 지름이란 트리에서 가장 먼 두 점 a,b의 경로를 의미합니다.
임의의 점 x에서 가장 먼 점 y를 구하고 y에서 가장 먼 점 z를 구하면 y-z의 경로가 트리의 지름이 됩니다.
( https://blog.myungwoo.kr/112 블로그를 참고하시면 자세한 설명이 있습니다.)

문제의 주어진 트리에서 지름이 y-z1, y-z2 이렇게 두가지가 있다면
정답은 트리의 지름의 길이가 됩니다. 왜냐하면 세 점을 y , z1, z2 이렇게 정하면
z1-z2의 거리는 트리의 지름인 y-z1,y-z2보다 길어질 수 없기 때문에 y-z1의 길이가 무조건 중간값이 됩니다.

만약 트리의 지름이 y-z 한개밖에 나오지 않는다면 z에서 다시한번 트리의 지름을 구해봅니다.
만약 이때 위의 경우처럼 두가지가 나온다면 마찬가지로 트리의 지름의 길이가 중간값이 되고,

만약 이때도 한가지만 나온다면 (트리의 지름의 길이 -1)이 정답이 됩니다.
왜냐하면 트리의 지름이 단 한가지 경로만 존재하는 경우이며 이것보다 같거나 긴 경로는 없습니다.
그러므로 트리의 지름 y-z 에서 z와 인접한 점 w를 정해야 하는 나머지 한 점으로 설정하면
y-w-z 형태의 경로가 나오게 되고, y-z,y-w,w-z 중에 y-w가 (y-z의 길이 -1)로, 구해야 하는 중간값이 됩니다.

#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[250001];
priority_queue<int> pq;
int mxD,from;
void dfs(int p,int m,int cnt,bool f){
    if(mxD < cnt){
        mxD=cnt;
        from=m;
    }
    if(f && adj[m].size()==1) pq.push(cnt);
    for(auto nxt : adj[m])
        if(nxt!=p) dfs(m,nxt,cnt+1,f);
}
int solution(int n, vector<vector<int>> edges) {
    for(auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    dfs(0,1,0,0);

    int a = from; mxD=0;
    dfs(0,a,0,1);
    int t=pq.top(); pq.pop();
    if(t==pq.top()) return t;
    while(!pq.empty()) pq.pop();

    a=from; mxD=0;
    dfs(0,a,0,1);
    t=pq.top(); pq.pop();
    return t==pq.top() ? t : t-1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/트리_트리오_중간값.cpp

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

[난이도] level4
[유형] DP

[풀이]
sales 배열의 크기가 최대 300000 이므로 판매원을 참석시킬 수 있는 모든 케이스를
다 해보기에는 시간이 너무 오래걸리기 때문에 다이나믹 프로그래밍을 사용해야 합니다.

우선 주어진 입력을 이용해 2차원 tree vector에 tree[parent].push_back(child) 와 같이
트리 형식으로 저장해줍니다.

Top-Down 방식을 이용하였고 sol(n)은 DP[n]은 구하고 return 합니다.

DP 배열은 아래와 같이 간단히 정의합니다.
DP[n] : 루트가 n인 트리의 최소 비용.

루트가 n일때,  루트인 n 혹은 그 자식 노드중에 하나는 회의에 참석해야 합니다.
위의 케이스를 모두 계산해보고 그 중 최솟값을 DP[n]의 값으로 확정짓는 방식으로 DP[n]을 구합니다.

우선 풀이에 사용될 변수 v를 아래와  같이 정의합니다.
v : n의 자식 노드가 nxt일 때 모든 DP[nxt]의 합
v = sum(DP[nxt])

점화식은 아래와 같습니다.
DP[n] = 

        i) n을 회의에 참석 시킬 때,
            n을 참석 시킬 때 비용 sales[n]에 n의 자식 노드들의 최소비용을 더해주기만 하면 되므로
            v + sales[n] 이 됩니다.

        ii) n의 자식 중 하나인 nxt를 회의에 참석 시킬 때,
            root인 n은 참여하지 않았으므로 sales[n]은 더할 필요 없이
            일단 v 값에 sales[nxt]를 더해줍니다.
            v값은 업데이트 되면 안되므로 임시변수 t를 선언하였습니다.
            t = v+sales[nxt]

            여기서 v에 더해져 있던 sol(nxt) 값은 nxt가 회의에 참석 되는 것이 확정되었으므로
            t에 빼주어야 합니다. 왜냐하면 sol(nxt)에는 nxt가 참여한 경우, 참여하지 않은 경우가 모두
            포함되어 있기 때문입니다.
            t = v+sales[nxt]-sol(nxt)

            여기까지 해주면 nxt의 자식들이 nnxt라고 했을 때, sol(nnxt)의 값도 빠져버려 nxt 자식 트리들의
            비용은 반영이 안되어 버리기 때문에 sol(nnxt)의 값들은 다시 더해줘야 합니다.
            t = v+sales[nxt]-sol(nxt)+sum(sol(nnxt)) (nnxt는 nxt의 자식노드들)
            위의 t 값이 nxt를 회의에 참여 시켰을 때의 최솟값이 됩니다.

        만약 sol(n)에서 n의 자식이 없다면 회의에 참석할 필요가 없기 때문에 0을 return 합니다.

        최종 DP[n]은 i),ii) 케이스 둘에서 나온 값들 중에 최솟값이 됩니다.

#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
vector<int> sales,tree[300001];
int dp[300001],inf=1<<31-1;
int sol(int n){
    if(tree[n].empty()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;

    ret=inf;
    int v=0;
    for(int nxt : tree[n]) v+=sol(nxt);
    ret=min(ret,v+sales[n-1]);
    for(int nxt : tree[n]){
        int t = v-sol(nxt);
        t+=sales[nxt-1];
        for(auto nnxt : tree[nxt]) {
            if(!tree[nnxt].empty()) t+=sol(nnxt);
        }
        ret=min(ret,t);
    }
    return ret;
}
int solution(vector<int> _s, vector<vector<int>> links) {
    sales = _s;
    memset(dp,-1,sizeof(dp));
    for(auto l : links) tree[l[0]].push_back(l[1]);
    return sol(1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/매출_하락_최소화.cpp

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

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍으로 해결할 수 있씁니다.
DP[i][j] : i~j 구간의 행렬을 계산했을 때의 최솟값.
DP[i][j] = min(DP[l][i]+DP[i+1][r]+matrix[l][0]*matrix[i][1]*matrix[r][1]) (l<=i<r)

#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> matrix;
int dp[201][201];
int sol(int l,int r){
    if(l==r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 2e9;
    for(int i=l;i<r;i++) ret=min(ret,sol(l,i)+sol(i+1,r)+matrix[l][0]*matrix[i][1]*matrix[r][1]);
    return ret;
}
int solution(vector<vector<int>> matrix_sizes) {
    matrix=matrix_sizes;
    memset(dp,-1,sizeof(dp));
    return sol(0,matrix.size()-1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/최적의_행렬_곱셈.cpp

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

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

[풀이]
재귀 함수를 이용해 사전순으로 문자열을 만들어보면 됩니다.

#include <string>
#include <vector>
using namespace std;
char mp[5] = {'A','E','I','O','U'};
int ans;
int sol(string str,string& word){
    ans++;
    if(str==word) return ans-1;
    if(str.size()>=5) return 0;
    for(int i=0;i<5;i++) {
        int ret=sol(str+mp[i],word);
        if(ret) return ret;
    }
    return 0;
}
int solution(string word) {
    return sol("",word);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/위클리_챌린지.cpp

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

[난이도] level4
[유형] DP

[풀이]
연산자의 수가 최대 N=100개가 될 수 있으므로 이것을 순열로 만들어 모든 연산 순서에
대해 해보는 풀이로는 해결할 수 없습니다.

다이나믹 프로그래밍을 이용하면 O(N^2)의 복잡도로 해결이 가능합니다.

재귀를 이용한 Top-Down DP를 이용하였으며

sol(int l,int r,int k) 함수는 dp[l][r][k]를 구하며 리턴합니다.

정의는 아래와 같습니다.
dp[l][r][k] : if k==0
                l~r번째 연산자 구간의 연산결과의 최솟값
              if k==1
                l~r번째 연산자 구간의 연산결과의 최댓값

배열의 길이가 2n+1 이라면 연산자는 총 n개 존재하며 각 연산자는 0~n-1 index를 갖는다고 가정합니다.

만약 아래와 같은 배열이 있다면 "-","-","+"연산자는 각각 index 0,1,2 입니다.
["1","-","5","-","3","+","8"]

l~r번째 연산자 구간의 의미는 전체 배열 arr에서는 arr[2*l] , arr[2*l+1] ... arr[2*r+2] 를 모두 사용했을 때,
즉 2*l~2*r+2 구간의 모든 숫자와 연산자를 사용했을 때의 최소 혹은 최댓값을 의미합니다.

예를들어, ["1","-","5","-","3","+","8"] 에서 1~2번째 연산자 구간의 값을 구하는 것은
("5","-","3","+","8")를 모두 사용한 값을 구하는 것이므로 arr[2*1] ~ arr[2*2+2] 를 모두 사용하는 것을 의미합니다.

dp[l][r][k] 를 구하려면

l~r 구간을 어떤 연산자를 기준으로 나눌지를 정해야 합니다.
만약 l이상 r이하의 i로 구간을 나눈다면

k가 0,1인 경우, arr[2*i+1]가 "+","-"인 경우가 나눠지므로 총 4가지 케이스의 식이 나옵니다.

a) k==0
    a-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,0)
        위와 같이 구할 수 있습니다. l~i-1 연산자 구간, i+1~r 연산자 구간의 최댓값 구하면 됩니다.
        만약 l>i-1 인 경우 좌측에 더이상 연산자가 없다는 의미이므로 arr[2*l] 값을 그대로 사용하면 되고,
        i+1>r 인 경우도 역시 우측에 더이상 연산자가 없다는 의미이므로 arr[2*r+2] 값을 그대로 사용하면 됩니다.
        이는 다른 케이스에서도 동일하게 적용됩니다.

        arr[i]=="+" 이므로 더하기 연산을 해야하는데 k==0으로, 최솟값을 구해야 하므로
        l~i-1 구간의 최솟값, i+1~r 구간의 최솟값을 더하는 것이 최솟값을 구할 때 가장 최적이므로
        sol(l,i-1,0) + sol(i+1,r,0) 와 같이 최솟값을 구하기 위해 3번째 인자로 0을 넣어주었습니다.

    a-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,0) + sol(i+1,r,1)

        첫번째 케이스와 마찬가지로 lvalue - rvalue 형태가 나와야 하는데 최솟값이 되려면
        lvalue는 최소, rvalue는 최대가 되는 것이 최적입니다.
        그러므로 위와 같은 식이 나옵니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최솟"값이 sol(l,r,k) 의 최종 결과가 됩니다.

b) k==1
    b-1) arr[i]=="+"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,1)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최대인 것이 최댓값을 만들 때 최적입니다.

    b-2) arr[i]=="-"
        sol(l,r,k) = sol(l,i-1,1) + sol(i+1,r,0)
        lvalue + rvalue형태이므로 lvalue는 최대, rvalue는 최소인 것이 최댓값을 만들 때 최적입니다.

    모든 i에 대해 위와 같이 식을 구해본 뒤 나온 값을 중에 "최댓"값이 sol(l,r,k) 의 최종 결과가 됩니다.

#include <vector>
#include <string>
#include <cstring>
using namespace std;
int dp[101][101][2],inf=9e8;
vector<string> arr;
int sol(int l,int r,int k){
    int& ret = dp[l][r][k];
    if(ret!=-1) return ret;
    if(k){
        ret=-inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,1);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,1);
            else rv = sol(i+1,r,0);

            if(arr[2*i+1]=="+") ret=max(lv+rv,ret);
            else ret=max(lv-rv,ret);
        }
    }else{
        ret=inf;
        for(int i=l;i<=r;i++){
            int lv,rv;
            lv = l>i-1 ? stoi(arr[2*l]) : sol(l,i-1,0);
            if(i+1>r) rv = stoi(arr[2*r+2]);
            else if(arr[2*i+1]=="+") rv = sol(i+1,r,0);
            else rv = sol(i+1,r,1);

            if(arr[2*i+1]=="+") ret=min(lv+rv,ret);
            else ret=min(lv-rv,ret);
        }        
    }
    return ret;
}

int solution(vector<string> _arr)
{
    memset(dp,-1,sizeof(dp));
    arr=_arr;
    return sol(0,arr.size()/2-1,1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/사칙연산.cpp

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

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 문제를 해결할 수 있습니다.

dp 배열을 선언하여 아래와 같이 정의합니다.
dp[i] = 문자열 t의 i번째 문자부터 시작하는 문자열을 만들 때 필요한 단어 조각의 최솟값.

Top-down DP를 이용하였습니다.

dp[n]을 구하고 리턴하는 sol(n)은 아래와 같은 과정을 통해 구해집니다.

for(auto& s : str){
    if(check(n,s)) ret=min(sol(n+s.size()),ret);
}
return ++ret;

str의 모든 단어 조각 s들을 확인하면서 t의 n번 index부터 시작하는 부분 문자열을 대체할 수 있는지를 체크합니다.
대체할 수 있다면 sol(n)=1+sol(n+s.size()) 으로 업데이트 할 수 있습니다. 하지만 이 값이 최솟값인지는 알 수 없기 때문에
모든 s들을 확인하면서 min값으로 업데이트 해줍니다. 위의 코드에서는 +1은 return 시에 해주었습니다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<string> str;
string t;
int dp[20001],inf=9e7;;
bool check(int n,string& s){
    for(int i=0;i<s.size();i++){
        if(n+i>=t.size()) return 0;
        if(t[n+i]!=s[i]) return 0;
    }
    return 1;
}
int sol(int n){
    if(n==t.size()) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret=inf;
    for(auto& s : str){
        if(check(n,s)) ret=min(sol(n+s.size()),ret);
    }
    return ++ret;
}
int solution(vector<string> _strs, string _t){   
    memset(dp,-1,sizeof(dp));
    str=_strs;
    t=_t;
    return sol(0) >= inf ? -1 : sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/단어_퍼즐.cpp