전체 글

[실3] 10158 - 개미

#include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define x first #define y second int main() { FAST_IO(); int w, h, p, q, t; cin >> w >> h >> p >> q >> t; p += t; q += t; p %= (2 * w); q %= (2 * h); if (p > w) p = 2 * w - p; if (q > h) q = 2 * h - q; cout

[골4] 1715 - 카드 정렬하기

#include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int main() { FAST_IO(); int n, ans = 0; cin >> n; priority_queue pq; if (n == 1) { cout tmp; pq.push(tmp); } while (!pq.empty()) { int sum = 0; sum += pq.top(); pq.pop(); if (!pq.empty()) { sum += pq.top(); pq.pop(); ..

SPFA (Shortest Path Faster Algorithm)

개념) 다익스트라 알고리즘은 O(ElogV)로 동작하며 (이론적으로는 O(E+VlogV) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 O(V3)으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 O(VE)이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다. 이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 O(VE)이지만 실제로는 O(V+E) 정도로 동작한다. 벨만-포드 알고리즘에서는 ..

알고리즘 대회 (Competitive Programming)에서 애드혹(Ad-Hoc) 문제란?

일반적으로 경쟁적 프로그래밍(Competitive Programming) 대회, 이른바 알고리즘 대회에서는 종종 애드혹(ad-hoc) 문제가 출제된다. 일반적으로 애드혹 문제라고 하는 것은 해당 문제를 풀기 위해 잘 알려진 정교한(sophisticated) 알고리즘을 적용하지 않고 해결할 수 있는 유형의 문제를 일컫는다. 이러한 유형의 문제는 손으로 직접 해당 문제를 해결하기 위한 (해당 문제만을 위한) 아이디어를 찾아서 문제를 해결할 수 있다. 애드혹 문제들을 굳이 분류하자면 단순히 지시(instruction)를 따르면 되는 구현 유형이나 그리디 유형 알고리즘 혹은 수학 유형으로 분류할 수 있는 경우가 많다. 즉 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제라고 한다. 안경..

[실3] 16956 - 늑대와 양

농장은 어떻게 출력되든 상관없다. #include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define y first #define x second pair dir[] { {1, 0}, {-1, 0}, {0, -1}, {0, 1} }; int main() { FAST_IO(); int r, c; cin >> r >> c; // 농장 초기화 vector farm(r, vector(c)); queue pos; for (int y = 0; y <..

[골3] 1005 - ACM Craft

#include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; #define MAX 1002 int main() { FAST_IO(); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; int time[MAX]; for (int i = 1; i > time[i]; vector adj[MAX]; queue q; int degree[MAX]{ 0 }; int res[MAX]{ 0 }; while (k-..

[Unity] MVC, MVP, MVVM 디자인 패턴

MVC 패턴 ▶ Model - View - Controller로 각각에 대한 역할을 구분하여 독립적인 기능을 수행하도록 설계하는 디자인 패턴이다. ▣ Model : 어플리케이션에서 사용하는 데이터의 집합이라고 볼 수 있다. ▣ View : 어플리케이션에서 사용자에게 보여지는 화면, UI 이라고 볼 수 있다. ▣ Controller : Model과 View를 이어주는 징검다리의 역할로 사용자는 Controller를 사용하여 Model의 데이터를 수정하게 된다. [ MVC 패턴 ] : MVC 패턴은 Model의 업데이트에 따라 View에 적용이 되야하는 부분에서 서로 간의 의존성이 발생하게 된다. MVP 패턴 ▶ MVC 패턴에서 파생된 디자인 패턴으로 Controller를 대신해 Presenter가 추가되었..

[C++] 문자열 찾기: string.find()

size_t find(const string& str, size_T pos = 0) const; str : 찾고자 하는 문자(열) pos: 찾기 시작하는 주솟값 ​ string.find 함수는 헤더 파일에 정의되어 있으며, 찾고자 하는 문자(열) str을 찾아준다. 그리고 str을 찾으면 해당 문자(열)이 위치한 주솟값을 반환하며, 찾지 못하면 string::npos를 반환한다. 예1. 찾는 문자(열)가 있으면 "Found"를 출력하고, 없으면 "Not found"를 출력한다. #include #include int main(void) { std::string word = "sweet new, sweet new"; std::string str; std::cout > str; int pos = 0; if ..

[골5] 16500 - 문자열 판별

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion int main() { string a[100]; string s; int dp[101]; int n; cin >> s >> n; for (int i = 0; i > a[i]; int sl = s.length(); dp[sl] = 1; for (int i = sl - 1; i >= 0; i--) { for (int j = 0; j

[골3] 1958 - LCS 3

#include #include using namespace std; #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define MAX 101 int dp[MAX][MAX][MAX]; int max(int a, int b, int c) { return max(a, max(b, c)); } int main() { FAST_IO(); string s1, s2, s3; cin >> s1 >> s2 >> s3; int sz1 = s1.length(), sz2 = s2.length(), sz3 = s3.length(); f..