분할 정복은 어떤 수의 거듭제곱만을 대상으로 하는 것이 아니다. 오히려 어떤 수의 거듭제곱보다는 행렬을 거듭제곱하는 것을 더욱 많이 볼 수 있다. 선형 점화식으로 주어진 수열일 경우 행렬을 거듭제곱함으로서 손 쉽게, 다이나믹 프로그래밍보다 훨씬 효율적으로, 매우 큰 n에 대하여 값을 구할 수 있다. 그럼 본격적으로 풀이에 돌입해 보자. 지문은 영어 한 줄, 해석 한 줄 번갈아서 표시된다. 문제 In the Fibonacci integer sequence, \(F_0 = 0, F_1 = 1\), and \(F_n = F_{n−1} + F_{n−2}\) for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are: 0, 1, 1, 2, ..

아마 모두의 첫 다이아몬드 티어가 아닐까. 소수 판정법과 소인수분해에 관해서는 거의 마법이나 다름없는 두 가지 알고리즘을 잘 쓰면 된다. 밀러-라빈 소수판정법과 폴라드-로 소인수분해 알고리즘. 작동 방식만 알고 있으면 그리 어렵지 않게 풀 수 있다. 그 작동 방식을 이해하는 것이 최소 다이아몬드라는 것은 잊어 두자. 그럼 본격적으로 풀이에 돌입해 보자. 문제 큰 수를 소인수분해 해보자. 입력 입력은 한 줄로 이루어져 있고, 소인수분해 해야 하는 수가 주어진다. 이 수는 1보다 크고, \(2^{62}\)보다 작다. 예제 입력) 18991325453139 출력 입력으로 주어진 양의 정수를 소인수분해 한 뒤, 모든 인수를 한 줄에 하나씩 증가하는 순서로 출력한다. 예제 출력) 3 3 13 179 271 138..

16563번 문제에서 말한 바 있듯이, 무식하게 전부 나눠 보는 방식인 에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 조금 더 영리하게 계산한 linear seive는 시간복잡도가 \(O(N)\)이다. 이 두 가지 모두 소수를 판정하고 소인수분해하기는 확실하지만, 매우 심각한 하자가 있다. 시간이 너무 오래 걸린다는 것이다. 충분히 빠른 컴퓨터라면 대여섯자리 수가 소수인지 검사하는 것은 그렇게 오래 걸리지 않는다. 하지만 10자리라면? 20자리라면? 4149번 문제에서는 최악의 경우 19자리 수를 계산해야 한다. 영리한 linear seive를 사용하더라도 걸리는 시간이 N에 비례하기 때문에 시간초과가 날 것이다. 이를 정말 빠르게 계산할 수 있는 것이 밀러-라빈 소수판정법과 폴..

소인수분해는 프로그래머들과 뗄려야 뗄 수 없는 관계이다. RSA를 통한 암호와 복호화는 지금도 광범위하게 쓰이고 있고, 따라서 해커들에게는 더 빠른 소인수분해가, 보안 책임자들에게는 더 큰 소수가 필요하다. 범위가 정해진 많은 수의 소인수분해를 빠르게 할 수 있는 방법으로 N 이하의 수로 모두 나눠 보는 무식한 방법인 에라토스테네스의 체가 있다. 그리고 이 글에서 소개할 방법은 그 무식한 방법을 응용한 linear seive이다. 에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 linear seive는 시간복잡도가 \(O(N)\)이라고 한다. 매우 큰 수에 대해서는 둘 다 시간을 많이 잡아먹기는 하겠지만, 5,000,000 정도의 매우 작은 수들에 대해서는 후자가 상당히 효율적이다..

이번 주는 대회가 네 개나 열렸다. 하나는 현 실력 상 참가 자체가 불가한 대회였지만, 그것 빼고는 전부 참가 성공했다. 서강콘은 마스터가 4학기 이내, 챔피언이 전 학년 참가 가능이더라. 챔피언은 단 한 문제도 못 풀었다. Uni-CODE는 A번 문제가 A번의 난이도가 절대 아니었다! 지금도 실버 5로 책정되어 있는데, 오픈 콘테스트 현장에서 풀 때는 그 이상의 난이도로 느껴졌고 지금도 마찬가지다. 아직도 그건 풀지 못했다. 대신 B번 문제는 이미 풀어서 여기에 그 답안까지 공개해 놓았다. 26123번 문제이다. 곰곰컵은... 문제가 귀여웠다. 무슨 소리냐고? 직접 찾아가서 확인해 보면 알 것이다. 카카오톡 이모티콘 홍보 겸 대회를 여는 것이라는 썰이 있는데, 그게 맞는 듯 문제마다 곰곰과 총총이 튀어..

이 문제는 UNIST 대회인 Uni-CODE 2022의 B번 문제이다. 대회 때 완벽하게 풀어 낸 유일한 문제이다. A번은 어떻게 푸는지 감도 못 잡겠더라. 정해가 빨리 공개되면 좋겠다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 N개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 i번째 건물의 높이는 \(h_i\)이다. 윤이는 울산을 파괴하기 위해 다음과 같은 계획을 세웠다. 윤이는 매일 UFO를 타고 울산의 상공을 가르며 가장 높이가 높은 빌딩에 레이저를 발사할 것이다. 레이저에 맞은 빌딩은 높이가 1 낮아진다. 만약 그 날에 가장 높이가 높은 빌딩이 여러 개라면, 해당하는 모든 빌딩에 레이저를 발사한다. 만약 이미 모든 빌딩의 ..