Doby's Lab

https://www.acmicpc.net/problem/22990 22990번: 사이클 모든 정점을 포함하고 정점과 간선이 서로 겹치지 않는 단순 사이클의 집합이 존재하는 경우 첫 번째 줄에 1을 출력한다. 그렇지 않으면 0을 출력한다. 모든 정점을 포함하고 정점과 간선이 서로 www.acmicpc.net Solved By: Network Flow, Bipartite Matching, MCMF 단순 사이클이란 시작점과 끝점을 제외한 중복 점이 없는 사이클입니다. 이러한 부분에서 노드를 정점 분할로 두고 생각해야겠다 했지만, '모든 정점을 사용했는가'는 알아낼 수 있는 방법이 떠오르지 않았습니다. 또한, 모든 정점을 사용해야 하지만 모든 정점이 한 사이클에 포함되었는지, 몇 개의 정점이 나뉘어서 단순 사..

https://www.acmicpc.net/problem/9413 9413번: 제주도 관광 제주도는 관광객들이 많이 찾는 도시이다. 제주도에는 교차로가 N개, 일방통행 도로 M개가 있다. 각각의 도로는 한 교차로와 다른 교차로를 연결한다. 한 교차로 쌍을 연결하는 도로의 개수가 여 www.acmicpc.net Solved By: Network Flow, MCMF 네트워크 문제는 항상 어떻게 모델링을 할 지에 대한 아이디어가 중요합니다. 문제를 읽어보며 어떻게 처리할지 하나씩 다루어봅시다. 1. 교차로, 일방통행 도로 - 교차로는 Node, 일방통행 도로는 Directed Edge로 처리하였습니다. 2. 교차로를 공유하면 안 된다. - 노드를 한 번만 지나쳐야 합니다. 정점 분할을 통해 정점 간의 Capa..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net Solved By: DP 4부터 다음과 같은 특징을 발견할 수 있었습니다. 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 2 + 1 + 1 2 + 2 3 + 1 로 4를 표현할 수 있는데 이 중에 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 는 앞에 1을 때고 보면 3을 만드는 방법과 같습니다. 2 + 1 + 1 2 + 2 또한 2를 만드는 방법과 같고, 3 + 1 마지막 또한 1을 만드는 방법과..

https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net Solved By: DP 간단한 점화식으로 구성됩니다. 현재 좌표값이 1일 경우 cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]) + 1 현재 좌표값이 0일 경우 cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]) #include #define MAX 301 using namespace std..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net Solved By: Greedy, Sort 우선 0을 기준으로 양수와 음수를 넘나드는 것은 비효율적이기 때문에 0을 시작점으로 두고 음수에 대해서만 생각해봤습니다. 테스트 케이스 1에서 음수 값들을 모두 절댓값 크기 순대로 정렬하면 {39, 37, 29, 28, 6}과 같은 순으로 나옵니다. M = 2이기 때문에 {39, 37}, {29, 28}, {6}으로 가서 39 * 2 + 29 * 2 + 6 =..

https://www.acmicpc.net/problem/25418 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net Solved By: DP 단순한 BFS로 구할 경우 중복된 값이 많이 들어가 시간 초과가 걸리게 됩니다. 그래서 중복체크를 하기 위해 Memoization 기법을 활용하여 BFS에 DP를 결합했습니다. #include #include #include #define pii pair using namespace std; int n, k; map cache; void bfs(){ queue q; q.push(n); ..

https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net Solved By: DP, Map 문제에서는 점화식이 주어졌으나 N의 범위가 너무 커서 배열로 다루기엔 불가능합니다. 그래서 map을 사용하여 Top-Down DP를 돌려주었습니다. #include #include using namespace std; typedef long long ll; ll N, P, Q; map m; ll solve(ll n){ if(n == 0) return 1; // base case if(m[n] != 0) return m[n]; return m[n] = solve(n / P) + solve(n / Q); } ..

Kaggle에서 제공하는 Learn 플랫폼을 통해 Feature Engineering 공부를 끝냈습니다. 자료가 구글에는 많지 않아 찾고 있었는데 Kaggle에서 제공을 하고 있더군요. (등잔 밑이 어둡다고..) 영어로 되어있어서 막막했는데 언젠가 올렸어야 했던 영어 독해 능력도 조금은 올라간 듯합니다. 그 덕에 모르는 영단어만 100개 넘게 정리했습니다. 코스는 5시간 정도 소요된다고 나와있었는데 저는 영어 때문인지 1~2주 정도 걸렸습니다. 그리고 나중에도 다시 복습하기 위해 블로그에도 정리해두었습니다. [Blog Posts] Mutual Information Creating Features Clustering With K-Means Principal Comonents Analysis Target E..