Intro 이분 탐색 알고리즘은 컴퓨터 공학을 전공하지 않더라도 누구나 교양 시간에 배워봤을 만한 알고리즘입니다. 이분 탐색의 개념 자체는 직관적이지만 응용이 상당히 어렵습니다. 오늘은 이분 탐색과 그 활용에 대해 다뤄보겠습니다. 이분 탐색이란? 이분 탐색이 정확히 무엇일까요? 이분 탐색의 예시로 보통 업-다운 게임을 많이 사용하는데요, 진행자는 $1$부터 $100$까지의 정수 중 하나를 고르고, 질문자는 이 정수를 맞혀야 합니다. 질문자는 매 질문마다 정수를 하나 골라 질문하고, 진행자는 질문자가 고른 정수와 진행자가 고른 정수의 대소관계만을 대답해줍니다....
Intro 등비수열 $a_{n} = ar^{n-1}$의 합은 $$ S_n = \begin{cases} an &\text{if } r=1\ \newline \frac{a(r^n - 1)}{r-1} &\text{otherwise} \end{cases} $$ 로 나타낼 수 있습니다. $r=1$일 때 $S_n$이 다른 이유는, $\frac{a(r^n - 1)}{r-1}$의 분모가 $0$이 되기 때문입니다. 이때는, $1$항부터 $n$항까지가 모두 $a$로 같으니, 간단하게 $an$으로 나타낼 수 있습니다. $n$이 커지면 커질 수록 $S_n$은 (말 그대로) 기하급수적으로 커지기 때문에, 일반적으로 PS에서는 $S_n$을 $m$으로 나눈 나머지를 구하도록 합니다. 따라서, 이 글에서는 등비수열의 합 $S_n\ \textrm{mod}\ m$을 빠르게 구할 방법을 소개하겠습니다....