Developer with Cat
© 2021. All rights reserved.
#[프로그래머스✈][2017 카카오코드] 4단 고음 해설
🛑🛑 아이유 팬은 주의 🛑🛑 🛑🛑 아이유 팬은 주의 🛑🛑 🛑🛑 아이유 팬은 주의 🛑🛑 🛑🛑 해당문제를 풀지 말고 돌아가길 권고 🛑🛑
우리 지은이는 3단 고음을 넘어 4단 고음을넘어 2147483647 단 고음을 연습중이다.
우리 지은이는 현재 음계의 3배 (음계에 배수라는게 존재하는지 모르겠다.) 높은 음계를 낼 수 있고 반드시 3단 점프를 한 후에는 음계를 한 단계씩 두 번을 더 높게 내야한다. 하지만 굳이 연속으로 1단 점프를 할 필요는 없다.
예시 )
(가능)
(불가능)
자세한 문제를 프로그래머스 홈페이지를 참고하는걸 강력히 권고
자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기
전형적인 DFS 문제이다. 범위가 INT_MAX에 해당하는 값이 있으므로 들어오는 인풋을 기준으로 역추적을 하여 1까지 찾아가는 것을 추천한다.
DFS 문제이지만 범위가 매우 크므로 적당한 가지치기가 필요하다. 3단 점프의 최대 가능 범위를 구하고, 3단 점프와 1단 점프간의 상관관계 (3단 점프 후에는 반드시 1단 점프 2번이 와야함.)
프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.
#include<vector> #include<algorithm> using namespace std; void dfs(int plusCt, int multiCt,int i, int num); int g_ans; long long maxNum[100]; long long minNum[100]; int solution(int n); int main() { solution(15); } int solution(int n) { g_ans = 0; int i = 1; maxNum[0] = 5; while (maxNum[i - 1] < 2147483647) { maxNum[i] = maxNum[i - 1] * 3 + 2; i++; } i = 1; minNum[0] = 3; while (minNum[i - 1] < 2147483647) { minNum[i] = minNum[i - 1] * 3; i++; } i = 0; while (true) { if (n < maxNum[i]) break; i++; } dfs(0, 0, i + 1, n); return g_ans; } void dfs(int plusCt, int multiCt, int i, int num){ if (plusCt > i * 2 || multiCt > i || num == 0) return; if (multiCt * 2 > plusCt) return; if (num == 1 && multiCt * 2 == plusCt) { g_ans++; return; } if(num % 3 == 0) dfs(plusCt, multiCt + 1, i, num / 3); dfs(plusCt + 1, multiCt, i, num - 1); }
프로그래머스도 성장하고 있구나를 많이 느꼈따.
당시 코드 템플릿이나 채점 등 지금과 비교하면 많이 부족한 것을 느낄 수 있다.
그리고 아이유는 아이유다.
#[백준🔉][14501] 퇴사 문제 해설
우리팀에서 가장 열심히, 돈을 위해 직장을 다니던 훌륭한 백준 직원이 퇴사를 하려고 한다. 퇴사하기 전까지 가장 많은 돈을 버는 (가장 많은 일을 하는게 아닌) 계획을 짜고 수행하려 한다. 백준이가 돈을 많이 벌 수 있게 도와주자.
자세한 문제 설명과 제한 사항은 백준 홈페이지 참고. 문제풀러가기
우리 백준이는 N + 1 일에 퇴사하기 때문에 N 일 까지는 일을 한다. 상담완료에 걸리는 일자가 3일이면 해당하는 날을 포함해 3일 이라는 것을 명심하자.
전형적인 DFS 문제이며 시작하는 일부터 N 일까지 탐색 후, 얼마를 벌었는지 가능한 케이스를 모두 조사하는 것이다.
백준 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 코드에는 테스트 코드가 존재합니다.
#include<iostream> #include<vector> #include<string> #include<algorithm> struct Task { int period; int earn; }; using namespace std; void dfs(int idx, int endDay, int money); vector<Task> myTask; int myMoney = -1; int main() { int TC; cin >> TC; myTask.assign(TC, {0, 0}); for (int i = 0; i < TC; i++) cin >> myTask[i].period >> myTask[i].earn; for (int i = 0; i < myTask.size(); i++) if (myTask[i].period + i <= myTask.size()) dfs(i + 1, i + myTask[i].period, myTask[i].earn); cout << myMoney; } // void dfs(int idx,int endDay,int money) { for (int i = idx; i < myTask.size(); i++) if(endDay <= i && myTask[i].period + i <= myTask.size()) dfs(i + 1, i + myTask[i].period, money + myTask[i].earn); myMoney = max(myMoney, money); }
DFS의 전형적인 문제로서 기본이 되는 문제였다. 나는 문제를 잘못 읽어서 1시간동안 이상한 짓을 했다.
퇴사를 하기 전까지 열심히 일하는 백준이. 백준이 상사는 훌륭한 부하가 나가기 때문에 매우 심기가 불편할 것 같다.
#[프로그래머스✈][2020 kakao] 동굴 탐험
우리 프로도는 특정한 규칙을 세워서 동굴의 각 방들을 탐험 하려고 한다. 해당 규칙을 만족하게 계획을 세우고 모든 방을 탐험할 수 있는지 탐색하라!
루트부터 각각의 방들을 탐색하며, 선행이 필요한 방은 이후에 다시 조사한다!
선행이 되는 방을 방문한다면, 선행이 필요한 방은 방문 가능하다고 판단한다.
#include <string> #include <vector> #include <deque> #include <string.h> using namespace std; int pre[200000]; int post[200000]; int hang[200000]; vector<vector<int>> myTree; bool visit[200000]; bool solution(int n, vector<vector<int>> path, vector<vector<int>> order); int main() { vector<vector<int>> path = { {0,1} ,{0,3},{0,7},{8,1},{3,6},{1,2},{4,7},{7,5} }; vector<vector<int>> order = { {8, 5}, {6, 7}, {4, 1} }; vector<vector<int>> path2 = { {8,1},{0,1},{1,2},{0,7},{4,7},{0,3},{7,5},{3,6} }; vector<vector<int>> order2 = { {4, 1}, {5, 2} }; vector<vector<int>> path3 = { {0, 1}, {0, 3}, {0, 7}, {8, 1}, {3, 6}, {1, 2}, {4, 7}, {7, 5} }; vector<vector<int>> order3 = { {4, 1}, {8, 7}, {6, 5} }; bool answer = solution(9, path, order); } bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) { myTree.assign(200000, vector<int>(0)); memset(post, -1,sizeof(post)); memset(pre, -1, sizeof(pre)); memset(hang, -1, sizeof(hang)); for (int i = 0; i < path.size(); i++){ myTree[path[i][0]].push_back(path[i][1]); myTree[path[i][1]].push_back(path[i][0]); } for (int i = 0; i < order.size(); i++){ if (order[i][1] == 0) return false; pre[order[i][0]] = order[i][1]; post[order[i][1]] = order[i][0]; } deque<int> myStack; myStack.push_back(0); visit[0] = true; while (!myStack.empty()) { int node = myStack.back(); myStack.pop_back(); for (int i = 0; i < myTree[node].size(); i++) { int target = myTree[node][i]; if (visit[target] == true) continue; if (pre[target] != -1) { if (hang[pre[target]] != -1) { myStack.push_back(pre[target]); } myStack.push_back(target); } else if (post[target] != -1) { if (visit[post[target]]) { myStack.push_back(target); } else hang[target] = post[target]; } else { myStack.push_back(target); } visit[target] = true; } } for (size_t i = 0; i < n; i++) { if (visit[i] != true) return false; } return true; }
매우 힘든 문제였다. 처음 풀었다가 효율성 마지막 번호만 통과하지 못하는 최악의 상황을 통과하지 못했다.
단순하게 스택-큐 같이 넣어 버린다면 효율성 마지막 케이스에서 시간초과가 뜰 것이다.
또한 이 미친 제출자는 0번 방을 들리기 전에 필요한 선행조건을 테스트 케이스로 만들어놨으니 주의.
걍풀지마세요. 답보고 푸세요.😁😁😁🤣🤣🤣
#[프로그래머스✈][2019 kakao 겨울 인턴십] 불량 사용자 문제 해설
우리가 사용자를 밴 할껀데 사실 나도 누가 밴 해야하는지 원본을 잃어버렸어… 혹시 가능한 경우의 수… 니가 좀 구해줄래? 일단 한번 보고 다 밴하던가 할게….
문자열에 별표가 들어있다. 이 문자열의 별표는 알파벳과 숫자로 대체 가능하다. 조건에 맞는 유저들을 찾아라.
별표는 무조건 단 하나의 문자와 대응 가능하기 때문에 문제는 어렵지 않다.
2차원 배열을 만든 후 banned_id에 대응하는 user_id를 체크하고 각 경우의 수를 구한다면 나름 쉽게 풀 수 있다.
#include <string> #include <vector> #include <algorithm> using namespace std; bool isMatch[10][10]; // ban, user 순 bool isUsed[10]; int bansize = 0; vector<vector<int>> ansVec; bool check(string userid, string banid); void travel(int banidx, int userNum, vector<int> ans); int solution(vector<string> user_id, vector<string> banned_id); int main() { string s = "frodo"; string test = s.substr(4); vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" }; vector<string> banned_id = { "fr*d*", "abc1**" }; solution(user_id, banned_id); } int solution(vector<string> user_id, vector<string> banned_id) { int answer = 1; bansize = banned_id.size(); for (size_t i = 0; i < banned_id.size(); i++) for (size_t j = 0; j < user_id.size(); j++) if (check(user_id[j], banned_id[i])) isMatch[i][j] = true; int startLine = -1; vector<int> ans; travel(0, user_id.size(), ans); return ansVec.size(); } void travel(int banidx, int userNum ,vector<int> ans) { if (banidx == bansize) { sort(ans.begin(), ans.end()); for (int i = 0; i < ansVec.size(); i++) { bool flag = true; for (int j = 0; j < ansVec[i].size(); j++){ if (ans[j] != ansVec[i][j]) flag = false; } if (flag == true) return; } ansVec.push_back(ans); return; } bool isExist = false; for (size_t i = 0; i < userNum; i++) if (isMatch[banidx][i] == true) isExist = true; if (isExist == false) { travel(banidx + 1, userNum, ans); return; } for (size_t i = 0; i < userNum; i++){ if (isUsed[i] == true) continue; if (isMatch[banidx][i] == true) { ans.push_back(i); isUsed[i] = true; travel(banidx + 1 , userNum, ans); ans.pop_back(); isUsed[i] = false; } } } bool check(string user, string ban) { if (user.size() != ban.size()) return false; for (size_t i = 0; i < ban.size();i++) { if (user[i] != ban[i] && ban[i] != '*') return false; } return true; }
BANNED 당한 유저를 * 로 처리 해주는 센스… 항상 생각 하지만 문제는 현실의 요구를 반영하지 않는 것 같다.
#[프로그래머스✈][2019 kakao 겨울 인턴십] 인턴십 호텔 방 배정 문제 해설
설계를 얼마나 잘 할 수 있는지 물어보는 문제인 것 같다. 얼마나 큰 호텔일까 10^12 개의 방을 보유하고 있다면
방 하나를 2 평 이라고 생각만 해도 2000000000000평 이고 대한민국 영토의 약 60배.. 그만하자.