본문 바로가기

Problem Solving

 (98)
백준 20922번 겹치는 건 싫어 문제 요약 길이 $N$인 수열 $a$와 $K$가 주어진다. 연속 부분수열 중에서 같은 정수가 $K$개 이하로 포함되는 최장 연속 부분 수열의 길이를 출력하시오. N은 최대 20만, K는 최대 100, 주어지는 수들의 범위는 1부터 10만까지이다. 풀이 연속 부분 수열이기 때문에 투포인터를 사용할 수 있다. 현재 보고 있는 수열의 범위를 $[s,e)$라고 하자. 만약 e번째 수의 등장횟수가 이미 K번이라면 s를 오른쪽으로 옮기면서 현재 보고 있는 부분 수열의 길이를 줄여나간다. 그러다가 e번째 수의 등장횟수가 K보자 작아졌다면 s를 오른쪽으로 옮기는 것을 그만두고 다시 e를 늘련간다. 이렇게 하면 답을 찾을 수 있다. #include using namespace std; int N, K; int cnt[1..
백준 20921번 그렇고 그런 사이 문제 요약 정수 N, K가 주어진다. 1부터 N까지를 한 번씩 사용해서 inversion이 정확히 K개인 배열을 출력하시오. 여기서 inversion이란 배열을 $a$라고 했을 때, $ia_j$인 $(i,j)$를 말한다. 이러한 $(i,j)$가 $K$개인 배열 $a$를 출력하자. N은 최대 4242고 K는 0부터 $N(N-1)/2$이다. 풀이 일단 문제불가능한 경우는 없다고 제시했다. 그래고 한 번 왜 가능한지 생각해보자. $a_i$가 만들 수 있는 inversion의 수는 N-i개이다. 이를 통해 0부터 N-1까지를 사용해서 그 합을 K로 만드는 것과 같다고 생각할 수 있다. K가 0부터 N-1 사이일 때는 숫자 하나만 사용하면 된다. N부터 2N-3까지는 N-1하나랑 남은 수 중에서 하나를 선택하고,..
백준 20920번 영단어 암기는 괴로워 문제 요약 문자열이 N개가 주어진다. 문자열 중에서 길이 M보다 작은 문자열은 무시한다. 이 문자열들을 아래와 같은 기준으로 정렬해서 출력하시오. 등장 빈도 수가 더 많은 문자열을 앞에 배치한다. 등장 빈도 수가 같다면 길이가 긴 문자열을 앞에 배치한다. 빈도 수도 같고 길이도 같다면 사전 순으로 앞선 문자열을 앞에 배치한다. N은 최대 10만이고, M은 최대 10이다. 주어지는 문자열들은 길이 10으넘지 않는다. 풀이 문자열을 입력 받으면서 길이가 M 이상인 문자열들만 map을 이용해서 빈도수를 저장하자. 각 문자열들을 한 번씩만 등장하게 벡터에 저장하고 이 벡터를 주어진 조건에 따라서 정렬하면 된다. 정렬 기준은 함수나 람다 함수를 이용하면 편하다. 지금 보니까 944ms로 아슬아슬하다... #inc..
백준 7149번 Can of Worms 문제 요약 직선 상에 캔이 n개 놓여있다. 캔은 터질 수 있다. 각 캔이 놓여있는 위치 $x_i$와 캔이 터지는 반경 $r_i$가 주어진다. 캔이 터질 때, 터지는 반경 내에 있는 캔은 모두 연쇄적으로 터지게 된다. j번째 캔이 i번째 캔의 반경 내에 있으면 j번째 캔도 터지고 j번째 지뢰의 반경 내에 있는 캔은 모두 같이 터진다. 이 때, $i$번째 캔이 터졌을 때 같이 터지게 되는 캔의 수를 모두 출력하라. $n \le 10^9$, $1 \le x_i, r_i \le 10^9$이다. 풀이 이 문제를 그래프로 생각해보자. 그러면, $i$번째 캔의 반경 내에 존재하는 모든 캔들에 대해서 간선을 연결해주자. 그렇게 만든 그래프에서 DFS를 돌리면 문제가 해결이 가능하다. 그러나, 간선 수가 $O(N^2)$..
백준 1892번 가위바위보 문제 요약 두 사람이 가위바위보를 하는데 총 N번까지 진행할 때, 먼저 K번 이길 확률이다. K와 N의 범위는 최대 40이다. 풀이 먼저, K가 1일 때를 생각해보자. 한 번이라도 게임의 승패가 결정나면 그 순간 끝난다. 그렇기 때문에, 최대 N번까지 진행하기 위해서는 N-1번 연속으로 내리 비기다가, N번째에 이겨야 한다. 게임이 K번보다 많이 진행되기 위해서는 내가 지기도 하고, 비기기도 해야 가능하다는 것이다. 일단, $i$번 째 라운드에서 K번 이길 확률을 $f(i)$라고 하자. $i$번째까지 진행되면서 내가 질 수 있는 최대 횟수는 K-1번이다. 그리고 $i-1$번의 게임 중에서 $K-1$번을 이겼어야 하며, $i$번째 게임에서 이기는 것이다. 이를 식으로 나타내자 $$ f(i) = \frac{..
백준 14858번 GCD 테이블과 연속 부분 수열 문제 요약 $G[i][j]$에 $GCD(i,j)$가 저장되어 있는 크기 $N \times M$의 배열이 있다. 길이 $k$인 수열 $a_1, a_2, ... a_k$가 주어졌을 때, 배열 G에서 연속한 부분 수열들 중에서 $a_1, a_2, ... , a_k$가 존재하는지 아닌지를 구해야 한다. 조건은 $1 \le N,M \le 10^{12}, \; 1 \le i \le N, \; 1 \le j \le M, \; 1 \le k \le 10000$이다. 문제 풀이 일단 첨자표시가 마크다운에선 좀 쓰기 힘드니 $G[i][j]$대신 $G(i,j)$로 쓰겠다. 문제를 다시 적어보자면, $1 \le l \le k$인 $l$에 대하여 $G(x,y+l) = a_l$인 $(x,y)$를 찾는 것이라고 생각하면 된다. 여..
중국인의 나머지 정리 설명(Chinese Remainder Therem, CRT) 중국인의 나머지 정리(Chinese Remainder Theorem) 2020.04.23 코드가 잘못된 것을 확인했습니다. 앳코더 라이브러리판 crt는 맞는데 제 꺼는 틀렸습니다. 확인하고 수정하겠습니다. 2020.04.27 제가 착각했습니다. 틀린 줄 알았는데 제가 코드를 옮길 때 정확히 옮기지 않았네요. 블로그 상에 올라와 있는 코드는 전부 int인데 long long으로 옮기다가 잘못 옮겼습니다. 포스트의 코드도 long long 버전으로 바꾸겠습니다. $$ \begin{aligned} x \equiv &a_1 \; (mod \; m_1) \\ x \equiv &a_2 \; (mod \; m_2) \\ &\vdots \\ x \equiv &a_k \; (mod \; m_k) \end{aligned}..
모듈러 역원 설명(Modular Inverse) 이 글은 확장 유클리드 알고리즘을 안다는 전제 하에 작성했습니다. 확장 유클리드 알고리즘은 여기에 설명했습니다. 나머지 연산 나머지 연산이란 정수끼리 연산을 할 때, 그 결과로 항상 어떤 수 $N$에 대하여 나머지를 취하는 연산을 말한다. 모듈러 연산이라고도 하며 나머지 연산 상에서 같다는 것을 표기할 때는 작대기 세개짜리 등호를 쓴다($\equiv$) . 어찌 됐든 이 모듈러 연산을 할 때, 덧셈과 곱셈, 뺄셈은 일반적인 정수의 사칙연산과 별 차이가 없다. 하지만 나눗셈의 경우 일단 원래 하던 방식으로 가능한지부터 의문이 든다. 모듈러 나눗셈을 하기 위해서는 역원이라는 개념을 알아야 한다. 어떤 수로 모듈러 나눗셈을 하고자 할 때, 그 수의 곱셈에 대한 역원을 찾고 그 역원을 곱해주는 것으로 나눗셈을 ..

티스토리툴바