알고리즘 (227) 썸네일형 리스트형 백준 16923 - 다음 다양한 단어 https://www.acmicpc.net/problem/16923풀이이 문제는 크게 두 가지의 경우로 나눌 수 있다.알파벳이 모두 들어있지 않은 경우이 경우엔 없는 알파벳 중 가장 작은 알파벳을 맨 뒤에 붙이면 된다.알파벳이 모두 들어있는 경우먼저 zyxwvutsrqponmlkjihgfedcba는 사전순 가장 마지막이기 때문에 사전순으로 오는 다음 문자열이 없다. 이런 경우에만 -1을 출력해 주면 된다. 그렇지 않으면 문자열 $s$에서 가장 마지막으로 $s_{i} 왜 나머지 문자를 지우냐면, 문자열의 사전순 비교는 길이가 작은 게 앞으로 오기 때문이다. 정답 코드 - C++더보기#pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")#pragma GCC o.. 백준 31002 - 그래프 변환 https://www.acmicpc.net/problem/31002 문제에 주어진 변환을 직접 손으로 해보자. 그러면 다음 사실을 발견할 수 있다. 차수를 $deg$이라고 할 때, 첫 변환에서 정점이 될 간선에서 연결된 기존 $G$의 정점으로 하여금 각각 연결된 간선이 $deg - 1$개만큼 존재하여 총 $2(deg - 1)$ 만큼의 간선이 새로 생기고 역시 새로운 차수가 된다. 이때 총 간선의 개수는 악수 정리에 의해 $\frac {VE}{2}$가 된다. 간선이 어떻게 증가하는지 파악했으니 위 계산을 $K$번 반복해주면 답을 구할 수 있다. 정답 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474.. [ICPC] 백준 28152 - Power of Divisors https://www.acmicpc.net/problem/28152힌트 1더보기문제에서 유효한 해가 존재할 때 $f(n)$의 값은 충분히 작다.힌트 2더보기$n^{f(n)} = x$라는 조건에 의해 $x$는 어떤 수의 거듭제곱으로 이루어져야만 함을 확인할 수 있다. 힌트 1과 힌트 2에서 언급한 사실을 종합했을 때, 후보를 빠르게 추릴 수 있는 방법이 있는가?풀이더보기$2^{64} > 10^{18}$이므로, $f(n)$이 가질 수 있는 최댓값을 64로 잡는다. 그러면 1부터 64까지 반복을 돌면서 $1 \leq i \leq 64$에 대해 어떤 정수 $a$가 $a^{i} = x$인지 $a$에 대해 이진탐색을 시행하여 확인할 수 있다. $a^{i} = x$를 만족하는 a를 찾을 경우, $f(a) = i$인지.. 백준 1174 - 줄어드는 수 https://www.acmicpc.net/problem/1174 문제의 조건은 숫자가 줄어들기만 하면 되기 때문에 탐색이 간단한 편임을 눈치챌 수 있다. "9876543210"에서 순서대로 몇 개의 문자를 선택하면 그것이 줄어드는 수이므로 $ 2^{10}$번의 연산으로 모든 경우의 수를 확인할 수 있다. 적당한 방법을 통해 줄어드는 수를 모두 구한 후 답을 출력해 주자. 정답 코드 - C++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")#pragma GCC optimize("O3.. [ICPC] 백준 30484 - Inversions https://www.acmicpc.net/problem/30484힌트더보기각 인덱스에서 알파벳이 몇 개 나오는지 $O(1)$에 계산할 수 있는 방법이 있다.풀이더보기문제에서는 자기보다 뒤에 있는 문자에서 사전 순으로 작은 녀석들의 횟수를 찾아야 한다. 우리는 이를 쉽게 계산하기 위해 각 알파벳 등장 횟수를 suffix 누적합 $suff$로 계산해 저장할 것이다. 그러면 $N - 1$번 만큼의 반복에 대해 사전순으로 작은 알파벳 횟수 $suff[0][character]$를 계산할 수 있고 최초 반복에서는 인덱스 $i$에 대해 $suff[i][character]$를 더하면 최종 답을 구할 수 있다. 정답 코드 - C++1234567891011121314151617181920212223242526272829.. 이전 1 2 3 4 ··· 46 다음