Approach 위 문제와 본질적으로 거의 비슷하다. https://viyoung.tistory.com/257 [백준 5419번] [세그먼트 트리 / 좌표 압축 / 스위핑] 북서풍 Approach 본질적으로 위 문제와 접근방법이 완전히 동일하다. https://viyoung.tistory.com/393 [백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생 Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개.. viyoung.tistory.com 잘 생각해보면, i번째 위치에 놓인 점이 정렬되기 위해서 움직여야 하는 횟수는 자기보다 앞에 앞에 있는 것 중에 자신보다 큰 것의 개수와 같다. 이렇게 되면, i번째 위치에 놓인 점의 이동 횟수를 구하는 시점에 자신보다 숫자가 큰 것의 개수만..

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

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