fatalite

문제 문제 난이도 : 골드 1 문제 분류: 셰그먼트 트리 문제 리뷰 코드 자체는 알고리즘 코딩 테스트 DO IT 편을 참조하였다. 재귀 셰그먼트 참고 해서 구현 했다가, 안되어서 비재귀 셰그먼트 트리로 구현하였는데 이게 더 나은 것 같다는 생각이.. 재귀 셰그먼트 안되었던게 로직이 이상한게 아니었고, "\n"을 안해줘서 틀렸다고 뜬 거였다.. 문제 소스 코드 #include #include #include #include #include #include #include #include using namespace std; int N,M,K; static vector Tree; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::cout..

문제 문제 난이도 : 실버 1 문제 분류 : 두 포인터 문제 풀이 및 코드 복잡... #include #include #include #include #include #include #include using namespace std; void Init() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int main() { //Initialize Init(); //Input int n, k = 0; cin >> n >> k; vector List; vector Count(100001,0); for (int i = 0; i > Tmp; List.push_back(Tmp); } //M..

문제 문제 난이도: 실버 2 문제 분류: BFS 혹은 DFS 문제 풀이 및 코드 #include #include #include #include #include #include using namespace std; vector Visited; vector Map; int LandNum() { queue q; for (int h = 0; h < Map.size(); ++h) { for (int w = 0; w < Map[h].size(); ++w) { if (Map[h][w] == true) { q.push({ h, w }); } } } int Count = 0; while (!q.empty()) { pair p = q.front(); q.pop(); if (Visited[p.first][p.second]..

문제 문제 난이도 : 실버 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..