서의 공간

[문제]: 2217번: 로프 (acmicpc.net) #include #include using namespace std; int W[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > W[i]; sort(W, W + N); int ret = 0; for (int i = 1; i

재귀호출을 이용하여 \(n\)까지의 합을 계산하는 것보다 더 빠른 합 함수를 알아본다. n까지의 합을 구하는 함수 \(fastSum()\)은 다음과 같이 표현할 수 있다. \begin{align} fastSum(n)&=1+2+\cdots+n\\&=\left(1+2+\cdots+\frac{n}{2}\right)+\left(\left(\frac{n}{2}+1\right)+\cdots+n\right)\\\end{align} 합을 두 부분으로 분리하면, 첫 번째 부분은 \(fastSum\left(\frac{n}{2}\right)\)으로 나타낼 수 있지만, 두 번째 부분은 그럴 수 없다. 다음은 두 번째 부분 식을 어떻게 정리하는지 보여준다. \begin{align} \left(\frac{n}{2}+1\right..

[문제]: 1260번: DFS와 BFS (acmicpc.net) #include #include #include #include #include using namespace std; int N, M, V; vector graph[1002]; bool visBFS[1002]; bool visDFS[1002]; void BFS() { queue q; q.push(V); visBFS[V] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); cout V; for (int i = 0; i > v >> e; graph[v].push_back(e); graph[e].push_back(v); } for (int i = 1; i

#include #include #include using namespace std; vector P; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; P.resize(N + 1); for (int i = 1; i > P[i]; sort(begin(P), end(P)); int ret = 0; int sum = 0; for (int i = 1; i < P.size(); ++i) { sum += P[i]; ret += sum; } cout

#include #include #include #include using namespace std; int 배추밭[52][52]; bool vis[52][52]; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, -1, 0, 1 }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int testCase; cin >> testCase; while (testCase--) { int M, N, K; cin >> M >> N >> K; for (int i = 0; i > X >> Y; 배추밭[X][Y] = 1; } // M: 가..

#include #include #include using namespace std; string operator+(string a, string b) { string ret; int n = 0, carry = 0; reverse(begin(a), end(a)); reverse(begin(b), end(b)); while (a.size() b.size()) b += '0'; for (size_t i = 0; i < a.size(); ++i) { n = ((a[i] - '0') + (b[i] - '0') + carry) % 10; ret += n + '0'; carry = ((a[i] - '0') + (b[i] - '0') + carr..

#include #include using namespace std; bool paper[130][130]; int w = 0, b = 0; void DQ(int y, int x, int size) { bool cur = paper[y][x]; for (int i = y; i < y + size; ++i) { for (int j = x; j < x + size; ++j) { if (paper[i][j] != cur) { DQ(y, x, size / 2); DQ(y + size / 2, x, size / 2); DQ(y, x + size / 2, size / 2); DQ(y + size / 2, x + size / 2, size / 2); return; } } } if (cur == 0) w++; else..

#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); unordered_map hMap; int testCase; cin >> testCase; while (testCase--) { int n; cin >> n; for(int i = 0; i > name >> type; if (hMap.find(type) != end(hMap))// type이 이미 있다면 hMap[type]++; else hMap.insert({ type, 1 }); } int ret = 1;..

1316번: 그룹 단어 체커 (acmicpc.net) #include #include #include using namespace std; // 연속이 끊긴 알파벳이 그 전에 등장했는지의 여부 // 예를 들어 aaabba에서 맨 뒤 a 위치에서 그 앞전에 a가 이미 등장했었는지를 알아야 함 bool presented[26]; bool Check(string& str) { bool ret = true; presented[str[0] - 'a'] = true; char cur = str[0]; for (size_t i = 1; i < str.length(); ++i) { if (cur != str[i]) { if (presented[str[i] - 'a']) {// 이미 등장했었다면 ret = false; ..

2941번: 크로아티아 알파벳 (acmicpc.net) 1. 첫 번째 방법 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 첫 번째 방법 string str; cin >> str; vector strs = { "c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z=" }; for (size_t i = 0; i < strs.size(); ++i) for (size_t pos = str.find(strs[i]); pos != string::npos; pos = str.find(strs[i])..