fatalite

문제 문제 난이도 : 실버 2 문제 분류 : BFS (DP) 문제 풀이 #include #include #include #include #include #include using namespace std; int main() { //Input int n = 0; vector Map; cin >> n; for (int i = 0; i > Tmp; Map.push_back(Tmp); } vector Visited(Map.size(), false); queue q; q.push({ 0, 0 }); short MinVal = 10000; while (!q.empty()) { pair p = q.front(); q.pop(); if (Visited[p.first]..

문제 문제 난이도 : 실버 1 문제 분류 : 다이나믹 프로그래밍, 모듈러 연산 성질 문제 풀이 #include #include #include #include using namespace std; int main() { //Input int n = -1; cin >> n; vector DP(n+1, vector(12, 0)); // (Padding) 0 ~ 9 (Padding) //Main Logic DP[1][1] = 0; for (int i = 2; i < 11; i++) { DP[1][i] = 1; } for (int i = 2; i

문제 문제 난이도 : 실버 2 문제 분류 : 다이나믹 프로그래밍 문제 코드 #include #include #include #include using namespace std; vector List; int main() { //Input int n; cin >> n; for (int i = 0; i > Tmp; List.push_back(Tmp); } vector DP(List.size(), 0); //Main Logic Start //Find Sum of N Elements DP[0] = List[0]; int MaxVal = List[0]; for (int i = 1; i < n; ++i) { DP[i] = max(DP[i - 1] + List[i], L..

문제 문제 난이도 : 골드 5 문제 분류 : 백 트래킹, 조합, 시뮬레이션, 구현 문제 풀이 굉장히 기네요.. 똑똑한 여러분은 좀 더 짧게 쓸 수 있을 거라고 생각합니다. #include #include #include #include using namespace std; int L, C; vector Words; vector Selected(16, false); vector SelectedWords; bool IsPromising() { if (SelectedWords.size() == 1) { return true; } char Before = NULL; int A = 0; int B = 0; // 모음 자음 카운팅 if (SelectedWords[0] == 'a' || SelectedWords[0]..

문제 분석 난이도 : 골드 5 문제 : 백 트래킹, 브루트 포스, 구현, 시뮬레이션 깨달은 점 1. unordered_set이나, set 쓰지 말고 그냥 Selected[13]으로 해야 erase 하는데에 O(1)이 된다. 2. 인자 값으로 선택된 것의 인덱스를 넘겨줘서 그 이후만 하도록 해서 시간 복잡도를 줄인다. 문제 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n, m; long long int MinimumCityChickenDistance = INT_MAX; vector City; v..

문제 난이도 : 골드 4 문제 분류 : 백 트래킹 난 바보다!!!!! 해결 방법 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n; int Queen[100]; int Result = 0; void Init() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } bool IsPromise(int Line) { for (int i = 0; i < Line; i++) { if (Queen[i] == Queen[Line] || abs(Queen[i] - Que..

Problem 골드 5 기하학 문제 잘 알려진 문제여서 외적을 사용하면 되는 것을 알고 있지만, 내적을 사용해도 되지 않을까? 라고 생각했다. 그러나 내적을 사용하면, cos 값이 90도 일때와 270(-90)도 일 때 모두 0 이기 때문에 CCW인지 CW인지 판별하기 어렵다는 것을 유추할 수 있다. 따라서 외적을 사용해야한다. 궁금하지만 일단 나중에 알아볼게 있는데 외적과 행렬식의 관계를 알아야할 필요가 있어보인다. Solution #include #include #include #include #include using namespace std; int Cross(pair p1, pair p2) { int ScalarOfOuterVector = p1.first * p2.second - p2.first..

Problem 난이도: 골드 4 분류: 이분 그래프, 그래프, 그래프 탐색 Solution #include #include #include #include using namespace std; int main() { int TestCase; cin >> TestCase; for (int i = 0; i > V >> E; vector AdjList(V+1); for (int k = 0; k > a >> b; AdjList[a].push_back(b); AdjList[b].push_back(a); } set VisitedNode; queue q; vector ParentNode(V + 1); for ..

Problem 레벨 : 골드 5 분류 : 이분 탐색, 두 포인터 접근 : 처음에는 완전 탐색 + 중복 없애기로 했음 방법 : 이분 탐색과 포인터 두 개를 움직인다는 게 중요한 아이디어였다. Solution #include #include #include using namespace std; vector list; pair combination = { 1000000001,10000000001 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; for (int i = 0; i > a; list.push_back(a); } int low = 0..

Problem 티어 실버 1 분류 Dynamic Programming(Bottom-Up) 접근 해결 못했었음 1) 첫 번째로 재귀(순열)로 접근(경우의 수가 기하급수적으로 되어버림), 2) DP 태그 보고 했는데 점화식 어떻게 세워야하는지 몰랐음. 걍 털림.. DP 너무 오랜만이라서 그런가..? 하고 변명을.. 풀이 문제의 구조에서 점화식을 유도 해야했음. 이런 부분이 아직 많이 부족한 것 같다. Solution #include #include using namespace std; int n,t; vector dp; vector tmp; int main() { cin >> t; //Test Case Loop for (int i = 0; i < t; i++) { tmp.clear(); dp.clear();..