단순히 이전 값과 비교하여 다르면 +1을 하는 구조로 풀 수 있다.마지막에는 1을 뒤집는데 드는 비용, 0을 뒤집는데 드는 비용 중 최솟값을 출력하면 된다. #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; int zero_cnt = 0, one_cnt = 0; char before = '\0'; for (char c : s) { if (before != c) { if (c == '0') { zero_cnt++; } else ..

단순한 그리디 문제였다.오름차순으로 둬야 했고, 순서가 안만들어진다는 조건이 없으니, 단순하게 for문을 사용해 풀이하였다.앞 뒤로 1만 차이나면 최소한으로 만들 수 있으니 for문으로도 충분했다. 코드는 아래와 같다. #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector vec; for (int i = 0; i > num; vec.push_back(num); } int result = 0; for (int i = n-2; i ..

위상 정렬 문제이다.똑같이 BFS 문제로 풀려했지만, 메모리 초과 발생으로 인해 다른 방식을 생각해야 했다.걸리는 시간이 최대임에 따라 DP 방식 + 위상 정렬 방식을 사용해 각 노드마다 최대로 걸리는 시간을 담아 쭉 나아가는 방식을 사용했다. 코드는 아래와 같다.#include #include #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; for (int i = 0; i > n >> k; vector> adj(n+1); vector indegree..

위상 정렬 문제로,문제에서 만족하는 순서를 출력하는 문제이다. BFS 풀이는 아래와 같다.#include #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector indegree(n+1, 0); vector> adj(n+1); queue q; for (int i = 0; i > a >> b; indegree[b]++; adj[a].push_back(b); } for (int i = 1; i

위상정렬 문제이다.방향 그래프여야 하고, 사이클이 없어야 한다.그래프 문제와 다른 점은, 문제에 조건에 맞는 순서를 출력하는 점이라고 생각하면 된다. 본인은 BFS 방식으로 풀었다.#include #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector> adj(1001); vector indegree(1001, 0); queue q; vector result; for (int i = 0; i > seq; int prev = 0; for (..

스택을 이용해서 푸는 문제였다. 처음에는 괄호마다 값을 따로 계산해야 한다고 생각했지만,사실은 하나의 cnt 값에 깊이(중첩)에 따라 곱을 누적해주는 방식으로 생각하면 훨씬 쉽게 풀린다. 1. 이전의 값이 괄호 여는 것이었다면 바로 result에 반영 후, cnt를 나누기2. 이전의 값이 괄호 여는 것이 아니라면 cnt만 나누기 구현한 코드는 아래와 같다.#include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); stack stack; long long result = 0; long long cnt = 1; char c; char b..

스택으로 풀었지만, 스택으로 size()를 사용하면 O(n) 시간 복잡도가 사용된다.이에 따라 그냥 int 값으로 저장하면 O(1)로 줄어드니 그게 더 효율적인 것 같다. 효율적인 방법은 후자지만, 막상 시험때는 잘 생각나지 않을 수도..? 스택 풀이법 1#include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); stack stack; int result = 0; char c; char before = '\0'; while(cin.get(c)) { if (c == '(') { stack.push..

덱 내부를 “단조 증가 / 감소” 상태로 유지 가능하다는 특징으로 풀 수 있다.최소값 문제 → 덱을 오름차순(단조 증가) 유지최대값 문제 → 덱을 내림차순(단조 감소) 유지 #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); int n, l; cin >> n >> l; deque> dq; for (int i = 0; i > num; while (!dq.empty() && dq.back().first >= num) { dq.pop_back(); } dq.push_..

#define endl "\n"을 통해서 시간을 줄였다.원래 endl은 줄바꿈 + 버퍼 비우기까지 하므로, 출력 호출이 많을 수록 느려진다. #include #include #define endl "\n"using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; queue q; for (int i = 0; i > s; if (s == "push") { cin >> num; q.push(num); } else if (s == "pop") { if (q.size() >..