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; ..

보호되어 있는 글입니다.

#include using namespace std;int parent[10001];vector>> edges;// findint find(int x) { if (x == parent[x]) return x; else return parent[x] = find(parent[x]);}// unionvoid merge(int a, int b) { int x = find(a); int y = find(b); if (x == y) return; parent[y] = x; // y -> x}int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int v, e; long long resul..

#include #define MAX 10int parent[MAX];int GetParent(int x) { if (x == parent[x]) return x; return parent[x] = GetParent(parent[x]);}int UnionParent(int a, int b) { a = GetParent(a); b = GetParent(b); if (a  관련 문제https://www.acmicpc.net/problem/1717

문제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); ..

크루스칼 알고리즘그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.시간 복잡도 : O(E log V)주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 프림 알고리즘그래프의 아무 정점부터 시작하여 MST를 구성한다가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다

이 내용에 대해선 앞으로 보완해나갈 예정입니다. 많은 문제를 풀어보면서 최대한 정리해보겠습니다.BFS vs DFSBFSBFS는 시작 정점에서 가까운 정점을 찾는데 적합하다큐를 이용하여 가까운 원소들부터 탐색하기 때문최단 거리 경로를 찾는데 적합하다.BFS에서는 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.BFS는 현재 경계에서 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며, 많은 메모리를 필요로 한다DFSDFS는 대체로 시작 정점에서 멀리 있는 정점을 찾을 때 적합하다.재귀적인 풀이 방식에 적합하다 (후입선출의 스택 구조를 사용하기 때문)백트래킹 방식의 PS 풀이에서 적합하다.모든 경우를 하나 하나 다 탐색해야 하는 경우 적합하다..

1. Terminal에서 다음 명령어를 입력c++ --version   2. InstalledDir에서 bin의 이전 directory로 이동cd /Library/Developer/CommandLineTools/usr/ 위 경로는 사용자 환경에 따라 다를 수 있습니다. cd 명령어 이후 나오는 경로는 1번에서 얻은 경로로 설정하면 됩니다 (3번 과정을 생략하려면 ~~~~/usr/include/로 한 번에 이동하면 됩니다) 3. usr 디렉토리에서 include 디렉토리로 이동cd include 4. include 디렉토리에서 bits 디렉토리 생성mkdir bits 5. bits 디렉토리로 이동cd bits 6. stdc++.h 파일 생성 후 편집기 열기vi stdc++.h또는vim stdc++.h Pe..

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