A. Casimir's String Solitaire - 수학 문제 - 주어진 문자열에서 아래의 두 연산중 하나를 수행한다. 임의의 A 와 B를 제거 임의의 B 와 C를 제거 - 이때 문자열을 ""로 만들 수 있으면 YES , 아니면 NO를 출력하는 문제이다. - 해결방법은 간단하다. - 문자열에서 ABC 각각의 개수를 세고 A + C = B 가 성립하면 ""로 만들 수 있다. 반성 - 주어진 입력의 크기를 보지 못하고 완전탐색으로 모든 경우의 수를 구하여 풀려고 했다. #include #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(..

1. 문제 https://www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 2. 풀이 늦는 시간 T 동안 주어진 그래프에서 이동할 수 있는 길의 경우의 수 구하는 문제. 가중치가 1인 인접 행렬 그래프를 n번 제곱하면 (가중치가 없는) mat[i][j]의 값은 i 에서 j 로가는 경로중 n개의 간선이 있는 경로의 경우의 수 와같다. 따라서 주어진 그래프를 가중치가 1 인 인접행렬 그래프로 변환하고 T 제곱 하면 간선의 개수가 T인 ..

1. 문제 4206번: 피보나치 단어 (acmicpc.net) 2. 간단 풀이 이 문제는 입력의 크기를 제외하면 단순하다. fib[i] = fib[i-1] + fib[i-2] + mid 이 공식을 사용하여 중간에 걸친부분을 조사하여 새로운 패턴이 생기는지 확인만하면된다. 하지만 long long 타입의 크기의 문자열을 처리해야한다는것. 이를 그대로 처리하게되면 당연히 시간 초과 메모리 초과가 일어날것은 뻔하다. 그러므로 피보나치의 성질을 활용하여 다루는 문자열의 크기를 제한하고, kmp알고리즘을 사용하여 효율적으로 처리해야한다. 3. 풀이 피보나치 문자열이 일단 패턴보다 길어야 패턴이 보인다는것은 자명하다. 길이가 같거나 더 긴 첫번째 피보나치 문자열을 first 라고하고 다음 문자열을 second라하자..

1. 문제 11400번: 단절선 (acmicpc.net) 2. 풀이 [백준] [C++] 11266번 단절점 (dfs) (tistory.com) 단절점 문제와 유사하다. dfs 스패닝 트리에서 부모 노드 - 자손 노드 의 간선을 조사할때 자손이 루트인 서브트리에서 부모로 가는 간선을 제외한 역방향 간선을 조사. 만약 서브트리에서 역방향간선이 전부 부모노드를 거슬러 올라가지 못할 경우. 부모노드 -> 자손 노드 의 간선이 단절선이되어 이 선을 제거하면 컴포넌트가 분리된다. 부모 노드로 가는 간선을 제외해야하는 이유 = 자손 노드의 자손들이 이 부모노드와 연결될경우, 현재 부모 - 자손 노드의 간선은 단절선이 될 수 없음. = 만약 부모노드로 가는 간선을 무시안할 경우 최소는 항상 부모노드와 같거나 작은값을 ..

1. 문제 단절점이란 한 노드와 인접한간선들을 모두 지웠을 때 해당 컴포넌트가 두개 이상으로 나뉘어지는 정점이다. 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 2. 무향 그래프 단절점 찾기 : dfs dfs 스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다. 그 중 단절점 찾기에서 중요한 간선은 역방향 간선으로, 자손 노드에서 선조 노드로 연결된 간선이다. 한 노드의 자손노드들이 모두 이런 역방향 간선을 통해 그 노드..

1. 문제 1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 2. 풀이 이 문제는 주어진 입력을 트리로 표현하고 모든 노드를 루트까지 거리를 구해 주어진 질의 a , b 에 대하여 다음을 답해야한다. depth(a) + depth(b) - 2depth(lca) (이 식은 구간합과 유사한 형태로, 증명또한 비슷하게 할 수 있다.) 3. 트리 재구성 : 구간트리 LCA는 최소 공통 조상이다. 특정 구간이 주어질때 그에 대해 질의를 답해줄 수 있는 구간 트..