Little Jay

문제를 읽어보면 Minimum Spanning Tree를 구하는 것이라는 것을 파악할 수 있다. MST라고 판단할 수 있는 조건은 다음과 같다 Complete Graph 간선에 weight가 있어야함 문제해결기법 수업 중의 일화인데, DFS 문제를 발표하는 순서가 와서 처음 문제를 풀 때의 사고과정을 설명하던 중 처음 문제 접근을 Prim Algorithm으로 접근해서 풀다가 Prim Algorithm으로 접근했을 때의 output이 문제의 예시 output과 달라 MST를 구하지 않고 DFS로 풀었습니다 라고 발표를 했었다. 그러자 교수님께서 사고의 흐름을 칭찬하셨지만 문제의 조건으로 그래프를 먼저 그려봤다면 MST의 조건에 의해서 Prim은 생각조차 하지 않아도 된다고 하셔서 머쓱했던 적이 있다. 여..

중등교육에서 배운 nCm을 출력하는 문제이다. 하지만 여기서 n이 매우 크다면 그 수는 주체할 수 없을 만큼 커질 것이다. 문제의 예시에서의 100C6만 하더라도 1192052400이 출력된다. 따라서 이를 long long 형태가 아닌 string으로 문제를 해결해야 한다. 그리고 떠오를 수 있는 것은 Paskal의 삼각형이다. Paskal의 삼각형의 점화식은 nCm = n-1Cm-1 + n-1Cm 이다. 따라서 이를 재귀적으로 구해준다면 문제를 해결할 수 있다. #include #define endl '\n' #define ll long long using namespace std; string arr[101][101]; int n, m; string longadd(string a, string b)..

전형적인 DFS문제이다. 그런데 이제 Sorting을 곁들인..... 순서대로 DFS를 수행해주면 되지만 인접리스트로 구현한 그래프를 정렬을 하고 DFS를 수행해줘야 한다. 문제해결기법 13주차 A번 문제와 매우 유사한 문제였던 것 같다. #include #define endl '\n' #define pii pair using namespace std; int t; vector v[100001]; bool visited[100001]; int order[100001]; vector dfs_order; bool cmp(int& a, int& b) { return order[a] < order[b]; } void dfs(int start) { if (visited[start]) return; visited[..

Prefix Sum문제. 문제에서 정확히 뭘 출력하라고 하는지만 파악하면 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int dp[1025][1025]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; int x1, y1, x2, y2; cin >> n >> m; for (int i = 1; i dp[i][j]; for (int i = 1; i y1 >> x2 >> y2; cout

DP가 하도 어려워서 요새 DP를 집중적으로 공부하고 있다. 그 와중에 조금 어이없는(?) 문제를 발견해서 풀이를 올리고자 한다. 위 문제는 어떤 실수 형태의 배열에서 연속되는 구간의 곱의 최대값을 출력하는 문제이다. 이를 간단하게 구성을 construct해보면 어떤 배열이 자기 자신으로 초기화 된 후에, 그 0번 인덱스의 것을 제외하고 1번 인덱스부터 자기 자신과 그 전에 있는 것의 곱의 대소 비교를 통해서 누적곱을 구할 수 있다. 이렇게 업데이트 시켜 주면서 최대값을 찾아주면 정답인데, C++를 하는 사람들은 당연히 setprecision 메서드를 사용했을 것이다. 문제는 이렇게 하면 정답이 아니다. 문제에서 요구한 것은 어떤 값들이 들어와도 소수 3번째 자리수까지 출력하는 것이다. 정수값을 setp..

substring과 map을 활용한 문제 map은 자료를 저장할때 red-black tree 구조로 구현이 되어있기 때문에 자동 정렬이 된다. 이는 int형 뿐만 아니라 string 형태에서도 char에 따라서 정렬을 한다. 'ab' > n; v..

플로이드-와샬 알고리즘으로도 풀 수 있는 문제이지만, 다익스트라가 문제를 보고 떠올랐기에 다익스트라로 풀었다 각 vertex에 대해서 다익스트라를 수행해주고, 수행 후의 distance와 m을 비교해 ans의 max값을 찾아내면 된다. #include #define endl '\n' #define pii pair #define MAX 987654321 using namespace std; int n, m, r; int a, b, l; int items[101]; vector v[101]; int dist[101]; void init() { for (int i = 0; i > n >> m >> r; for (int i = 1; i > items[i]; } for (int i = 0; i < r; i++) ..

트리를 활용한 문제이다. 사실 트리 문제가 나오면 DFS를 활용하는 것이 정배라고는 하지만 이 문제는 단순히 BFS를 통해서 문제를 풀 수 있었다. 1번 Node는 고려하지 않으므로, 1번 Node에서 출반하여 BFS 탐색을 수행하면 문제가 풀린다. 문제는 항상 root node가 1이 아니기 때문에 입력에서 양방향 인접리스트로 받았는데, 이제 visited한 것을 잘 처리해주면 된다. #include #define endl '\n' #define pii pair using namespace std; int n; vector tree[100001]; bool visited[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..

골드문제라 겁먹었지만 Tree개념을 제대로만 알고 있다면 어려운 문제는 아니었다. 먼저 단절점에 대해서 생각을 해보자. 단절점에서 해당 vertex가 삭제가 되었는데, child가 없다면 해당 vertex는 단절점이 아니고, 그래프로 하나로 유지될 것이다. 따라서 해당 vertex의 size가 1 초과라면 당연히 해당 정점은 단절점이 된다. 반면 단절선은 무의미하다. 편향 tree라고 하더라도 간선을 하나 자르면 무조건 그래프는 2개 이상으로 쪼개진다. 이 점을 고려하여 잘 그림만 그려도 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int n, q, t, k; vector tree[100001]; int main() { ios::sync_wit..

Greedy하게 풀 수 있는 문제이다. 아이디어를 한번에 떠올리기가 어려워서 다른분들의 블로그를 참고했다. 사실 아이디어는 여러개가 있었지만 (부분 합 문제 등) 너무 구현이 어려워서 다른 분들의 블로그를 참고했다. 결국 우리가 원하는것은 앞사람과 뒷 사람의 차이(변화량)을 찾는것이다. 따라서 이를 sort시켜서 k-1개 만큼 뽑아내면 된다. #include #define endl '\n' using namespace std; int n, k; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; vector v(n); for (auto& i : v) cin >> i; vector diff(n - 1); for ..