With The Lights Out

시간복잡도에 유의하여 풀이해야 한다. 인덱스 배열을 만들어 해결했다. #include using namespace std;int M;int S[22];int main() { cin.tie(NULL); ios::sync_with_stdio(false); cin >> M; string inputoper; int input; for (int i = 0; i > inputoper; if (inputoper == "add") { cin >> input; if (!S[input]) S[input] = 1; } else if (inputoper == "remove") { ..

백트래킹을 이용해 푸는 문제. 늘상 하던 백트래킹 말고 좋아보이는 방법을 하나 발견할 수 있었는데, 처음에는 N^2 시간복잡도로 풀이하려 했었다. 그 대신 Sum 배열을 선언한 후 합을 미리 구해 놓는 방식이다. 이를 통해 시간복잡도를 획기적으로 줄일 수 있다.원하는 범위(-10 ~ 10) 까지에서 원하는 Depth 까지 순열을 구한다. (1, 1), (2,2) (3,3)  ----  이렇게 i == j 일 때는 무조건 자기 자신을 검사하면 되므로 if ((sign[depth][depth] == '+' && i = 0) || (sign[depth][depth] == '0' && i != 0)) { continue;} 이렇게 복잡도를 줄일 수 있다. 그리고 recur() 함수로 재귀 호출을 하기..

재귀, 백트래킹 을 이용하여 풀이했다.next_permutation을 사용하면 더 빨리 풀 수 있을 것 같다. 시간 복잡도가 다르기 때문에. 범위는 항상 조심하자.  #include #include #include #include using namespace std;int k[12];long long MinNum = 9999999999;long long MaxNum = -1;vector PermuVec;int visited[10] = { false };int N;bool checkCondition(vector inputVec){ for (int i = 0; i PermuVec[i+1]) { return false; } if (k[i] ==..

재귀는 항상 어려운 것 같다. 이해도 이해지만 이 풀이 방식을 기억해 놓는 것도 좋을 것 같다. 다 풀어놓고 실수 한 점은 팀이 3,3 으로 나뉘었을 때 (0,1) (0,2) (1,2) 등등 모든 순서쌍을 고려 해야 하는데 그러지 않았다. 모든 순서쌍을 더할 수 있는 코드로 고치니 풀이에 성공했다. vector find, 조합, 백트래킹, DFS 를 통해 풀이했다.  재귀 풀이#include #include #include using namespace std;int N;int mindiff = 99999999;int arr[20][20];int ans[10];vector v1, v2;int cal(vector v) { int sum = 0; for (int i = 0; i = N / 2) ..

재귀, 백트래킹, 조합, 을 통해 풀이했다.    #include #include #include using namespace std;int L, C;int vowel = 0;int consonant = 0;vector s;char ans[15];void recur(int depth, int next){ if (depth == L) { vowel = 0; consonant = 0; for (int i = 0; i > L >> C; char input; for (int i = 0; i > input; s.push_back(input); } sort(s.begin(), s.end()); recur(0,0); ..

다음 순열을 구하는 문제이다. 처음에는 백트래킹, dfs, 재귀 를 전부 사용해 모든 순열을 찾아가다가 조건에 맞으면 출력하는 방식을 선택하려고 했는데, 범위가 10000 까지이므로 시간 초과가 났다.   #include #include #include #include using namespace std;int N;vector v;vector input_v;bool visited[100001] = {false};bool same = false;void dfs(int input){ if(input == N) { if(same) { for(auto i : v) { cout > N; int tmp; ..

앞의 문제들과 똑같이 풀이를 한다. 그러나 중복되는 수열을 여러 번 출력하면 안된다.  따라서 set 을 사용하여 풀이했다. 처음에는 unordered_set 을 사용해야 하나 하고 생각했었지만 순회를 전부 돌기 때문에 상관이 없다는 것을 이내 깨달았다.  #include #include #include #include using namespace std;vector v;vector input_v(10);set> s;bool visited[10] = { false };int N, M;void dfs(int input){ if (input == M) { s.insert(v); /* for (auto i : v) { cout >..

dfs, 백트래킹, 재귀 를 사용해 푸는 문제이다.DFS - 깊이우선 탐색으로 수열을 제공받는 길이 M 까지 출력하기 위해서 사용하는 알고리즘 백트래킹 - 해를 찾는 도중, 해가 아니어서 막히면 다시 돌아가서 해를 찾는 방법 재귀 - 함수 내에서 자기 자신을 다시 호출하는 함수 처음에 dfs 함수를 0 을 넣어 호출해 1 2, 1 3, 1 4, 2 1 .... 등등 출력할 수 있도록 재귀함수 탈출조건을 명시해준 후 ( 함수 인풋이 M과 같으면 == 수열의 개수가 M개로 채워지면) 탈출 시에는 벡터에 담아두었던 원소를 전부 출력한다. 탈출조건 만족 못할 시에는 순회 하면서 벡터에 넣어주고 dfs(+1) 만큼 재귀호출 해준다.    #include #include #include #include using ..

음... 영양가 하나도 없는 밥을 억지로 우겨넣는 느낌의 문제였다.배열 초기화만 할 줄 알면 쉽게 풀 수 있다.   #include #include using namespace std;int a[1001][1001];int p[501][501];int t[20][4][4] = { { {1,1,1,1}, {0,0,0,0}, {0,0,0,0}, {0,0,0,0} }, { {1,0,0,0}, {1,0,0,0}, {1,0,0,0}, {1,0,0,0} }, { {1,1,0,0}, {1,1,0,0}, {0,0,0,0}, {0,0,0,0} ..

좀 멍청하게 풀었나 해서 다른 사람들의 풀이를 확인 해 보았었는데, 메서드 화 하지 않고 푼 것 말고는 딱히 다른 효율적인 방법이 없었다. 어짜피 브루트 포스로 풀이하는 것이기도 했고, 다음 문제로 넘어가기로 했다.  #include #include #include using namespace std;int N;char a[51][51];int main() { cin >> N; for (int i = 0; i > a[i][j]; } } int max = 0; for (int i = 0; i