Approach 라빈-카프 방법으로 접근하였다. 1. 일단 그림의 각 행에 대해서 Rabin fingerprint 해시함수를 활용하여 해싱을 한다. 2. 1에서 구한 해싱값을 이용하여 다시 해싱을 한다. 단, fingerprint_x를 다르게끔 해싱을 한다. 3. 걸작에 대해서도 동일하게 1, 2과정을 반복해준다. 단, 걸작의 크기가 그림의 크기보다 클 수 있으므로 동일한 크기를 기준으로 해싱을 해준다. 4. 믿음과 신뢰를 가지고, 해싱한 값이 같으면 동일한 패턴이 나왔다고 생각해준다 kmp나 야호코라식 등등으로 접근할 수 있다는데, 차후에 다시 풀어보는 것으로.. 라빈-카프 알고리즘에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/22092727216..

Approach 전형적인 KMP문제 KMP 알고리즘에 대해서는 다음 블로그 글을 참고하도록 하자. https://bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했 bowbowbow.tistory.com Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; using tiii = tuple; int move_x[4] = {-1, 1,..

BERT는 다양한 자연어 처리 태스크 분야에서 가장 성능이 뛰어나고, 자연어 처리 분야에서 한 걸음 나아가는데 이바지한 모델이다. 2.1 Basic idea of BERT 기존의 word2vec와 같은 다른 인기있는 모델과 달리, BERT는 단어의 의미를 파악하는 과정에서 문맥을 고려하였다. 그 결과 질문에 대한 대답, 텍스트 생성, 문장 분류 등과 같은 태스크에서 가장 좋은 성능을 도출하여, 자연어 처리 분야에 크게 기여하였다. 단어의 의미를 파악하는 과정에서 문맥을 고려하는지 여부로 모델을 분류하면 다음과 같다. 문맥 독립 모델 (Context-free-model) : word2vec 문맥 기반 모델 (Context-based-model) : BERT 두 개념의 차이를 명확히 이해하기 위해, 다음과 ..

Approach 전형적인 LCA 문제 Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = long long; using pii = pair; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int MAX = 18; vector adj[100001]; int parent[100001][18]; int depth[100001]; bool visited[100001]; void dfs(int cur, int cur_depth){ visited[cur] = 1; depth[cur] = cur_depth; for(auto &p :..

1. 1 트랜스포머 소개 기존의 RNN과 LSTM 네트워크의 경우 순차적 테스크에서 널리 사용되는 편이다. CS231n에서 학습한 것처럼 순차적으로 데이터들이 들어오고 이를 활용한다는 측면에서, 시간에 따른 데이터들의 동향을 예측하기에 유리한 측면이 존재한다. 하지만, 해당 2개의 네트워크는 장기 의존성 문제를 가지고 있다. 장기 의존성 문제란 hidden state를 통해 과거의 정보를 저장할 때 문장의 길이가 길어지면 앞의 과거 정보가 마지막까지 잘 전달되지 못하는 현상을 말한다. 즉, 문장의 길이가 길어지면 길어질수록 앞쪽 부분에 대한 정보를 거의 잊고, 최근에 들어온 정보를 중점적으로 판단하기에 발생하는 문제라고 이해해주면 된다. 또한 이는 Vanishing gradient problem과도 관련..

Approach 정해진 출발점을 기준으로 최단거리가 m보다 작으면 방문할 수 있는 정점이라는 아이디어를 파악했으면 모든 정점을 출발점으로 설정하고, 다익스트라를 통해 최단거리가 m보다 더 작은 모든 정점에 속한 아이템의 수를 다 더해준 뒤 그 중 최댓값을 출력해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 1000000000; //ElogV * V int main() { fastio; i..

Approach 다익스트라를 돌리되, parent 배열을 따로 잡아줘서 역추적해주면 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 200000000; int main() { fastio; int n, m; cin >> n >> m; vector edge[n]; for(int i = 0; i > a >> b >> c; edge[a - 1].pu..

Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long ll; typedef pair pii; typedef tuple tiii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; const int INF = 100000000; int main() { fastio; int t; cin >> t; while(t--){ int n, m, k; cin >> n >> m >> k; vec..