Brute force Study

문제 접근탐색을 하면서 현재 구성하고 있는 문자열이 신이 좋아하는 문자열인지를 체크해주면 된다.이 문제의 특징이라면, 지나왔던 칸에 다시 방문할 수 있다는 것. 그리고 비교 대상이 되는 문자열의 길이가 5이하로 매우 짧다는 점이다. 이 문제를 살펴보고 탐색까지 떠올렸으면 BFS? DFS? 를 생각해볼 것이다. 이런 문제에선 현재 구성하고 있는 문자열로 신이 좋아하는 문자열을 만들 수 없는 경우에는 탐색을 멈추고, 아니면 탐색을 계속하도록 DFS를 생각해볼 수 있다.이렇게 접근한다면 구현하려고 생각해본다면 1. 모든 문자열의 substring, 그리고 신이 좋아하는 문자열에 모두 포함되면 되면 count를 증가2. substring에만 속하면 이어서 탐색3. substring에만 속한다면 탐색 종료  하지..

문제 접근만약 Bruete Force한 접근 방식으로 모든 경우를 다 구한다고 하면 O(n!)로 주어진 시간 내에 해결이 불가능하다.어떻게 접근해야 할 지 잘 모르겠지만 분명 매 케이스마다 나머지를 하고 있으면 매우 많은 연산 시간이 필요하다는 것 정도는 알 수 있다. (문자열의 최대 길이가 50이기 때문에 특정 상태에서 나머지를 구할 때 해당 문자열 처음부터 끝까지 나머지를 계산하는 것 또한 매우 비효율적이다.) 따라서 먼저, 각 문자열의 수를 k로 나눈 나머지를 미리 기록해두자int cachestr[16];// 주어진 문자열과 제수(divisor)를 입력받아 나머지를 반환해주는 함수int mod(const string &s, const int divisor) { int result = 0; ..

문제https://www.acmicpc.net/problem/11724   무방향 그래프에서 연결 요소를 찾는 문제틀렸던 부분N개의 노드가 있고, 1개의 간선이 있다고 하자. 그러면 연결 요소는 1개가 아니라 N-2개여야 한다. 즉, 연결되어있지 않은 노드들을 고려하지 않아서 2트한 문제이다. 코드#include using namespace std;bool vis[1002];unordered_set sub;vector adj[1002];void DFS(int start) { vis[start] = 1; sub.erase(start); for (int i = 0; i > n >> m; for (int i = 0; i > s >> e; adj[s].push_back(e); ..

https://www.acmicpc.net/problem/11286   힙을 이용하여 문제를 해결해야 하기 때문에 C++에서 제공하는 priority_queue를 사용할 수 있다.절대값을 기준으로 비교하기 때문에 함수 객체를 만들고, 우선순위 큐의 comparator로 사용하여 문제를 해결하면 된다. comparator의 구체적인 작동방식이 헷갈려서 우선순위 큐에서 비교자의 작동 방식에 대해 적어보겠다. 비교자의 작동 방식비교자의 작동 방식을 더 구체적으로 이해해봅시다.여기서 간주한다는 의미는, 우선순위가 낮다는 의미이다.std::less는 x  true일 때 x가 y보다 작다고 간주합니다. 최대 힙에서 이는 큰 값이 높은 우선순위를 가지게 만듭니다.x가 y보다 작을 때, 작다고 간주하는게 당연하다고 생..

문제https://www.acmicpc.net/problem/25501 시간 초과된 풀이#include using namespace std;int count;int recursion(string s, int l, int r){ ::count++; if(l >= r) return 1; else if(s[l] != s[r]) return 0; else return recursion(s, l+1, r-1);}int isPalindrome(string s){ return recursion(s, 0, s.length() - 1);}int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int ..

문제 https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 잘못 접근하기 좋은 풀이 문제에 나와있는 그대로 모든 원소를 삽입, pop을 해보겠다 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWri..