결국 오고야 마는 것들

dfs+dp 문제. 파이프 왼쪽 끝을 기준으로 이동할 수 있는지 그리고 끝나는지 확인하는 함수를 만든 뒤 모든 경우의 수를 시도해보면 된다. 가독성이 좋게 짠 것 같아서 기분이 좋다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; bool arr[32][32]; ll cache[32][32][3]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i][j]; } } } // 0 right // 1 down // 2 diag ..

혼내주기 2021. 7. 26. 22:42

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string cache[111][111]; int n, m; void input() { fastio; cin >> n >> m; } string add(string a, string b) { vector v(max(a.size(), b.size())+1); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); for(int i = 0; i < a.size(); ++i) v[i] += a[i]-'0'; for(int i = 0; i < b.size(); ++i) v[i] += b[i]-'0'; string ret ..

혼내주기 2021. 7. 26. 22:42

며칠전에 카카오 2021 여름 인턴십 공고가 올라와서 작년 문제를 실전처럼 시간을 재고 풀어봤다. 결과는 4솔. 5번 문제는 감이 안잡혀서 공식 블로그 해설을 참고해 풀어봤다. 작년엔 서류와 코딩테스트를 함께 평가해서 그런지 3솔하고 붙은 사람도 있고 5문제를 풀고 떨어진 사람도 있는 것 같다. 이번에는 코딩테스트를 붙고 서류를 제출하기 때문에 커트라인이 더 높을테니 5문제면 4~5문제를 풀어야 할 것 같다... 풀이 1번 키패드 누르기 그냥 풀면 된다. 나머지 연산으로 손을 정했는데 0일때를 처리 안해줘서 잠깐 헤맸다. #include #include using namespace std; pair getGrid(int num) { if(num == 0) return make_pair(3, 1); int..

혼내주기 2021. 7. 26. 22:41

다음주 토요일에 있는 2021 카카오 인턴 코딩테스트를 준비하기 위해 2019 카카오 겨울 인턴십 기출문제를 풀어봤다. 2020 카카오 인턴 코테와 마찬가지로 4솔. 풀이 1번 크레인 인형뽑기 게임 엄청 쉬운 문젠데 스택에 넣는 for문에 범위 설정을 잘못해서 1시간 넘게 붙잡고 있었다... 세로칸 하나마다 스택을 만들어서 풀었다. #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; int n = board.size(); stack rows[n]; for(int j = 0; j = 0; --i) { if(boa..

혼내주기 2021. 7. 26. 22:41

t번만큼 미세먼지 확산과 공기청정기 가동을 해주면 된다. 확산에서는 모든 먼지들을 큐에 넣어서 다른 확산되어 날라온 값에 영향을 받지 않도록 했다. 청정은 귀찮지만 그냥 구현하면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; pair purifier; int arr[51][51]; int n, m, t, ans = 0; struct dust { int x, y, value; dust(int a, int b, int c) { x = a, y = b, value = c; } }; void input() { f..

혼내주기 2021. 7. 23. 15:57

문자로 char형 double linked list를 만든 후 폭발 문자열을 발견하면 해당 폭발 문자열을 지우고, 폭발 문자열의 크기만큼 뒤로 돌아가서 다시 탐색한다. 다른 사람들의 풀이를 보니 비슷한 로직을 배열로 구현하면 더 빠르던데, 무지성 가장 빠른 코드로 다시 풀기가 오히려 접근법을 제한하는 것 같아 앞으로는 선택적으로 익히거나 참고만 하려고 한다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; list l; string s, bomb; void input() { fastio; cin >> s >> bomb; } int main() { input(); for(char c : s) { l.push_b..

혼내주기 2021. 7. 23. 15:56

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; const ll MOD = 1e9+7; int m; void input() { fastio; cin >> m; } ll inverse(ll b, int n) { ll ret = 1; while(n) { if(n&1) ret = ret * b % MOD; b = b * b % MOD; n >>= 1; } return ret; } ll fraction(ll a, ll b) { return a * inverse(b, MOD-2) % MOD; } int main() { input(); ll ans = 0; while(m--) { ..

혼내주기 2021. 7. 23. 10:59

세그먼트 트리 공부를 시작했다. 여러 블로그를 참고하면서 bottom-up으로 구현했는데, top-down에 비해 구현은 쉽지만 디버깅할 때 트리 구조를 파악하기가 어려운 것 같다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; const int SZ = 1 n >> m >> k; for(int i = 0; i > tree[SZ + i]; for(int i = SZ-1; i > 0; --i) tree[i] = tree[i >= 1; tree[i] = tree[i > b >> c; if(a == 1) update(b-1, c); else cout

혼내주기 2021. 7. 23. 10:58