[백준]/C++

https://www.acmicpc.net/problem/15831  #문제 간단 정리 투 포인터 /슬라이딩 윈도우 문제 계속해서 조약돌을 줍다가 검은 조약돌이 초과하게 되면슬라이딩 윈도우를 줄여주면 된다.  #문제 해결 방법 슬라이딩 윈도우를 사용한다고 생각하고 우선 기본적으로 ㅣ , r 두가지의 포인터를 설정하고 오른쪽으로 계속 조약돌을 r++ 하면서 주워주되 while (r b ) { bw[color_map[s[l]]]--; l++; } if (bw[0] = w) { maxlength = max(maxlength, r - l); } } 만약 검은 조약돌의 개수가 원하는 개수보다 늘어나개 된다..

https://www.acmicpc.net/problem/2312   #문제 간단 정리 N을 소인수분해한 결과를 출력  #문제 해결 방법 우선 첫째로 소인수 분해를 하기 위해소수들로 나눠줘야 하는데 그렇기 때문에 1. 소수를 구해야 한다 소수를 구하는 방법은 여러가지 방법이 있지만브루트포스로 1부터 N까지 소수를 구하거나 하면 너무 시간이 오래 걸리니에라토스테네스로 소수를 구해서 소수들만 따로 구해주도록한다. 그렇다면 이제 주어진 수를 소수로 나누고 개수를 카운팅해야된다2. 소수로 나누고 개수를 카운팅해야된다에라토스테네스의 체로 구한 소수들로 계속해서 나눠서 소인수분해한 결과를담는 것은 어렵지 않다. 그런데 만약에 2x2x3 이렇게 되있다면 2가 두번 중복 되기 때문에2 2 이렇게 (숫자) (개수) 로 ..

https://www.acmicpc.net/problem/11721   #문제 간단 정리문자열을 10개 씩 끊어 출력하는 문자열 문제 #문제 해결 방법https://dfdfg42.tistory.com/entry/C-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%9E%90%EB%A5%B4%EA%B8%B0-%EC%B4%9D%EC%A0%95%EB%A6%AC C++ 문자열 자르기 총정리1) substr 함수substr 함수는 문자열의 특정 부분을 잘라내는 데 사용됩니다.기본 사용법cpp #include #include using namespace std;int main() { string s = "0123456789"; string subs1 = s.substr(2, 5); // subs1 = "23..

#문제 간단 정리노골적으로 O(N+M) 가 걸리는 KMP 사용하라는 문제이다  #문제 해결 방법https://dfdfg42.tistory.com/entry/KMP-C-%EC%BD%94%EB%93%9C KMP C++ 코드#include #include #include using namespace std;vector makePI(const string& pattern) { int m = pattern.size(); vector PI(m, 0); int k = 0; for (int i = 1; i 0 && pattern[k] != pattern[i]) k = PI[k - 1]; if (pattern[k] == pattern[i]) k++; PI[i] = k; } returndfdfg42.tistory.com ..

https://www.acmicpc.net/problem/9742  #문제 간단 정리dfs 등 완전탐색으로 순열을 탐색해 해당 순번의 순열을 출력하는 문제   #문제 해결 방법우선 eof 를 확인하는 입출력에 주의 https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-eof-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EB%B2%95> variable과 같은 입력 시도가 먼저 이루어져야 " data-og-host="dfdfg42.tistory.com" data-og-source-url="https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-C-eof-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EB%B2%..

https://www.acmicpc.net/problem/1275  #문제 간단 정리세그먼트 트리 사용일반적인 구간합 문제 #문제 해결 방법세트 코드는https://dfdfg42.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-C-%EC%BD%94%EB%93%9C > 1] = tree[where] + tree[where ^ 1]; where >>= 1; }}int query(int left, int right) { int sum = 0; left += h" data-og-host="dfdfg42.tistory.com" data-og-source-url="https://dfdfg42.tistory.com/entry/%EC%..

https://www.acmicpc.net/problem/27498  #문제 해결 방법크루스칼 알고리즘을 사용하자 기존에 주어진 사랑 성사 관계는 바뀌면 안되기 때문에 Union 함수로 이어주고 MST 를 최대 스패닝 트리로 만들어서 연결되지 않고 남은 사랑 관계들을 최소 값으로 만든다. 키 포인트를 정리하자면1. 이미 연결된 사랑 관계는 스패닝트리에 미리 포함시킨다.2.최대 스패닝 트리로 만들어서 남은 관계들의 값이 최소가 된게 한다. 로 요약 가능하다  #전체 코드 #include #include #include #include using namespace std;const int MAX = 100001;int parent[MAX];int Find(int a) { if (parent[a] == ..

https://www.acmicpc.net/problem/18352  #개요bfs 를 사용해서 거리를 기록한 뒤에같은 거리에 있는 도시들을 벡터에 넣어준 뒤에하나씩 출력하면 된다. #전체 코드#include #include #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M, K, X; cin >> N >> M >> K >> X; vector> graph(N+1); for (int i = 0; i > u >> v; graph[u].push_back(v); } ..

https://www.acmicpc.net/problem/9694  #개요 다익스트라를 활용한 문제라는걸 쉽게 알아 볼 수 있는데 관건은 다익스트라로 알게된 최소비용     + 경로를 기억하는게 관건이다. 이 경로를 기억하는데서 좀 삽질을 했다. #첫번째 코드 - 다익스트라/dfs가지치기 #include #include #include #include #include using namespace std;vector>> nodes;vector dist;vector visited;vector path;vector resultSeq;int N, M;int intimacy;int minIntimacy;void dijkstra(int start) { priority_queue, vector>, greater..

https://www.acmicpc.net/problem/20056  #개요말 그대로 따라가면 정답을 얻을 수 있는 구현문제지만풀기 전에 설계를 정확하게 한 후에 최대한 실수를 적게 하도록 하자.특히 3차원 벡터를 사용하기때문에 실수하기 쉽기 때문에 체감난이도가 조금 더 높게 느껴 질 수 있다. #전체 코드#include #include #include #include #define MAX 52using namespace std;struct fireBall { int y; int x; int mass; int speed; int dir;};int N, M, K;vector mapVec[MAX][MAX];int dx[8] = { 0,1,1,1,0,-1,-1,-1 };int dy[..