mononeural synthesis

1. 문제 소개 2. 풀이 Berlekamp-Massey 알고리즘 Berlekamp-Massey 알고리즘Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던koosaga.com Berlekamp-Massey 알고리즘을 사용했다. 위의 글을 읽어보면 친절하게 설명돼 있는데, 한 30% 이해한 것 같다. #include #include #include #include #include using namespace std;const int MOD = 1e9 + 7;using lint = long long;lint ipow(lint x, lin..

1. 문제 소개 2. 생각해야 할 거 키 같으면 볼 수 있음 이런식으로 들어간다 이렇게 생각하면 더 큰 '벽'을 만나기 전 광선이 어디까지 가느냐 묻는 문제라고 해도 본질적으로 같다 (상관은 없지만) 3. 알고리즘 활용 monotone stack을 활용한다.모노톤 스택은 정리가 끝난 후가 아니라 각종 operation을 반복하면서 거기서 발생하는 정보가 유의미하다. 예를 들어서 이 문제에서는 stack안의 원소들을 내림차순(정확히는 non-increasing) 으로 유지하면서, pop 하기 전에 수를 카운트한다. 작은 키는 뒤에서 더 큰 키를 만나면 영원히 가려져서 쓸모 X -> 팝(pop).같은 키는 서로 다 볼 수 있음 -> 키 같은 경우 카운트하고 합쳐서 처리 더 큰 키 가려지지 않아서..

1. BFS, DFS에 대해 BFS의 기본 원리는 아주 간단하다. 그래프의 시작점에서 닿을 수 있는 모든 곳을 탐색하는 것이다. DFS는 이의 반대다. 그래프에서 가능한만큼 깊이 탐색하는 것이다.  [알고리즘-4]그래프 – IREALISM [알고리즘-4]그래프『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다.  본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인irealist.org 두가지 개념을 정확히 이해하고 싶다면 위의 글을 먼저 읽고 오자. BFS의 predecessor subgraph는 이렇게 나타낸다.  \(G_\pi = (V_\pi, E_\pi),\)\(\quad \text{where} \)\(\qu..