Approach 본질적으로 위 문제와 접근방법이 완전히 동일하다. https://viyoung.tistory.com/393 [백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생 Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다. 일단 첫번째 시험을 기준으로 오름차순으로 정렬을 viyoung.tistory.com 기본적으로 특정 점에 데헤 차례차례 update하면서 세그먼트 트리에 쿼리를 날리게 되면, 2가지 기준에 대해서 동시에 처리할 수 있는 테크닉에 대해서 잘 알아두도록 하자. 추가적으로 이 문제는 북서풍을 타고 이동하는 것이지만, 북서풍쪽으로 이동할 수 있는 섬을 찾아도 괜찮다. 따라서, x축 기준..

Approach 전체 수의 크기가 65536정도밖에 안되는 상황이므로, k개의 숫자들 중 해당 숫자보다 작은 수의 개수를 질의하는 쿼리를 빠르게 응답해주면 된다. 잘 생각해보면 세그먼트 트리로 쉽게 구할 수 있다는 것을 알 수 있다. 또한 슬라이딩 윈도우 느낌으로 빠지는 부분은 -1, 들어오는 부분은 +1하는 방식으로 update해주면 된다. 추가적으로 위 방식대로 진행하게 되면 0 ~ 특정한 수까지 고려했을 때의 개수가 중앙값 보다 작은 경우와 그렇지 않은 경우가 이분법적으로 갈리게 되므로 이분탐색으로 중앙값을 쉽게 도출할 수 있게 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = ..

Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다. 일단 첫번째 시험을 기준으로 오름차순으로 정렬을 한다. 정렬된 결과에서 앞에 위치하는 학생은 적어도 첫번째 시험을 더 잘 본 것이므로, 해당 학생보다 뒤에 위치하는 학생은 굉장한 학생한 학생을 판단하는 과정에서 고려하지 않아도 된다. 따라서 첫 시험을 기준으로 정렬을 한 뒤, 해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 학생이 없다면 해당 학생은 굉장한 학생이라고 판단해주면 된다. 따라서, 이 문제를 풀기 위해서 실질적으로 해결해야하는 부분은 "해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 사람이 있는지 여부"이다...

Approach 문제를 잘 관찰해보면, 위에서 표현한 2차원 각 공간에 있을 수 있는 물의 높이는 다음과 같은 절차를 거쳐서 결정하게 된다. 1. 외부와 직접적으로 마주하고 있는 공간은 구멍의 높이에 맞춰서 무조건 높이가 형성이 된다. 2. 외부와 직접적으로 마주하고 있는 공간과 직접적으로 구멍이 뚫려있는 경우, 뚫린 구멍의 높이와 외부와 직접적으로 마주하고 있는 공간의 높이값 중 최댓값으로 결정된다. (잘 생각해보면 자명하다.) 3. 2의 과정을 반복함으로써 해당 영역에 위치한 물의 높이를 구할 수 있게 된다. 이때, 물이 계속해서 빠져나가는 상황이므로 넘치게 하는 최소 경계값을 구하는 것과 같고, 이는 다익스트라 문제로 회귀할 수 있게 된다. 최소값을 구해나간다는 점에서 dist를 업데이트하고 pq에..

Approach 문제에서 열어야하는 문의 최솟값을 물어보고 있고, 정점과 정점 사이에 이동할 때 벽의 개수가 가중치라고 생각해보면 최단경로(거리)문제로 치환해서 풀 수 있다는 것을 눈치챌 수 있다. 문제에서 예시로 들어준 것을 잘 분석해보면, 2명의 죄수가 바깥으로 나가기 위한 최단경로와 관련이 있다는 것을 알 수 있다. 하지만, 벽을 중복해서 부술 수 있다는 점 때문에 단순하게 다익스트라로는 위 문제를 쉽게 해결할 수 없게 된다. 추가적으로 문제를 더 고민해보면, 결국 모든 상황에서 상근이가 바깥에서 안으로 들어오는 것과 2명의 죄수가 바깥으로 나가기 위한 최단경로는 한 점에서 만날 수 밖에 없다는 점을 착안하면 결국 3번의 최단거리의 합에서 벽일 경우 중복을 제거하기 위해 2를 빼주면 된다. Code..

Approach 문제를 잘 관찰해보면, 현재 방문했던 주유소 중 주유 비용이 가장 싼 것이 무엇인지를 저장해두는 것이 중요하다는 것을 쉽게 파악할 수 있다. 추가적으로, 현재까지의 주유 비용이 가장 싼 것이 어느 것인지에 따라서 특정 점까지 방문하는데 필요한 비용이 다르므로 DP처럼 차원을 1개 더 잡아줘서 다익스트라를 돌려주면 된다. https://viyoung.tistory.com/380 [백준 10217번] [Dijkstra / DP] KCM Travel Approach 잘 생각해보면, 비용 단위로 최단거리를 구해주면 된다. https://viyoung.tistory.com/369 문제와 유사하다. Code #include #define fastio cin.tie(0)->sync_with_stdio..

Bert에서 모델 경량화를 시킨 모델이라고 생각해주면 된다. 모델 경량화 방법에는 다음과 같은 3가지 방법이 존재한다. 1. Quantization 2. Weight Pruning 3. Knowledge Distilation 위 3가지 중 본 논문은 3번째 방법인 Knowledge Distilation을 활용하여 모델을 경량화 하는 방법을 제안한다. 해당 방식을 사전 학습과 fine-tuning 단계 모두 진쟁하게 된다. 따라서 위 모델은 사전학습을 통해 얻을 수 있는 general domain에 대한 지식과 fine-tuning 단계에서 얻을 수 있는 task-specific한 지식까지 얻을 수 있게 되는 것이다. 위 모델의 핵심적인 내용은 3가지의 loss를 사용했다는 점과, 2단계의 distilla..

Intro ELECTRA를 살펴보기에 앞서, 기존 BERT 모델이 어떤식으로 작동하는지를 recap해보도록 하자. BERT는 기본적으로 트랜스포머의 인코더 부분만 사용한 모델이다. 또한 추가적으로, MLM과 NSP라는 2가지의 사전학습 과정을 거쳐서 해당 모델이 언어를 이해할 수 있게끔 훈련시킨다. 이 중 MLM task의 경우, 다음과 같은 과정을 통해 진행된다. 주어진 corpus를 Tokenizing한다. (Wordpiece tokenizer) 전체 단어의 15% 정도를 무작위로 고르고, 이 중 80%는 MASK 토큰으로 바꾸고, 10%는 임의의 토큰으로 바꾸고, 10%는 아무런 처리를 하지 않는다.(80-10-10 규칙) 3가지의 임베딩 처리를 하고, concat한다.(Token embedding..