백트래킹

[LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters

시간 복잡도) O(n * n2) 공간 복잡도) O(n) class Solution { public: int ans = 0; bool isUnique(string s) { set st(s.begin(), s.end()); return (st.size() == s.length()); } // 백트래킹 void solve(vector& arr, int index = 0, string s = "") { if (!isUnique(s)) return; ans = max(ans, (int)s.length()); for (int i = index; i < arr.size(); i++) solve(arr, i + 1, s + arr[i]); } int maxLength(vector& arr) { solve(arr); r..

[LeetCode] 17 - Letter Combinations of a Phone Number

class Solution { map digitComb { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; vector res; string digits; public: void DFS(int i = 0, string curStr = "") { if (curStr.size() == digits.size()) { res.push_back(curStr); return; } for (auto& c : digitComb[digits[i]]) DFS(i + 1, curStr + c); } vector letterCombinations(string digit..

[골4] 1405 - 미친 로봇

#include #include #include using namespace std; using ll = long long; #pragma region 상하좌우 / 위치 const pair dir[] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }, }; #define y first #define x second #pragma endregion #pragma region 빠른 입출력 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion #define SIZE 4 double arrProb[SIZE]; double simple; int n..

[골5] 1759 - 암호 만들기

#include #include #include using namespace std; using ll = long long; #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ vector v; int l, c; void DFS(int now, string str = "", int consonant = 0, int vowel = 0) { char ch = v[now]; str.push_back(ch); if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') vowel++; else consonant++; if (str.length(..

[골5] 24891 - 단어 마방진

#include #include #include #include #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ using namespace std; vector ans(20), s(20); vector vis(20); int l, n; void DFS(int cnt = 0) { if (cnt == l) { bool flag = true; for (int i = 0; i < l; i++) { for (int j = i + 1; j < l; j++) { if (flag) flag = (ans[i][j] == ans[j][i]); } } if (flag) { for (int i = 0; i < ..

[골5] 15686 - 치킨 배달

#include #include #include #include #include using namespace std; using IntPair = pair; #define y first #define x second vector board; vector house, chicken; int m, n, res = 0; bool vis[13]; int distance(IntPair a, IntPair b) { return abs(a.y - b.y) + abs(a.x - b.x); } void DFS(int start = 0, int end = 0) { if (end == m) { int tmpRes = 0; for (int i = 0; i < house.size(); i++) { int dist = INT_M..

[골4] 14502 - 연구소

참고해서 코드 작성 #include #include #include #include #define y first #define x second using namespace std; using IntPair = pair; using TwoDVec = vector; IntPair dir[] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; TwoDVec m, vm; vector vis; int h, w, ans = 0; // 바이러스 지도 초기화 함수 void SetMap() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) vm[i][j] = m[i][j]; } } void SpreadVirus() { queue q;..

[실3] 15650 - n과 m(2)

#include #include using namespace std; #define MAX 9 int n, m; int arr[MAX]{ 0 }; bool visited[MAX]{ 0 }; void dfs(int num, int depth) { if (depth == m) { for (int i = 0; i < m; i++) cout m; dfs(1, 0); }

[실3] 15649 - n과 m(1)

#include using namespace std; #define MAX 9 int n, m; int arr[MAX]{ 0 }; bool visited[MAX]{ 0 }; void dfs(int depth) { if (depth == m) { for (int i = 0; i < m; i++) cout m; dfs(0); }

[실1] 14888 - 연산자 끼워넣기

#include using namespace std; #define OPERATOR_COUNT 4 int n; int arr_operand[1000]; // 수열 int arr_operator[OPERATOR_COUNT]; int min_val = INT_MAX; int max_val = INT_MIN; void DFS(int result, int idx) { if (idx == n) { if (result > max_val) max_val = result; if (result 0) { arr_operator[i]--; ..