2021 KAKAO BLIND RECRUITMENT 1차예선 풀이

 

요즘 클린코드 책을 공부하느라 알고리즘에 손을 떼고 있었는데, 다음 달에 있는

2022 KAKAO BLIND RECRUITMENT를 참여하기 위해 연습삼아 풀어봤습니다. (진행중)

싸지방에서 시간이 되는대로 예전 문제까지 풀어볼 생각입니다.

카카오 코딩테스트는 프로그래머스에서 진행되는데 처음 접해보신 분들은 제출 환경에서 당황할 수 도 있습니다.solution 함수를 구현하되 매개변수와 return 값은 건들면 안되고, 제출 시 main 함수는 있어도 되니 똑같이 제출하면 됩니다.

 

---

 

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

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

 

 

A번 신규 아이디 추천

알고리즘 : 구현

예외만 잘 처리해주면 되는 문자열 문제입니다. 숫자에 대한 언급이 적게 있어 빠지지 않도록 유의해야 합니다.

지금 보니 lastPos 변수는 없어도 풀이할 수 있었을 것 같습니다.

 

< CODE - 신규 아이디 추천 >

#include <iostream>
#include <string>

using namespace std;

string solution(string new_id) {
	string answer = "";
	int lastPos = 0;

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

		if (word >= 'A' && word <= 'Z')
			answer += (char)(word + ('a' - 'A'));
		else if (word >= 'a' && word <= 'z' || word >= '0' && word <= '9' || word == '_' || word == '-')
			answer += word;
		else if (word == '.')
		{
			if (new_id[lastPos] == '.')
				continue;
			answer += word;
		}
		else
			continue;

		lastPos = i;
	}

	lastPos = 0;

	if (!answer.empty())
	{
		while (!answer.empty() && answer[lastPos] == '.')
			lastPos++;

		if (lastPos != 0)
		{
			if (lastPos == answer.length())
				answer = "";
			else
				answer = answer.substr(lastPos, answer.length() - lastPos);
		}
	}

	while(!answer.empty() && answer[answer.length() - 1] == '.')
		answer.pop_back();

	while (answer.empty())
		answer = "a";

	if (answer.length() >= 16)
	{
		answer = answer.substr(0, 15);

		while (!answer.empty() && answer[answer.length() - 1] == '.')
			answer.pop_back();
	}

	while (answer.length() <= 2)
		answer += answer[answer.length() - 1];

	return answer;
}

 

---

 

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

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

 

 

B번 메뉴 리뉴얼

알고리즘 :  비트마스크 / 우선순위큐 / 구현

각 손님에 대해 나오는 모든 경우를 구해서 각 조합을 비트로 나타냅니다. 

각 조합이 몇 번 나왔는지 1 << 26개의 경우를 나타내는 배열에 더해준 후 코스에 속하는 요리 수(1~10)를 대표하는

우선순위 큐에 각 개수를 넣어 최고의 코스 요리를 뽑습니다. 후에 문제를 해결해주면 됩니다.

 

< CODE - 메뉴 리뉴얼 >

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int cnt[1 << 26];
bool courseSize[11];
bool chk[26] = { 0, };
priority_queue<pair<int, int>> pq[11];

void makeCourse(const string & order, int orderIdx, int courseAmount, int courseSet)
{
	if (courseSize[courseAmount])
		cnt[courseSet]++;

	if (courseAmount >= order.size())
		return;

	for (int i = orderIdx; i < order.length(); i++)
	{
		int cur = order[i] - 'A';

		chk[cur] = true;

		int nextCourseSet = courseSet | (1 << cur);

		makeCourse(order, i + 1, courseAmount + 1, nextCourseSet);

		chk[cur] = false;
	}
}

vector<string> solution(vector<string> orders, vector<int> course) {
	vector<string> answer;

	for (int i = 0; i < course.size(); i++)
		courseSize[course[i]] = true;

	for (int i = 0; i < orders.size(); i++)
		makeCourse(orders[i],0,0,0);

	for (int i = 1; i < (1 << 26); i++)
	{
		if (cnt[i] >= 2)
		{
			//__builtin_popcount(i)
			int bitCnt = __builtin_popcount(i);
			pq[bitCnt].push({ cnt[i],i });
		}
	}

	for (int i = 0; i < course.size(); i++)
	{
		int j = course[i];
		int mSize = pq[j].top().first;

		while (!pq[j].empty())
		{
			pair<int, int> cur = pq[j].top(); pq[j].pop();

			if (cur.first != mSize)
				break;

			string ans = "";

			int lastIdx = 0;

			while (lastIdx < 26)
			{
				if (cur.second & (1 << lastIdx))
					ans += (lastIdx + 'A');

				lastIdx++;
			}

			answer.push_back(ans);
		}
	}

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

	return answer;
}

 

---

 

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

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

 

 

C번 순위 검색

알고리즘 :  정렬 / 이분탐색

조금 더럽게 풀지 않았나 싶은 문제입니다.

처음 기저로 문자열에 대한 숫자값을 맵에 저장한 후 모든 경우에 대한 벡터를 만들어줍니다. (3*2*2*2 = 24)

각 경우에 대해 인원을 벡터에 추가하고 모든 인원이 추가되었을 때 모든 벡터를 정렬합니다.

이 과정에서 각 벡터의 크기를 m이라 했을 때 시간복잡도는 O(24mlogm) 이지만 모든 m의 합이 100,000이고,

log m을 log 100,000이라고 가정하면 (m_1 + m_2 + m_3 ... + m_k) log 100,000이고, m들의 합은 n이므로

전체적으로 O(nlogn)정도가 소요됩니다.

그렇게 정렬된 벡터들에서 해당 쿼리에서 가능한 경우를 모두 순회하여(최대 24) lower_bound를 통해 답을 찾습니다.

(시간복잡도는 위와 같습니다.)

그렇게 하여 문제를 풀이합니다.

 

처음에는 multiset으로 풀이하려다 multiset에서 두 iterator의 거리를 구하는 distance라는 함수를 사용했는데 시간초과가 났습니다.

알아보니 해당 함수는 random access인 경우엔 상수시간, 아닌 경우에는 선형시간이 걸린다고 합니다.

 

 

< CODE - 순위 검색 >

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

map<string, int> m;
vector<int> vs[3][2][2][2];

void init()
{
	m["cpp"] = m["backend"] = m["junior"] = m["chicken"] = 0;
	m["java"] = m["frontend"] = m["senior"] = m["pizza"] = 1;
	m["python"] = 2;
}

vector<string> split(string s)
{
	vector<string> ret;
	string now;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == ' ')
		{
			ret.push_back(now);
			now = "";
			continue;
		}

		now += s[i];
	}

	if(!now.empty())
		ret.push_back(now);

	return ret;
}

vector<string> split_query(string s)
{
	vector<string> ret;
	string now;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == ' ')
		{
			ret.push_back(now);
			now = "";

			if(ret.size() != 4)
				i += 4;
			continue;
		}

		now += s[i];
	}

	if (!now.empty())
		ret.push_back(now);

	return ret;
}

int solve(vector<string> cur, int score)
{
	int ret = 0;

	vector<int> v1, v2, v3, v4, v5;

	if (cur[0] == "-")
	{
		v1.push_back(0);
		v1.push_back(1);
		v1.push_back(2);
	}
	else
		v1.push_back(m[cur[0]]);

	if (cur[1] == "-")
	{
		v2.push_back(0);
		v2.push_back(1);
	}
	else
		v2.push_back(m[cur[1]]);

	if (cur[2] == "-")
	{
		v3.push_back(0);
		v3.push_back(1);
	}
	else
		v3.push_back(m[cur[2]]);

	if (cur[3] == "-")
	{
		v4.push_back(0);
		v4.push_back(1);
	}
	else
		v4.push_back(m[cur[3]]);

	for (int i = 0; i < v1.size(); i++)
	{
		for (int j = 0; j < v2.size(); j++)
		{
			for (int k = 0; k < v3.size(); k++)
			{
				for (int l = 0; l < v4.size(); l++)
				{
					vector<int> & now = vs[v1[i]][v2[j]][v3[k]][v4[l]];

					if (now.empty())
						continue;

					auto idx = lower_bound(now.begin(), now.end(), score);

					ret += (now.end() - idx);
				}
			}
		}
	}

	return ret;
}

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

	for (int i = 0; i < info.size(); i++)
	{
		vector<string> cur = split(info[i]);
		int score = stoi(cur[4]);

		vs[m[cur[0]]][m[cur[1]]][m[cur[2]]][m[cur[3]]].push_back(score);
	}

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				for (int l = 0; l < 2; l++)
					sort(vs[i][j][k][l].begin(), vs[i][j][k][l].end());

	for (int i = 0; i < query.size(); i++)
	{
		vector<string> cur = split_query(query[i]);
		int score = stoi(cur[4]);

		answer.push_back(solve(cur, score));
	}

	return answer;
}

 

---

 

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

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

 

 

D번 합승 택시 요금

알고리즘 : 플로이드 워샬

플로이드 워샬을 통해 각 vertex에서 vertex까지의 최소 비용을 구합니다. 

그리고 각 첫 시작 정점에서 i번째 정점까지 같이 택시를 타고 i번째에서 A는 a로 B는 b로 가는 최소비용인

fw[i][a]와 fw[i][b]를 더해준 값 중 최저값을 구하면 해결됩니다.

(택시를 타고 가다 헤어지고 다시 만나서 택시를 같이 타게 되면 최소비용이 아니게 됩니다.)

 

< CODE - 합승 택시 요금 >

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 203
#define INTMAX 10000000001
typedef long long int ll;

ll fw[MAX][MAX];

void calculateFW(int n)
{
    
	for(int k = 1; k <= n; k++)	
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(fw[i][k] + fw[k][j] < fw[i][j])
                    fw[i][j] = fw[i][k] + fw[k][j];
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    ll answer;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
		{
			if(i == j)
				fw[i][j] = 0;
			else
				fw[i][j] = INTMAX;
		}

    
	for(int i = 0; i < fares.size(); i++)
	{
		fw[fares[i][0]][fares[i][1]] = fares[i][2];
		fw[fares[i][1]][fares[i][0]] = fares[i][2];
	}

	calculateFW(n);

	answer = fw[s][a]+fw[s][b];

	for(int i = 1; i <= n; i++)
	{
		ll basis = fw[s][i] + fw[i][a] + fw[i][b];

		answer = min(answer, basis);
	} 
    
    return answer;
}

 

---

 

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

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

 

E번 광고 삽입

알고리즘 : 슬라이딩 윈도우 / 세그먼트 트리?

처음에 문제를 보고 레이지 프로퍼게이션을 이용한 세그먼트 트리 문제로 오인하여 삽질을 한 문제입니다. 더티 코딩을 해서

세그먼트 트리로 문제를 풀이해 3 테스트 케이스(4, 15, 17(에서 트려 90.3 / 100 점을 받았지만 이 이상 진행을 못하였습니다.

아마도 가장 빠른 시간을 출력해야 되는 부분에서 틀린 것 같지만 정확한 오답의 원인은 찾지 못했습니다.

(계속하면 100점도 맞을 수 있을 것 같지만 포기..)

이상함을 느껴 문제 풀이법을 바꾸어 슬라이딩 윈도우 기법을 사용하여 총 시간 100시간을 360000초로 치환하고, 1초를 더하고 이전 1초를 빼는 식으로 진행하여 풀이하였습니다. 저같은 실수를 하신 분들을 위해 세그먼트 트리 코드도 올려놓겠습니다.

 

 

 

 

< CODE - 광고 삽입(슬라이딩 윈도우) >

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

#define MAX 360005
typedef long long int ll;

ll arr[MAX];

vector<ll> split(string str)
{
    vector<ll> ret;

    int now = 0;
    string curStr = "";

    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == ':')
        {
            now *= 60;
            now += stoi(curStr);
            curStr = "";
        }
        else if (str[i] == '-')
        {
            now *= 60;
            now += stoi(curStr);
            ret.push_back(now);
            now = 0;
            curStr = "";
        }
        else
            curStr += str[i];
    }

    now *= 60;
    now += stoi(curStr);
    ret.push_back(now);

    return ret;
}

string rvs(int time)
{
    string ret = "";

    if (time / 3600 < 10)
        ret += '0';

    ret += to_string(time / 3600);
    ret += ':';
    time %= 3600;


    if (time / 60 < 10)
        ret += '0';

    ret += to_string(time / 60);
    ret += ':';
    time %= 60;

    if (time < 10)
        ret += '0';

    ret += to_string(time);

    return ret;
}

string solution(string play_time, string adv_time, vector<string> logs)
{
    ll answer = 0;

    ll iPlayTime = split(play_time)[0];
    ll iAdvTime = split(adv_time)[0];

    ll mResult = 0;
    ll result = 0;
    ll pos = 0;

    for (int i = 0; i < logs.size(); i++)
    {
        vector<ll> curTime = split(logs[i]);

        arr[curTime[0]]++;
        arr[curTime[1]]--;
    }

    for (int i = 1; i <= iPlayTime; i++)
    {
        arr[i] += arr[i - 1];

        if (i < iAdvTime)
            result += arr[i];
    }

    mResult = result;

    for (int i = iAdvTime; i <= iPlayTime; i++)
    {
        result -= arr[i - iAdvTime];
        result += arr[i];

        if (result > mResult)
        {
            mResult = result;
            pos = i - iAdvTime + 1;
        }
    }

    return rvs(pos);
}

int main()
{
    string play_time = "02:03:55";
    string adv_time = "00:14:15";
    vector<string> logs = {"01:20:15-01:45:14", "00:40:31-01:00:00", "00:25:50-00:48:29", "01:30:59-01:53:29", "01:37:44-02:02:30"
};
    cout << solution(play_time, adv_time, logs) << endl;

    return 0;
}

---

< CODE - 광고 삽입 (세그먼트 트리) >

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

#define MAX 2500005
typedef long long int ll;

ll segT[MAX];
ll lazy[MAX];

ll s2[MAX];

vector<vector<ll>> v;
vector<ll> times;
ll mResult = 0;

vector<ll> split(string str)
{
    vector<ll> ret;

    int now = 0;
    string curStr = "";

    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == ':')
        {
            now *= 60;
            now += stoi(curStr);
            curStr = "";
        }
        else if (str[i] == '-')
        {
            now *= 60;
            now += stoi(curStr);
            ret.push_back(now);
            now = 0;
            curStr = "";
        }
        else
            curStr += str[i];
    }

    now *= 60;
    now += stoi(curStr);
    ret.push_back(now);

    return ret;
}

void lazy_propagation(int idx, int start, int end)
{
    if (lazy[idx] != 0)
    {
        segT[idx] += ((ll)times[end + 1] - times[start]) * lazy[idx];
        s2[idx] += lazy[idx];

        if (start < end)
        {
            lazy[idx * 2] += lazy[idx];
            lazy[idx * 2 + 1] += lazy[idx];
        }

        lazy[idx] = 0;
    }
}

void update(int idx, int start, int end, int left, int right)
{
    lazy_propagation(idx, start, end);

    if (right < left || right < start || left > end)
        return;

    if (left <= start && end <= right)
    {
        segT[idx] += ((ll)times[end + 1] - times[start]);
        s2[idx] += 1;

        if (start < end)
        {
            lazy[idx * 2] += 1;
            lazy[idx * 2 + 1] += 1;
        }

        return;
    }

    int mid = (start + end) / 2;

    update(idx * 2, start, mid, left, right);
    update(idx * 2 + 1, mid + 1, end, left, right);

    segT[idx] = segT[idx * 2] + segT[idx * 2 + 1];
}

ll sum(int idx, int start, int end, int left, int right, ll maximum)
{
    lazy_propagation(idx, start, end);

    if (left > end || right < start)
        return 0;
    if (left <= start && end <= right)
    {
        if (start != end && times[end + 1] > maximum)
        {
            int mid = (start + end) / 2;

            return sum(idx * 2, start, mid, left, right, maximum) + sum(idx * 2 + 1, mid + 1, end, left, right, maximum);
        }

        if (times[end + 1] > maximum)
            return ((ll)maximum - times[end]) * s2[idx];

        return segT[idx];
    }

    int mid = (start + end) / 2;

    return sum(idx * 2, start, mid, left, right, maximum) + sum(idx * 2 + 1, mid + 1, end, left, right, maximum);
}

string rvs(int time)
{
    string ret = "";

    if (time / 3600 < 10)
        ret += '0';

    ret += to_string(time / 3600);
    ret += ':';
    time %= 3600;


    if (time / 60 < 10)
        ret += '0';

    ret += to_string(time / 60);
    ret += ':';
    time %= 60;

    if (time < 10)
        ret += '0';

    ret += to_string(time);

    return ret;
}

string solution(string play_time, string adv_time, vector<string> logs)
{
    ll answer = 0;

    ll iPlayTime = split(play_time)[0];
    ll iAdvTime = split(adv_time)[0];

    for (int i = 0; i < logs.size(); i++)
    {
        vector<ll> curTime = split(logs[i]);

        times.push_back(curTime[0]);
        times.push_back(curTime[1] - 1);

        v.push_back(curTime);
    }

    times.push_back(0);
    times.push_back(iPlayTime);

    sort(times.begin(), times.end());

    for (int i = 0; i < v.size(); i++)
    {
        int sPos = lower_bound(times.begin(), times.end(), v[i][0]) - times.begin();
        int ePos = lower_bound(times.begin(), times.end(), v[i][1]) - times.begin();

        update(1, 1, times.size(), sPos, ePos);
    }

    for (int i = 0; i < iPlayTime - iAdvTime + 1; i++)
    {
        int sPos = lower_bound(times.begin(), times.end(), i) - times.begin();
        int ePos = lower_bound(times.begin(), times.end(), i + iAdvTime) - times.begin();

        ll result = 0;

        result = sum(1, 1, times.size(), sPos, ePos, i + iAdvTime);

        if (mResult < result)
        {
            mResult = result;
            answer = i;
        }
    }

    return rvs(answer);
}

 

---

 

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

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

 

F번 카드 짝 맞추기

알고리즘 : BFS  /  브루트포스 / 비트마스크

카드를 없애는 순번을 가진 시컨스 경우를 모두 구해 6! 개의 경우를 구합니다. 

각 경우에서 한 숫자에 대해 카드가 두개이므로 두 카드에 대해서 어떤 순서로 답을 구할지 정한 후 계산하면

2^6*6!개의 경우가 나오고, bfs를 통해 현재 커서에서 첫 카드, 첫 카드에서 두번째 카드까지의 거리를 구해서 

min값으로 구하면 구현할 수 있는 문제입니다. bfs에서 방문한 점은 총 16칸이므로 비트마스크를 통해 메모이제이션 해주었습니다.

 

 

 

< CODE - 카드 짝 맞추기 >

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

#define INTMAX 987654321

struct Point
{
    int y;
    int x;

    bool operator==(const Point& b)
    {
        if (this->y == b.y && this->x == b.x)
            return true;
        return false;
    }
};

struct curCondition
{
    Point cursor;
    int curSequence;
    int curMove;
};

vector<int> vSequence;
vector<Point> cardPos[8];
bool isCardUsed[8];
int copyBoard[4][4];
int minCardNum=9;
int maxCardNum;
int sequenceLimit;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

void createSequence(int sum)
{
    if (sum >= sequenceLimit / 10)
    {
        vSequence.push_back(sum);
        return;
    }

    for (int i = maxCardNum+minCardNum - 1; i >= minCardNum; i--)
    {
        if (!isCardUsed[i])
        {
            isCardUsed[i] = true;
            createSequence(sum * 10 + i);
            isCardUsed[i] = false;
        }
    }
}

void createSequences()
{
    sequenceLimit = pow(10, maxCardNum);

    createSequence(0);
}

int getMaxCardNum(const vector<vector<int>> board)
{
    int ret = 0;

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (board[i][j] != 0)
            {
                minCardNum = min(minCardNum, board[i][j]);
                ret++;
            }

    return ret / 2;
}

void dividePositionOfCardsByNum(const vector<vector<int>> board)
{
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
        {
            if (board[i][j] != 0)
                cardPos[board[i][j]].push_back({ i,j });
            copyBoard[i][j] = board[i][j];
        }
}

bool Safe(Point p)
{
    if (p.y >= 0 && p.x >= 0 && p.y <= 3 && p.x <= 3)
        return true;
    return false;
}

Point jump(Point from, int direction)
{
    Point ret = {-1,-1};
    int mul = 1;

    while (true)
    {
        int dY = from.y + dy[direction] * mul;
        int dX = from.x + dx[direction] * mul;

        if (!Safe({ dY,dX }))
            break;

        ret = { dY,dX };

        if (!isCardUsed[copyBoard[dY][dX]])
            break;

        mul++;
    }

    return ret;
}

struct forQ
{
    Point from;
    Point to;
    int move;
    int visit = 0;
};


int getDistance(Point from, Point to, int move)
{
    queue<forQ> q;
    int visit = 0;
    visit |= (1 << (from.y * 4 + from.x));
    
    q.push({from, to, 0,visit});
    
    while(!q.empty())
    {
        forQ cur = q.front(); q.pop();
        
        if(cur.from == cur.to)
            return cur.move;
        
        //CTRL
        for (int i = 0; i < 4; i++)
        {
            Point there = jump(cur.from, i);

            if(there.y == -1)
                continue;
            
            if(!(cur.visit & (1 << (there.y*4+there.x))))
            {
                int temp = cur.visit | (1 << (there.y*4+there.x));
                q.push({there,to,cur.move+1,temp});
            }
        }
                              
        //MOVE NEARBY
        for (int i = 0; i < 4; i++)
        {
            Point there = { cur.from.y + dy[i], cur.from.x + dx[i] };

            if (Safe(there) && !(cur.visit & (1 << (there.y * 4 + there.x))))
            {
                int temp = cur.visit | (1 << (there.y*4+there.x));
                q.push({there,to,cur.move+1,temp});
            }
        }
    }
                                        
    return 98765;
}

int getResult(curCondition cur)
{
    if (cur.curSequence == 0)
    {
        //cout << cur.curMove << endl;
        return cur.curMove;
    }

    int towardPos = cur.curSequence % 10;

    Point p1 = cardPos[towardPos][0];
    Point p2 = cardPos[towardPos][1];

    int p1Movement = getDistance(cur.cursor, p1, 0) + getDistance(p1, p2, 0);
    int p2Movement = getDistance(cur.cursor, p2, 0) + getDistance(p2, p1, 0);

   //cout << cur.cursor.y << ',' << cur.cursor.x << ' ' << p1.y << "," << p1.x << ' ' << p2.y << "," << p2.x << endl;
    //cout << p1Movement << ' ' << p2Movement << '\n';
    
    isCardUsed[towardPos] = true;

    int ret = min(getResult({ p2,cur.curSequence / 10, cur.curMove + p1Movement }), getResult({ p1, cur.curSequence / 10, cur.curMove + p2Movement }));
    
    isCardUsed[towardPos] = false;
    
    return ret;
}

int solve(int curSequence, int r, int c)
{
    Point cursor = { r,c };

    curCondition curC1 = { cursor, curSequence, 0 };

    int ret = getResult(curC1);

    //cout << ret + maxCardNum * 2 << endl;
    
    return ret + maxCardNum * 2;
}

int solution(vector<vector<int>> board, int r, int c)
{
    int answer = INTMAX;
    maxCardNum = getMaxCardNum(board);
    dividePositionOfCardsByNum(board);
    createSequences();

    isCardUsed[0] = true;

    for (int i = 0; i < vSequence.size(); i++)
    {
        answer = min(answer, solve(vSequence[i], r, c));
    }
    
    return answer;
}

int main()
{
    vector<vector<int>> board = { {1, 0, 0, 3}, {2, 0, 0, 0}, {0, 0, 0, 2}, {3, 0, 1, 0} };
    int r = 1;
    int c = 0;

    cout << solution(board, r, c) << endl;

    return 0;
}

 

---

 

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

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

 

G번 매출 하락 최소화

알고리즘 : 트리 DP

dp[idx][0] : 현재 idx번째 사원이 세미나를 안 가는 경우

dp[idx][1] : 현재 idx번째 사원이 세미나를 가는 경우

로 정의하여 리프노드부터 처리하지 않은 자식노드가 0이 되는 사원을 큐에 넣어 처리합니다.

그렇게 자식이 있는 팀장인 경우 팀의 사원들이 참여하는 경우와 참여하지 않는 경우 중 최소값을 구하고 만약 팀장이 세미나를 안 가는 경우에 자식들이 모두 안 가는 경우는 안되므로 그 경우를 처리해주면 답을 구할 수 있습니다.

 

< CODE - 매출 하락 최소화>

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

using namespace std;

#define INF 2147483647;
#define MAX 300005

int dp[MAX][2];
int par[MAX];
vector<int> child[MAX];
int childCount[MAX];
queue<int> leaf;

int solution(vector<int> sales, vector<vector<int>> links) 
{
    int answer = 0;

    for (int i = 1; i <= sales.size(); i++)
    {
        par[i] = i;
    }

    for (int i = 0; i < links.size(); i++)
    {
        child[links[i][0]].push_back(links[i][1]);
        childCount[links[i][0]]++;
        par[links[i][1]] = links[i][0];
    }

    for (int i = 1; i <= sales.size(); i++)
    {
        if (child[i].empty())
        {
            dp[i][0] = 0;
            dp[i][1] = sales[i - 1];

            if (--childCount[par[i]] == 0)
                leaf.push(par[i]);
        }
    }

    while (!leaf.empty())
    {
        int now = leaf.front(); leaf.pop();

        bool success = false;
        int minDiff = INF;

        dp[now][1] = sales[now - 1];

        for (int i = 0; i < child[now].size(); i++)
        {
            int c = child[now][i];

            if(!success)
                success = dp[c][0] >= dp[c][1];
            if (dp[c][1] > dp[c][0])
                minDiff = min(minDiff, dp[c][1] - dp[c][0]);
           
            dp[now][0] += min(dp[c][0], dp[c][1]);
            dp[now][1] += min(dp[c][0], dp[c][1]);
        }

        if (!success)
            dp[now][0] += minDiff;

        if (now == par[now])
        {
            answer = min(dp[now][0], dp[now][1]);
            continue;
        }

        if (--childCount[par[now]] == 0)
            leaf.push(par[now]);
    }

    return answer;
}

 

---

 

<2020 KAKAO BLIND RECRUITMENT 1차예선 풀이>

2020 KAKAO BLIND RECRUITMENT 1차예선 풀이(진행중)

 

태그 :  #2021 카카오 코딩테스트 #2021 카카오 코테 #카카오 코딩테스트 #카카오 코테 #2021 카카오 #2021 카카오 블라인드 코딩테스트 1차

#2021 카카오 코딩테스트 2차 #2021 카카오 블라인드 1차 #카카오 문제 #카카오 순위검색 #카카오 신규 아이디 추천 #카카오 메뉴 리뉴얼

#2021 KAKAO BLIND RECRUITMENT #카카오 광고 삽입 #카카오 합승택시요금 #카카오 매출 하락 최소화 #카카오 1차 합격컷