백준 2529 - 부등호난이도 : 실버 1 10! 대충 300만언저리쯤의 시간복잡도가 나오는 문제브루트포스로 해결할수 있는 시간복잡도 문제여서 브루트포스로 풀었습니다 정수 연산을 Char로 해석할때는i + '0' 를 해야한다는걸 알게해준 문제였습니다#include #include #include #include using namespace std;int k;bool visited[13];char a[13];vector ret;bool IsValidOper(char a, char b, char op){ if (a b && op == '>') return true; return false;}void Go(int idx, string num){ if (idx == k + 1) { ret.push_back..

트리 순회에는DFS의 전위, 중위, 후위 순회와BFS의 레벨 순회가 있다BFS의 레벨 순회는 우리가 아는 위에서부터 아래로 레벨별 탐색 방식의 일반적인 BFS 순서이다.결과 : 3 6 2 1 4 5 7 DFS의 전위, 중위, 후위 순회의 그래프 탐색 순서는 이와 같다전위 순회 (Preorder)순서 : 루트 -> 왼쪽 -> 오른쪽결과 : 3 6 1 4 2 5 7중위 순회 (Inorder)순서 : 왼쪽 -> 루트 -> 오른쪽결과 : 1 6 4 3 5 2 7후위 순회 (Postorder)순서 : 왼쪽 -> 오른쪽 -> 루트결과 : 1 4 6 5 7 2 3 C++ 구현#include #include using namespace std;vector adj[10];//전위 순회 (루트 -> 왼쪽 -> 오른쪽)v..

백준 3197 - 백조의 호수난이도 : 플래티넘 5 백조이동 BFS + 얼음 녹이기 BFS를 따로 관리하며하루 단위로 번갈아서 실행하는 BFS 방식으로 해결했습니다#include #include #include #include using namespace std;int r, c;const int dy[4] = { -1, 0, 1, 0 };const int dx[4] = { 0, 1, 0, -1 };queue> waterQ, waterTemp, swanQ, swanTemp;int visitedSwan[1504][1504], visited[1504][1504];int y, x, swany, swanx;char a[1504][1504];string s;int day;void Qclear(queue>& q){..

백준 13913 - 숨바꼭질 4 최단거리를 구하고 해당 최단거리의 경로를 역추적해서 출력하면되는문제입니다저번과 다르게 bfs의 최단거리 하나만 구하면되는 쉬운문제였습니다#include #include #include #include using namespace std;int n, k;int visited[100004];int parent[100004];int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; queue q; visited[n] = 1; q.push(n); while (q.size()) { int a = q.front(); q.pop(); //도착시 종료 if (a == k) break; ..

백준 16637 - 괄호 추가하기 해당 문제는 브루트포스 문제이면서 방향성이 있고 사이클이 없는 그래프의 문제입니다 #include #include using namespace std;int n;string s;vector num;vector operStr;int ret = -987654321;int Oper(char c, int operA, int operB){ if (c == '+') return operA + operB; if (c == '-') return operA - operB; if (c == '*') return operA * operB;}//최대값void Go(int idx, int checkNum){ if (idx == num.size() - 1) { ret = max(ret, ..

백준 4179 - 불! 불과 사람이 서로 퍼져나갈때 최단거리를 구하는 문제다가중치가 같으면서 두개의 최단거리를 구하는 문제이기때문에 BFS문제이며다 풀었는데 마지막의 반례를 확인해줘야하는문제라 난이도가 좀 있었던거 같았습니다 .. 생각을 못했었거든요 처음에#include #include #include using namespace std;int n, m;char a[1004][1004];int fireList[1004][1004], personList[1004][1004];int ret;int y, x;int sy, sx;const int dy[4] = { -1, 0, 1, 0 };const int dx[4] = { 0, 1, 0, -1 };int INF = 987654321;bool InMap(int ..

백준 15686 - 치킨배달 해당 문제의 시간복잡도는 O(C(K, M) × H × M)대충 1000만 안팍의 문제이므로 해당문제는 무식하게풀수있으며 백트래킹을 사용하면 풀린다#include #include using namespace std;int n, m;int result = 1e9;int a[54][54];vector> homeList, chickenList;vector> chicken;void Combi(int start, vector v){ if (v.size() == m) { chicken.push_back(v); return; } for (int i = start + 1; i > n >> m; for (int i = 0; i > a[i][j]; if (a[i][j] == 1) h..

완전탐색Brute Force라고 불리며 모든 경우의 수를 탐색하는 알고리즘간단하게 말해 노가다 라고불린다 경우의 수는 단 두가지로 나뉜다순열 (n C r)조합 (n P r)순서와 상관이 있는경우순서와 상관이 없는경우 완전탐색을 사용해야할때?최대 범위로 시간복잡도를 계산했을때 보통 1억 미만이다그러면 BruteForce로 풀면된다사용방식반복문사용재귀함수 사용for문을 사용할 경우#include #include using namespace std;int main(){ vector v = { 1, 2, 3, 4, 5 }; //5라는 원소를 찾을때 for (int i = 0; i while문을 사용할 경우#include #include using namespace std;int main(){ vector v ..

문자열 다루는 문제입니다난이도는 낮은데 처음 봤을때 주춤거렸던 문제입니다for문의 무한루프 방식으로 풀어보았습니다#include #include using namespace std;int n;int main(){ cin >> n; int num = 666; for (;; num++) { if (to_string(num).find("666") != string::npos) n--; if (n == 0) break; } cout

백준 1325 - 효율적인 해킹 해당 문제는 dfs로 풀어서 가장 깊은 뿌리 문제를 구하는 문제이다깊이를 구하는 SudoCode의 예시이다#include #include using namespace std;vector adj[1004];int visited[1004];int DFS(int here){ int ret = 1; for (int i : adj[here]) { if (visited[i]) continue; visited[i] = 1; ret += DFS(i); } return ret;}int main(){ adj[1].push_back(2); adj[1].push_back(3); visited[1] = 1; cout 이를 활용하여 풀었습니다#include #include #inclu..