2021 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 모든 문제 코드 및 해설

프로그래머스에 카카오 2021년 공채 코테가 올라오며,

그 당시 제출했던 코드를 공개합니다.

 

당시 1차 합격컷은 3.5문제 이상 선으로 알려져 있습니다.

 

신규 아이디 추천

 

programmers.co.kr/learn/courses/30/lessons/72410

코딩테스트 연습 - 신규 아이디 추천

제한사항을 읽어 봅시다.

new_id는 길이 1 이상 1,000 이하인 문자열입니다.

 

모든 코딩테스트의 문제는 시간 초과가 나지 않는 분기점은 10^8입니다.

10^3은 어떻게 짜도 시간 초과가 나기 어렵습니다.

 

따라서 시간 초과를 고민하기보다는, 단순하고 빠르게 구현하는 것이 이 문제의 주안점입니다.

 

#include <string>
#include <vector>

using namespace std;


string solution(string new_id) {
    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];
        if (e >= 'A' && 'Z' >= e) {
            e = e - 'A' + 'a';
        }
        new_id[i] = e;
    }
    string next;
    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];
        if ( ('a' <= e && e <= 'z') || ('0' <= e && e <= '9') || (e == '-') || (e == '_') || (e == '.')) {
            next += e;
        } else {
            continue;
        }
    }
    new_id = next;
    next = "";

    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];

        if (e == '.' && i != 0 && new_id[i-1] == '.') {
            continue;
        } else {
            next += e;
        }
    }
    new_id = next;
    next = "";



    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];

        if (i == 0 && e == '.') {
            continue;
        } else if (i == new_id.size()-1 && e == '.') {
            continue;
        } else {
            next += e;
        }
    }
    new_id = next;
    next = "";

    if (new_id.size() == 0) {
        new_id = "a";
    }

    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];

        if (i >= 15) {
            break;
        }
        next += e;
    }
    new_id = next;
    next = "";

    for (int i=0; i<new_id.size(); i++) {
        char e = new_id[i];

        if (i == new_id.size() - 1 && e == '.') {
            continue;
        }
        next += e;
    }
    new_id = next;
    next = "";


    while (new_id.size() <= 2) {
        new_id += new_id[new_id.size()-1];
    }


    string answer = "";
    return new_id;
}

 

 

메뉴 리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

 

이 문제의 제한사항을 살펴봅시다.

• orders 배열의 크기는 2 이상 20 이하입니다.

1번 문제보다 입력의 길이가 작습니다.

하지만 조건이 엄청나게 복잡합니다.

 

이런 문제는 역시 시간 복잡도에 구애를 받지 않습니다.

자기의 코드가 얼마나 오래 걸리든 구애받지 않고, 

문제를 어떻게든 조건을 맞게 구현해서 짜기만 하면 됩니다.

 

C++ 을 사용할 경우, set이나 map을 이용하면 귀찮은 구현에서의 시간 낭비를 절약할 수 있습니다.

다른 언어에서도, 해시맵과 집합에 해당하는 자료구조를 활용하시면 됩니다.

 

각각의 주문은 알파벳의 조합으로 이루어져 있습니다. 알파벳은 26개밖에 존재하지 않으므로,

주문을 각각의 알파벳이 포함되는지 안 되었는지를 나타내는 크기 26의 불리언 배열르 나타낼 수 있습니다.

 

예를 들어서, ABC의 경우, 0=A, 1=B, 2=C 가 참이고 다른 모든 알파벳이 거짓인 26개의 배열로 변환시킬 수 있을 것입니다.

 

이제, 주문들 중 임의의 2개를 뽑는 for loop를 작성합니다. 

주문을 26개의 배열로 변환했으므로, 알파벳 26개를 순회하면 두 주문의 공통 음식을 뽑아낼 수 있을 것입니다.

 

이를 벡터로 담은 뒤에, 이 벡터에 DFS 연산을 수행합니다.

그러면 코스요리 후보를 찾아낼 수 있습니다.

찾아낸 코스요리 후보는, 알파벳으로 변환하여 map<string, int> 에 모두 집어넣습니다.

이 경우, 겹치는 코스요리 후보가 각각 몇 번씩 등장했는지 효과적으로 세낼 수 있습니다.

 

마지막으로, map<string, int> 을 순회하여, 최다 등장한 녀석을 뽑아내 출력합니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;


void push(int index, int current_count,int order, string& input, string& current, map<string, int> & to_push) {
//    cout << index << ' ' << current_count << order << input;
    if (order == current_count) {
//        cout << current << '\n';
        string deep = current;
        to_push[deep] += 1;
        return;
    }
    for (int i = index; i<input.size(); i++) {
        current += input[i];

        push(i+1, current_count+1, order, input, current, to_push);

        current.pop_back();
    }

}

vector<string> solution(vector<string> orders, vector<int> course) {
    int order_size = orders.size();
    int course_size = course.size();

    vector<vector<bool>> converted_orders(order_size, vector<bool>(26, false));

    vector<map<string, int>> map_course(course.size());

    for (int i=0; i<order_size; i++) {
        auto original = orders[i];
        vector<bool>& converted = converted_orders[i];

        for (auto c: original) {
            converted[c-'A'] = true;
        }
    }

    for (int i=0; i<order_size; i++) {
        for (int j=i+1; j<order_size; j++) {
            vector<bool>& converted_a = converted_orders[i];
            vector<bool>& converted_b = converted_orders[j];


            string candidate;
            for (int k=0; k<26; k++) {
                if (converted_a[k] && converted_b[k]) {
                    candidate += (k + 'A');
                }
            }
            for (int k=0; k<course_size; k++) {
                string temp;
                if (candidate.size() >= course[k]) {

                    push(0, 0, course[k], candidate, temp, map_course[k]);
                }
            }
//            cout << candidate << '\n';

        }
    }
    vector<string> answer;

    for (int k=0; k<course_size; k++) {
        int max_count = 0;
        for (auto e: map_course[k]) {
            max_count = max(max_count, e.second);
//            cout << e.first << ' ' <<e.second << '\n';
        }
        for (auto e: map_course[k]) {
            if (e.second == max_count) {
                answer.push_back(e.first);
            }
        }

    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

순위 검색

programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

가장 직관적인 풀이는, 각 쿼리를 처리할 때마다 info를 순회하면서 조건을 만족하는 것을 세는 것입니다.

하지만 문제의 제한조건을 살펴 봅시다.

• info 배열의 크기는 1 이상 50,000 이하입니다.

• query 배열의 크기는 1 이상 100,000 이하입니다.

 그러면 시간복잡도는 상수로 50000 * 100000 이 됩니다.

앞서 말씀드렸듯, 시간복잡도가 10^8 로 넘어가면 시간 초과가 납니다.

따라서 이 풀이는 결코 짜면 안 됩니다.

 

그럼 어떻게 하면 될까요?

조건은 언어, 직군, 경력, 소울 푸드, 점수로 되어 있습니다.

언어, 직군, 경력, 소울 푸드의 가지수를 세면, 

언어가 3종류, 직군이 2중류, 경력이 2종류, 소울 푸드가 2종류이므로

총 24개의 서로 배타적인 집합으로 각 info를 발라낼 수 있습니다.

 

각 쿼리는 점수 이상 혹은 미만이 몇 개인지 살펴보기를 요구하고 있습니다.

만약 각 24개의 집합을 점수를 기준으로 각각 정렬하고, 이진 탐색을 이용한다면,

쿼리가 요구하는 점수에 몇 명이 해당하는지 logN만에 탐색해낼 수 있습니다.

 

이 경우 시간복잡도는 log( 50,000 ) * 100,000가 되고,충분히 합리적인 시간복잡도가 됩니다.

 

아이디어는 구해냈지만, 문자 배열을 파싱해서 24개로 발라낸다는 과정은 복잡한 구현을 필요로 합니다.

만약 C만 익숙한 사용자라면, 좌절감을 겪었을 것입니다.

 

방법론이야 많겠지만, 저는 쿼리와 info를 각각 객체로 정의했습니다.

이 객체들은 string 을 받아서 적절한 정보를 담는 객체로 변환할 수 있음은 물론,

쿼리 객체는 matched(index) 라는 메서드를 가지고 있습니다.

이 index는 0부터 23까지의 정수만을 받음을 가정합니다.

언어, 직군, 경력, 소울 푸드로 분류해낸 24개의 집합이 쿼리가 해당하는 질의에 포함되어야 하는지 리턴하는 메서드입니다.

 

이제 info를 24개로 분류하는 벡터에 집어넣은 뒤에, 벡터를 각각 점수에 대해서 오름차순으로 정렬합니다.

각각 쿼리마다 24번 순회하면서, 정렬된 점수에 이진 탐색을 수행하며 포함되는 것이 몇 개인지 구해냅니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;


struct Info_Raw {
    int language;
    int isBackend;
    int isJunior;
    int isPizza;
    int score;

    int index() {
        int sum = language;
        return language + 3 * isBackend + 6 * isJunior + 12 * isPizza;
    }
};

struct Query_raw{
    bool all_language;
    bool all_end;
    bool all_ex;
    bool all_food;
    int language;
    int isBackend;
    int isJunior;
    int isPizza;
    int score;

    bool matched(int index) {
        int a_language = index % 3;
        index /= 3;
        bool a_isBackend = index % 2;
        index /= 2;
        bool a_isJunior = index % 2;
        index /= 2;
        bool a_isPizza = index % 2;
        if (!all_language && this->language != a_language) {
            return false;
        }
        if (!all_end && isBackend != a_isBackend) {
            return false;
        }
        if (!all_ex && isJunior != a_isJunior) {
            return false;
        }
        if (!all_food && isPizza != a_isPizza){
            return false;
        }
        return true;
    }
};

Info_Raw parse(string input) {
    vector<string> parse;
    string temp = "";
    for (auto e: input) {
        if (e == ' '){
            string deep = temp;
            parse.push_back(deep);
            temp = "";
        } else {
            temp += e;
        }
    }
    parse.push_back(temp);
    Info_Raw answer;
    if (parse[0] == "cpp") {
        answer.language = 0;
    } else if (parse[0] == "java") {
        answer.language = 1;
    } else {
        answer.language = 2;
    }
    answer.isBackend = parse[1] == "backend" ? 1 : 0;
    answer.isJunior = parse[2] == "junior" ? 1 : 0;
    answer.isPizza = parse[3] == "pizza" ? 1 : 0;
    answer.score = stoi(parse[4]);

    return answer;

}

Query_raw parse_q(string input) {
    vector<string> parse;
    string temp = "";
    for (auto e: input) {
        if (e == ' '){
            string deep = temp;
            parse.push_back(deep);
            temp = "";
        } else {
            temp += e;
        }
    }
    parse.push_back(temp);
    Query_raw answer;
     answer.all_language = false;
    if (parse[0] == "cpp") {
        answer.language = 0;
    } else if (parse[0] == "java") {
        answer.language = 1;
    } else if (parse[0] == "python") {
        answer.language = 2;
    } else {
        answer.all_language = true;
    }
    answer.isBackend = parse[2] == "backend" ? 1 : 0;
    answer.all_end = parse[2] == "-";
    answer.isJunior = parse[4] == "junior" ? 1: 0;
    answer.all_ex = parse[4] == "-";
    answer.isPizza = parse[6] == "pizza" ? 1: 0;
    answer.all_food = parse[6] == "-";
    answer.score = stoi(parse[7]);

    return answer;
}



vector<int> solution(vector<string> info, vector<string> query) {


    vector<vector<int>> db(24);
    for (auto e: info) {
        auto result = parse(e);
        db[result.index()].push_back(result.score);
    }

    for (int i=0; i<24; i++) {
        vector<int> &e = db[i];
        sort(e.begin(), e.end());
        //  for (auto ee: e) {
        //     cout << ee << '\n';
        // }
    }

    vector<int> answer;
    for (auto e: query) {
        auto result = parse_q(e);
        int scores = 0;
        for (int i=0; i<24; i++) {
            if (result.matched(i)) {
                vector<int> &now = db[i];
                auto it = lower_bound(now.begin(), now.end(), result.score);
                scores += (now.end() - it);
            }
        }
        answer.push_back(scores);
    }
     // for (auto ee: answer) {
     //        cout << ee << '\n';
     //    }
    return answer;
}

 

 

합승 택시 요금

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

다익스트라 알고리즘은, 그래프에서 한 정점을 기준으로 다른 모든 정점에 대한 최단 거리를 구해낼 수 있습니다.

 

S를 시점으로 다익스트라 알고리즘을 수행하면, S->A 와 S->B의 최단거리를 구해낼 수 있습니다.

 

한편 A와 B가 미지의 정점 X까지 합승한다고 생각해 봅시다.
그럴 경우 최단 거리는 S->X, X->A, X->B 일 것입니다.

 

모든 가능한 X에 대해서 순회하면서 S->X+X->A+X->B를 계산한다고 생각해 봅시다.

 

플로이드 와샬 알고리즘을 쓸 경우, 시간복잡도가 n^3 안에 임의의 두 정점에 대한 최단 거리를 구해낼 수 있습니다.

정점의 개수가 n=200 이므로, 시간복잡도와 공간복잡도가 모두 유의미하게 작아서, AC를 해낼 수 있었다고 추정합니다.

 

하지만, 우리가 원하는 것은

* S 에서 임의의 모든 정점까지의 최단거리

* A 에서 임의의 모든 정점까지의 최단거리

* B 에서 임의의 모든 정점까지의 최단거리

만 필요하다는 것을 주목합니다.

 

따라서 S, A, B를 시점으로 다익스트라를 세 번 수행하면, 플로이드-와샬보다 더 효율적으로 값을 계산해 낼 수 있습니다.

 

각각의 거리가 나오면, 모든 정점을 상대로 순회하면서 가장 최적의 X를 구하는 것뿐입니다,

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;



vector<int> dij(int n, vector<vector<pair<int, int>>> &graph, int index) {
    const int inf = 100000000;
    vector<int> dist(n, inf);

    dist[index] = 0;
    priority_queue<pair<int, int>> q;
    q.push({0, index});
    while (!q.empty()) {
        auto top = q.top();

        int cost = -top.first;
        int here = top.second;
        q.pop();
        if (dist[here] < cost) {
            continue;
        }
        for (auto e: graph[here]) {
            int next = e.first;
            int next_cost = e.second + cost;

            if (dist[next] > next_cost) {
                dist[next] = next_cost;
                q.push({-next_cost, next});
            }
        }
    }
    return dist;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    const int inf = 100000000;

    s--;
    a--;
    b--;
    vector<vector<pair<int, int>>> graph(n);
    for (auto e: fares) {
        int from = e[0];
        int to = e[1];
        int fee = e[2];
        from--;
        to--;
        graph[from].push_back({to, fee});
        graph[to].push_back({from, fee});
    }

    vector<int> a_dist = dij(n, graph, a);
    vector<int> b_dist = dij(n, graph, b);
    vector<int> s_dist = dij(n, graph, s);


    int answer = s_dist[a] + s_dist[b];
    for (int k=0; k<n; k++) {

        int temp = s_dist[k] + a_dist[k] + b_dist[k];
        answer = min(temp, answer);
    }

    return answer;
}

programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

당시 풀려고 시도했지만, 엣지 케이스를 찾지 못해 결국 풀지 못했습니다.

 

공익 광고 시간을 초단위로 쪼갠 다음, 

부분합 배열을 이용하면, 각각 초에 몇 명의 시청자가 시청하고 있는지 계산해낼 수 있습니다.

여기 나아가, 부분합 배열을 한 번 더 계산하면, 00:00:00 부터 해당하는 초까지의 범위에서 누적 시청 시간을 계산해낼 수 있습니다.

이를 바탕으로 최적의 광고 시간을 찾아내면 되는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
#include <string>
#include <iomanip>

using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;

const ll range = 360000;

ll convert(string input) {
    ll hour = (input[0] - '0') * 10 + (input[1] - '0');
    ll minute = (input[3] - '0') * 10 + (input[4] -'0');
    ll second = (input[6] - '0') * 10 + (input[7] - '0');
    return hour * 3600 + minute * 60 + second;
}

pair<ll, ll> convert_log(string & input) {
    ll start = convert(input.substr(0, 8));
    ll end_time = convert(input.substr(9, 8));
    return {start, end_time};
}
string convert_time(ll n){
    string time="00:00:00";
    int s = n%60; n/=60;
    int m = n%60; n/=60;
    int h = n;

    time[0] += h / 10;
    time[1] += h % 10;
    time[3] += m / 10;
    time[4] += m % 10;
    time[6] += s / 10;
    time[7] += s % 10;

    return time;
}
string solution(string play_time, string adv_time, vector<string> logs) {
    ll play = convert(play_time);
    ll adv = convert(adv_time);
    vector<pair<ll, ll>> lo(logs.size());
    for (ll i=0; i<lo.size(); i++) {
        lo[i] = convert_log(logs[i]);
    }
    vector<ll> play_save(play+1);
    for (ll i=0; i<lo.size(); i++) {
        play_save[lo[i].first]++;
        play_save[lo[i].second]--;
    }


    for (ll i=1; i<play_save.size(); i++) {
        play_save[i] += play_save[i-1];
    }
    for (ll i=1; i<play_save.size(); i++) {
        play_save[i] += play_save[i-1];
    }
    ll big = play_save[adv];
    ll that_time = 0;
    for (ll i=0; i+adv<=play; i++) {
        // cout << i << '\n';
        ll current = play_save[i+adv];
//        if (i != 0) {
        current -= play_save[i];
//        }
        if (big < current) {
            big = current;
            that_time = i+1;
//            cout << current << ' ' << i << '\n';
        }
    }

    string answer = convert_time(that_time);
    return answer;
}

 

카드 짝 맞추기

programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

 

문제가 요구하는 복잡한 조건에 압도될 수 있습니다만, 

모든 제한사항이 한 자리 숫자임에 주목합시다.

 

이럴 경우, 시간복잡도를 크게 신경쓰지 않아도 된다는 인상을 받습니다.

그러면, 모든 경우를 계산해도 충분히 풀어낼 수 있지 않을까, 즉 브루트 포스를 진행해도 되지 않을까를 생각하면,

이 문제의 해결의 실마리를 찾으신 것입니다.

 

먼저 각각의 카드패를 짝에 맞게 기억할 수 있도록, 탐색을 진행합니다.

제 경우, vector<vector<pair<int, int>>> cards(6); 에 저장했습니다.

이 배열은 서로 일치하는 카드의 x좌표, y좌표를 저장해 푸시합니다.

 

이제 각 카드 덱이 제거되었는지를 기억하는 vector<bool> is_deleted 을 생각해 내고 dfs를 수행해 냅니다.

 

이 dfs에서는 모든 카드 쌍을 제거해 나가는 순서의 방법을 모두 계산하도록 작성됩니다.

 

1번쌍, 2번쌍... 6번쌍 순으로 제거부터..

6번쌍, 5번쌍, 1번쌍... 순으로 제거까지 모두 계산하겠다는 마음가짐입니다.

 

이제 1번쌍, 2번쌍... 6번쌍 으로 제거하는 것을 가정해 봅시다.

1번쌍에 예를 들어서 카드1 이 (1, 1) 에 있고, (4, 4)에 카드2가 있다고 계산해 봅시다.

 

이번엔 bfs를 써서, 큐에 전후좌우 움직임을 모두 박아넣어서, 최소 몇 턴의 움직임만에

커서를 (1,1)에서 (4,4) 까지 움직일 수 있는지 계산합니다.

 

이런 전탐색을 거쳐서, 최소 움직임을 리턴합니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;


int index(vector<vector<int>> &board) {
    int answer = 0;
    int current = 1;
    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            if (board[i][j]) {
                answer += current;
            }
            current *= 2;
        }
    }
    return answer;
}

bool is_in(int x, int y) {
    return 0 <= x && x < 4 && 0 <= y && y < 4;
}

int minimum_move(vector<vector<int>> board, pair<int, int> from, pair<int, int> to) {

    int move = 0;

    queue<pair<int, int>> q;
    q.push(from);

    vector<vector<bool>> is_visited(4, vector<bool>(4, false));

    is_visited[from.first][from.second] = true;

    vector<vector<int>> direction = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!q.empty()) {
        int size = q.size();

        for (int i=0; i<size; i++) {
            auto top = q.front();
            q.pop();
//            cout << top.first << ' ' << top.second << '\n';
            if (top == to) {
                return move;
            }

            for (auto d: direction) {
                int next_x = top.first + d[0];
                int next_y = top.second + d[1];

                if (is_in(next_x, next_y) && !is_visited[next_x][next_y]) {
                    is_visited[next_x][next_y] = true;
                    q.push({next_x, next_y});
                }
            }

            for (auto d: direction) {
                int current_x = top.first;
                int current_y = top.second;

                while(true) {

                    int next_x = current_x + d[0];
                    int next_y = current_y + d[1];
                    if (!is_in(next_x, next_y)) {
                        break;
                    }
                    if (board[next_x][next_y] != 0) {
                        current_x = next_x;
                        current_y = next_y;
                        break;
                    }
                    current_x = next_x;
                    current_y = next_y;
                }
                if (is_in(current_x, current_y) && !is_visited[current_x][current_y]) {
                    is_visited[current_x][current_y] = true;
                    q.push({current_x, current_y});
                }
            }




        }

        move++;
    }
    return 0;
}

int dfs(int x, int y, vector<bool> &is_deleted, vector<vector<int>> board, int deleted_card_deck, vector<int> &card_deck, vector<vector<pair<int, int>>> & cards) {

    int answer = 100000000;
    if (deleted_card_deck == card_deck.size()) {
        return 0;
    }
    for (int i=0; i<card_deck.size(); i++) {
        if (!is_deleted[i]) {
            is_deleted[i] = true;
            auto deleting_card_pair = cards[card_deck[i]];

            auto first_card_location = deleting_card_pair[0];
            auto second_card_location = deleting_card_pair[1];


            // 첫 카드 이동
            {
                int current_to_first = minimum_move(board, {x, y}, first_card_location);
                board[first_card_location.first][first_card_location.second] = 0;
                int first_to_second = minimum_move(board, first_card_location, second_card_location);
                board[second_card_location.first][second_card_location.second] = 0;

                int candidate_one = dfs(second_card_location.first, second_card_location.second, is_deleted, board,
                                        deleted_card_deck + 1, card_deck, cards);
                candidate_one += (current_to_first + first_to_second + 2);
                board[second_card_location.first][second_card_location.second] = 1;
                board[first_card_location.first][first_card_location.second] = 1;


                answer = min(answer, candidate_one);
            }
            // 둘째 카드 이동
            {
                int current_to_second = minimum_move(board, {x, y}, second_card_location);
                board[second_card_location.first][second_card_location.second] = 0;
//                cout << current_to_second << '\n';
                int second_to_first = minimum_move(board, second_card_location, first_card_location);
                board[first_card_location.first][first_card_location.second] = 0;

                int candidate_two = dfs(first_card_location.first, first_card_location.second, is_deleted, board, deleted_card_deck+1, card_deck, cards);
                candidate_two += (current_to_second + second_to_first + 2) ;
                board[second_card_location.first][second_card_location.second] = 1;
                board[first_card_location.first][first_card_location.second] = 1;

                answer = min(answer, candidate_two);

            }



            is_deleted[i] = false;
        }
    }

    return answer;
}

int solution(vector<vector<int>> board, int r, int c) {

    vector<vector<pair<int, int>>> cards(6);

    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            if (board[i][j] > 0) {
                cards[board[i][j]-1].push_back({i, j});
            }
        }
    }
    vector<int> card_deck;
    for (int i=0; i<6; i++) {
        if (cards[i].size() > 0) {
            card_deck.push_back(i);
        }
    }


    vector<bool> is_deleted(card_deck.size());


    int answer = dfs(r, c, is_deleted, board, 0, card_deck, cards);
    return answer;
}

 

 

매출 하락 최소화

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

코딩테스트 연습 - 매출 하락 최소화

풀었던 문제 중에서 가장 어렵다고 생각합니다. 

카테고리로 치면 그래프 dp 라는 아이디어 싸움에 들어갑니다.

 

트리의 각 리프마다 (내가 참석했을 때 매출하락의 최소값, 내가 참석하지 않았을 때 매출하락의 최소값) 을

저장해 내야 합니다.

이를 f(node) = (a, b) 라고 해봅시다.

내가 참석했을 때 매출하락의 최소값을 생각해 봅시다.

이 경우, 트리의 자식에 해당하는 팀원들은, 팀원 개개인이 참석하든 불참하든 내가 팀장으로 있는 팀은 상관이 없습니다.

내가 참석을 했기 떄문입니다.

따라서 자식들에 대해서 

f(childern).a 와 f(children).b 중 작은 값을 모두 더해 주면 f(node).a가 됩니다.

 

반면, 내가 참석하지 않았을 때 매출하락의 최소값을 생각해 봅시다.

그럼 내 팀원 중에 한 명은, 반드시 이 팀의 대표로서 참석을 해야 합니다.

 

따라서 각 children 에 대해서 순회를 해서 최소값을 구해 내야 합니다.

모든 자식 노드마다, 이 자식 노드가 참가를 한 경우. 즉 f(child).a + sum( min(f(other child).a, f(other child).b)) 를 구합니다.

이는 이 자식 노드가 참가를 하여 조건을 만족했을 경우의 최소값이 될 것입니다.

이 값들을 모든 자식 노드마다 계산을 하여, 어느 자식 노드가 참석을 해야지

매출 하락이 최소가 되는지 계산해냅니다.

 

아이디어는 이런 느낌이며, 구체적인 구현은 tree dp 라고 하는 복잡한 구현의 전형적인 예를 따릅니다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <string>
#include <queue>
using namespace std;

using ld = long double;
using ll = long long;
using pldld = pair<ld,ld>;
using edge = pair<ld, pair<ll, ll>>;
#include <string>
#include <vector>

using namespace std;

#include <string>
#include <vector>

using namespace std;

pair<int, int> dfs(vector<int>& sales, vector<vector<int>> & graphs, int parent_index, int index, vector<bool> is_visited) {

    is_visited[index] = true;

    int inf = 1000000000;
    int value_if_i_checked = 0;
    int value_if_other_checked = inf;
    // 내가 채크했을 때.
    // 내 값 + 남의 값 중 총합.

    // 남이 체크했을 때.
    // 남의 값 중 하나는 반드시 체크해야 함.
    // 나머지는 내 값과 남의 값 중에서 작은 것의 합.

    vector<pair<int, int>> dfs_save(graphs[index].size());
    for (int i=0; i<graphs[index].size(); i++) {
        auto children = graphs[index][i];
        if (children == parent_index) {
            continue;
        }

        auto childern_value = dfs(sales, graphs, index, children, is_visited);
        dfs_save[i] = childern_value;
        if (childern_value.second == inf) {
            continue;
        } else {

        }
        value_if_i_checked += min(childern_value.first, childern_value.second);

    }
    for (int i=0; i<graphs[index].size(); i++) {
        int value = dfs_save[i].first;
        if (graphs[index][i] == parent_index ) {
            continue;
        }
        for (int j=0; j<graphs[index].size(); j++) {
            if (i == j) { continue;}
            if (graphs[index][i] == parent_index) {
                continue;
            }
            if (dfs_save[j].second == inf) {
                continue;
            } else {
                value += min(dfs_save[j].first, dfs_save[j].second);
            }
        }
        value_if_other_checked = min(value_if_other_checked, value);
    }

    value_if_i_checked += sales[index];
    // cout << index + 1 << ' ' << value_if_i_checked << ' ' << value_if_other_checked << '\n';
    return {value_if_i_checked, value_if_other_checked};
}

int solution(vector<int> sales, vector<vector<int>> links) {
    int answer = 0;
    int n = sales.size();
    vector<vector<int>> graph(n);
    for (auto e: links){
        int from = e[0];
        int to = e[1];
        from--; to--;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    vector<bool> is_visited(n);

    auto v = dfs(sales, graph, -1,  0, is_visited);

    return min(v.first, v.second);
}