백준 문제 링크 🔍 문제 분석 문제에서 최종 결과는 처음 뽑는 c개의 카드에 따라서 달라진다. 처음 c개에 가장 큰 수의 카드가 포함될 경우 이 경우, 덱에있는 나머지 모든 카드를 뽑고 결과는 마지막으로 뽑은 카드가 된다. 마지막 카드는 가장 큰 수를 제외한 모든 카드가 동등한 확률로 나타난다. ...

백준 문제 링크 🔍 문제 분석 전형적인 LCA알고리즘을 이용하는 문제이다. 설명은 코드로 대신한다. 💻 코드 구현 #include <bits/stdc++.h> #define fastio cin.tie(0)->ios::sync_with_stdio(0) using namespace std; using ll = long lon...

백준 문제 링크 🔍 문제 분석 문제에서는 책을 빌린 날짜 s, 책의 반납기한 e, 책을 읽는 데 걸리는 시간 f가 주어진다. 따라서, 책을 반납해야 하는 기간은 [s + f, e]이다. 책은 하루에 한 권만 반납할 수 있으므로 구간 내에 적절한 지점에서 책을 반납해서 겹치는 지점이 없도록 해야한다. 구간이 여러개 주어지므로 라인 스위핑 알고...

백준 문제 링크 🔍 문제 분석 본 문제는 특정 구간이 주어졌을 때 구간 내에 k이상의 원소의 수를 구하는 문제이다. 만약, 특정 구간이 주어졌을 때 구간 내의 원소가 정렬되어 있다면 이분 탐색을 통해 O(logN)내에 k이상의 원소의 수를 구할 수 있다. 세그먼트 트리의 각 노드가 해당 구간 내의 원소를 정렬한 배열을 나타낸다고 하면, 임의...

백준 문제 링크 🔍 문제 분석 본 문제에서는 성공할 때까지 폭죽을 제작하고 테스트하는 과정을 반복한다. 폭죽의 개수와는 관계없이 현재 시점까지 만들어진 모든 폭죽을 테스트하는데 걸리는 시간은 m이다. 따라서, 매번 num개의 폭죽을 제작하고 테스트한다고 가정한 후 예상 시간을 최소화하는 x를 탐색한다. 테스트의 성공은 확률적으로 결정되므로 ...

백준 문제 링크 🔍 문제 분석 문제의 설명을 읽어보면, 1번 노드에서 출발하여 K번 노드에 이르는 최단 경로를 탐색하는 문제로 이해할 수 있다. 문제에서 주어진 그래프는 모든 노드의 가중치가 1인 유향 그래프이므로, BFS알고리즘을 활용한다면 최단 경로를 쉽게 탐색할 수 있다. 출력은 최단 경로의 길이뿐 아니라, 최단 경로를 구성하는 노...

백준 문제 링크 🔍 문제 분석 대표적인 이분 매칭 문제로 N명 중 최대 K명은 최대 2개의 일을 담당할 수 있다는 차이점이 있다. 본 문제는 다음과 같은 과정으로 풀이한다. 일반적인 이분 매칭을 수행한다. 이분 매칭을 한 번 더 수행하며, 성공한 매칭의 횟수가 K가 되면 종료한다. 💻 코드 구...

🔍 개요 문자열 S에 대하여 S[i:]형태의 문자열들을 문자열 S의 접미사(Suffix)라고 부른다. 따라서, 문자열 S의 길이가 N이라고 한다면, 문자열 S는 서로다른 접미사 N개를 가지게 된다. 이러한 접미사들을 사전 순으로 정렬한 것을 접미사 배열(Suffix Array)이라고 부른다. 접미사 배열을 구하는 가장 쉬운 방법은, 모든 접미사...

백준 문제 링크 🔍 문제 분석 자세한 내용은 접미사 배열(Suffix Array) 및 LCP(Longest Common Prefix)접미사 배열 페이지를 참고한다. 반복되는 부분 문자열은 접미사들의 공통 접두사로 이해할 수 있다. 따라서, LCP 배열을 계산한 뒤 배열의 최댓값을 통해서 반복되는 부분 문자열의 최댓값을 계산할 수 있다....

백준 문제 링크 🔍 문제 분석 분석 수식을 최대로 만드는 괄호를 찾기 위해 완전탐색을 실시한다. 이 때, 동적계획법을 활용하여 시간 복잡도를 낮출 수 있다. 주의해야 할 점은 -연산과 *연산의 경우이다. -연산의 결과가 최대가 되기 위해서는 좌변이 최대가 되고, 우변이 최소가 되어야 한다 *연산의 경우 좌변...