아희PS - BOJ 2749 피보나치 수 3(Gold II)

피보나치 수열이란 \(F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2} (n \geq 2) \)을 만족하는 수열이다. PS를 하는 사람들에게는 상당히 익숙한 수열이며, 이를 응용한 문제들도 여럿 있다. 이번 글에서는 아희를 이용하여 피보나치 수열을 구하는 방법에 대해 다루려고 한다. 더 정확히 말하면, 자연수 \(n\)이 주어졌을 때 \(n\)번째 피보나치 수 \(F_n\)을 출력하는 아희 코드를 설명하려고 한다.

 

문제 링크: https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

\(O(N)\) 코드

피보나치 수를 구하는 가장 기본적인 방법은 제 1항부터 제 \(n\)항까지 순서대로 구하는 것이다. 보통 dp를 이용하여 배열에 저장함으로써 계산하지만, 아희의 특성상 배열의 특정 인덱스에 접근하는 시간이 \(O(1)\)이 아니기 때문에, 약간 최적화를 해 주어야 한다. 어차피 피보나치 수열의 특성상 지금까지 계산한 끝의 두 항만 알면 되기 때문에 계산하기가 매우 편해진다. 결국, 알고리즘은 다음 순서대로 작동할 것이다.

1. '아' 스택에 0, 1을 push한다. 이는 각각 \(F_0, F_1\)을 의미한다.
2. '악' 스택에 \(n\)을 입력받는다.
3. '악' 스택의 값을 1 감소시킨다.
4. '악' 스택의 값이 0이라면 '아' 스택의 값을 출력하고 프로그램을 종료한다.
5. '아' 스택에 있는 \(F_{k-1}, F_k\)값을 토대로 \(F_k, F_{k+1}\)값을 계산하여 다시 '아' 스택에 넣는다.
6. 프로그램이 종료될 때까지 3~5를 반복한다.

이 6단계를 구현한 코드는 다음과 같다.

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

그리 길지는 않은 코드이다. 이 코드를 하나하나 살펴보도록 하자.

 

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

강조된 부분은 '아' 스택에 0, 1을 push하는 과정이다. '바'와 '받반타'가 각각 0과 1을 의미한다.

 

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

강조된 부분은 '악' 스택에 \(n\)을 입력받는 과정이다. 정수 하나를 입력받고, 그 정수를 '악' 배열에 옮겨 준다.

 

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

강조된 부분은 '악' 스택의 값을 1 감소시키고(삭받반타타), 감소된 값에 따라 분기(뺘쿠처)되는 부분이다. 개인적으로 '뺘쿠차'라는 형태는 굉장히 많이 사용되는데, 스택 내의 값은 그 개수가 변하지 않으면서 그 값이 0인지 아닌지에 따라 분기가 일어나는 형태이기 때문에, 대부분의 조건 분기는 이런 형태를 사용한다. 여기서도, 스택 내의 값이 0이면 오른쪽으로, 아니면 '쿠'의 아래쪽으로 코드가 진행된다. 먼저 그 값이 0일때를 살펴보자.

 

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

현재 스택에는 \(F_{n-1}, F_n\)이 들어 있는데, \(F_n\)을 출력하고 프로그램을 종료한다. 굳이 '마'가 한 번 더 있는 이유는, 스택을 비운 뒤에 '해'를 호출하기 위해서이다. 즉, 프로그램의 return 값을 0으로 만들기 위해서이다.

 

바받반타방싹삭받반타타뺘쿠처사망마해
ㅋㅋㅋㅋㅋ사포쎠석더썩뻐서

 

뭉뚱그려서 설명하기에는 상당히 많은 일을 하고 있다. 이 부분이 하는 일을 크게 요약하자면 다음과 같다.

1. '아' 스택의 back을 '악' 스택에 복사 - 썩뻐서
2. '아' 스택의 두 값을 더함 - 더
3. '악' 스택의 값을 다시 '아' 스택으로 옮김 - 석쎠
4. '아' 스택의 두 값의 위치를 바꿈 - 사포

이 4단계의 과정을 스택 내의 값에 집중하여 살펴보자. 처음에 '아' 스택에는 \(F_{k-1}, F_k\)가 들어 있다.

1. '악' 스택에 \(F_k\)가 복사된다.
2. '아' 스택의 두 값을 더해 \(F_{k+1}\)이 저장된다.
3. \(F_k\)를 다시 '아' 스택으로 옮긴다.
4. 두 값의 위치를 바꿔 \(F_{k+1}\)이 \(F_k\)보다 뒤에 오도록 한다.

결국, \(F_{k-1}, F_k\)가 들어 있는 스택을 \(F_k, F_{k+1}\)이 들어있는 스택으로 바꾸어 준 것이다. '포' 명령이 끝난 후 다시 위로 올라가서, '악' 스택의 값이 0이 될 때까지 프로그램이 반복된다.

\(O(log N)\) 코드

점화식을 \(O(logN)\)만에 구하려면, 행렬을 이용해야 한다. 피보나치 수열을 구하는 행렬로는 다음이 있다.

$$\begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{bmatrix} (n \in \Bbb N)$$

수학적 귀납법을 이용하여 증명할 수 있으며, 자세한 증명은 생략하겠다.

즉, 행렬 연산이 필요한데, 아희에는 딱히 행렬 연산을 지원하는 도구가 없다. 즉, 행렬 연산을 직접 일일이 해 주어야 한다. 행렬을 \(\begin{bmatrix}a&b\\c&d\end{bmatrix}\)라고 하면, 악-\(a\), 안-\(b\), 앋-\(c\), 알-\(d\)로 저장하면 행렬을 저장할 수 있다.

\(O(log N)\)에 문제를 해결하는 과정은 다음과 같다.

1. \(N\)의 2진법 표현을 구한다.
2. 1에서 구한 2진법 표현을 바탕으로 \(\begin{bmatrix}1&1\\1&0\end{bmatrix}^n\)을 구한다.
3. 2에서 구한 행렬에서 \(F_n\)에 해당하는 값을 출력한다.

과정의 수가 그리 많지는 않지만, 1번 과정은 그렇다 쳐도 2번 과정에 필요한 코드의 길이가 그리 짧진 않다. 우선 답을 구하는 코드는 다음과 같다.

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

코드가 \(O(N)\)코드에 비해 긴데, 위의 과정을 바탕으로 코드를 하나씩 뜯어보자.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

강조된 부분은 전처리 과정으로, 입력을 받고 변수들의 초깃값을 설정하는 부분이다. 각 스택에 들어간 값은 다음과 같다.

아-\(N\)

악-1

안-1

앋-1

알-0

암-1000000

압-0

악~알에서는 행렬이 계산될 것인데, 처음 행렬을 저장한 것이다. 암에 들어간 1000000은 끝 6자리를 구할 것이기 때문에 나머지 연산을 위해 저장된 것이며, 압의 0은 1번 과정을 위해 필요한 변수의 초깃값을 설정한 것이다. 이 0의 쓰임은 이어서 설명할 것이다.

이제 \(N\)의 이진법 표현을 구할 것이다.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

빠반라쌑: 아 스택의 값을 2로 나눈 나머지를 앝 스택에 push한다.

반나: 아 스택의 값을 2로 나눈다.

뺘숩처: 아 스택의 값이 0이면 오른쪽, 아니면 압 스택으로 이동하고 '숩'의 아래쪽으로 진행한다. 만약 0이라면 루프가 끝나고 다음 과정이 진행될 것이다.

더터번벋: 압 스택의 값을 1 증가시킨다. 이 값은 \(N\)의 이진법 표현의 길이가 될 것이다.

소커커커: '소'에서 아 스택으로 이동한다. '커'들은 위치를 맞추기 위한 이동일 뿐이다(아무 기능이 없다).

 

이제 본격적으로 행렬 계산이 시작될 것이다. 나머지 부분이 죄다 이 일을 하고 있기 때문에 한번에 설명하기에는 너무 길고, 우선 전체적인 흐름만을 살펴보자.

 

괴랄한 진행방향

행렬 계산 과정은 다음 경로를 통해 진행된다. 검은색으로 표시한 부분에서 일단 행렬을 제곱한 뒤에, 앝 스택에 있는 값에 따라서 초록색과 파란색으로 분기가 진행된다. 이 값이 0이면 파란색으로, 1이면 초록색으로 간다. 이 분기의 정당성에 대해서 먼저 알아볼 필요가 있을 것 같다.

예를 들어서 만약 \(N=11=1011_{(2)}\)라면, 앝 스택에는 1 1 0 1 순으로, 즉 2진법 표현의 역순이 저장된다. 스택의 back에 있는 1은 필요가 없고, 남은 1 1 0의 역할을 살펴 보자. 편의상 행렬 \(A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)이라고 하면, \(A \rightarrow A^{2 \times 1+0}=A^2 \rightarrow A^{2 \times 2+1}=A^5 \rightarrow A^{2 \times 5 +1}=A^{11}\)의 순서로 계산되는 것이다. 지수를 \(N\)과 같게 맞추는 과정에서, 이 1 1 0이라는 3개의 값이 사용되었다. 즉, \(A\)를 제곱한 뒤에 파란 경로에서는 아무 것도 하지 않고, 초록색 경로에서는 \(A\)를 한 번 더 곱해주는 과정이 진행된다.

마지막으로, 빨간 경로에서 답을 출력하고 프로그램이 종료된다.

 

이제 검은색 부분부터 프로그램의 진행방향을 살펴보자.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

숱

마: 앝 스택의 back에 있는 쓸모 없는 1을 pop한다. 이 1은 이진법 표현에서 처음 등장하는 1이다.

삽뺘쿠처: 만약 압 스택의 값이 0일 경우 답을 출력(산망)하고 프로그램을 종료(해)하며, 아닐 경우 '쿠'의 밑으로 진행된다.

쿠커...커: 아무 역할도 없다.

 

이제 행렬을 제곱할 차례이다. 우선, 행렬의 제곱이 어떻게 표현되는지 살펴보자.

$$\begin{bmatrix}a&b\\c&d\end{bmatrix}^2=\begin{bmatrix}a^2+bc&b(a+d)\\c(a+d)&d^2+bc\end{bmatrix}$$

이것을 알고, 다음 부분을 분석해보자.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

삭빠쌋빠쌋삿따: 앗 스택에 a²을 넣는다.

 

산빠쌋삳빠쌋삿따: 앗 스택에 bc를 넣고 덧셈 연산을 한다. 앗 스택에는 a²+bc가 들어가게 된다.

 

산빠쌋삭빠싹살빠쌋삿다뚜: 앗 스택에 b-a-d 순서로 담은 후, 덧셈과 곱셈을 수행한다. 즉, 앗 스택에 a²+bc 뒤에 b(a+d)가 추가된다.

 

떠더섯썻뻐설썻뻐석썻뻐섣: 앗 스택에 c-a-d 순서로 담은 후, 덧셈과 곱셈을 수행한다. 즉, 앗 스택에 c(a+d)를 추가한다.

 

떠섯썻뻐썻뻐설: 앗 스택에 d²을 추가한다.

 

두떠섯썻뻐섣썻뻐선: 앗 스택에 bc를 추가하고, 덧셈 연산을 한다. 결국 앗 스택에는 d²+bc가 들어간다.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

지금까지 이만큼을 분석했다. 그동안 앗 스택에 상당히 많은 값이 들어갔는데, 이들을 정리하면 다음과 같다.

a²+bc, b(a+d), c(a+d), d²+bc

왼쪽이 front, 오른쪽이 back이다. 이 4개의 값을 보면, 앞에서 설명한 행렬의 제곱과 같다는 것이 보일 것이다.

이제 이 값의 끝 6자리를 다시 악, 안, 앋, 알 스택에 넣어주면 될 것이다.

 

삼빠쌋삿루
ㅋ샬썰퍄켜모

위의 형태가 4개가 이어진다. 다른 부분은 '샬썰'이 샫썯, 샨썬, 샥썩으로 바뀐 것 뿐이다. 이 부분이 하는 일을 살펴보자.

 

삼빠쌋-암 스택의 1000000을 앗 스택으로 옮긴다.

삿루-앗 스택에서 나머지 연산을 수행한다. 이제 앗 스택의 back은 끝 6자리만 남았다.

샬썰퍄켜모-이것을 알 스택으로 옮긴다.

샬썰퍄켜모-알 스택에서 기존에 있던 값을 삭제한다. 새로 들어간 값이 back에 있으므로, 한 번의 swap을 거쳐 기존에 있던 값이 back에 오게 만든 뒤에 pop을 했다.

 

실행 과정과는 별개로, 너무 번잡하지 않은 코드를 만들기 위한 테크닉으로 일명 '1차원 지그재그 테크닉'이라는 것이 존재한다. 루프, 혹은 커서 위치를 조절하기 위해서 갔다가 다시 돌아오는 과정이 필요할 때, 이것을 2줄이 아니라 1줄만에 가능하게 하는 기술이다. 위의 "샬썰퍄켜모"처럼, "+2, ..., +2, -1, -2, ..., -2"의 과정이 반복되면 겹치는 칸 없이 갔다가 다시 오는 과정을 수행할 수 있다.

 

아무튼 같은 과정을 앋, 안, 악 스택에도 반복해서, 행렬을 제곱하는 것은 끝냈다.

 

이제 남은 것은, 홀수 거듭제곱일 때 다시 행렬 \(\begin{bmatrix}1&1\\1&0\end{bmatrix}\)을 곱해 주는 것이다. 이진법 표현은 이미 앝 스택에 저장되었으므로, 다음 부분에서 분기가 발생한다.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

만약 그 값이 0일 경우, 행렬을 추가로 곱해 줄 필요가 없으므로, 아무 것도 하지 않고 그냥 위치만 옮겨 준다.

 

하지만, 그 값이 1이라면 행렬을 곱해주어야 할 것이다.

 

$$\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}1&1\\1&0\end{bmatrix}=\begin{bmatrix}a+b&a\\c+d&d\end{bmatrix}$$

 

이 식을 바탕으로 다음 과정을 수행한다. 편의상 처음에 악, 안, 앋, 알 스택의 값을 a, b, c, d라고 하자.

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

삭빠싼 이후 스택: [악-a][안-a b][앋-c][알-d]

산다 이후 스택: [악-a][안-a+b][앋-c][알-d]

싹삭파쏜 이후 스택: [악-a+b][안-a][앋-c][알-d]

 

방삭받반타빠싼빠싿살바숩
수떠뻐떠떠뻐뻐더벌벌섬버ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ쑬퍼섣
빠반라쌑반나뺘숩처숱투터번벋섭커커커커커커커커커커커커커커쏟
소커커커더터번벋ㅋ마삽뺘쿠처산망해ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코도
쿠커커커커커커커커커커커커ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ코솔
삭빠쌋빠쌋삿따산빠쌋삳빠쌋삿따다산빠쌋삭빠쌋살빠쌋삿다뚜코쏠
두떠섯썻뻐섣썻뻐선떠섯썻뻐썻뻐설떠더섯썻뻐설썻뻐석썻뻐섣코뽀
삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루삼빠쌋삿루샽쿠처카카카카카코솓
ㅋ샬썰퍄켜모샫썯퍄켜모샨썬퍄켜모샥썩퍄켜모삭빠싼산다싹삭파쏜

 

솓/뽀/쏠 이후 스택: [악-a+b][안-a][앋-c][알-d c]

솔/도 이후 스택: [악-a+b][안-a][앋-c][알-c+d]

쏟/섣/퍼/쑬 이후 스택: [악-a+b][안-a][앋-c+d][알-c]

 

이제 행렬은 \(\begin{bmatrix}a+b&b\\c+d&c\end{bmatrix}\)가 되었다. 위의 식과는 형태가 다른데, 이 행렬의 형태 덕분에 이것은 원하는 형태가 된다. 행렬의 값은 피보나치 수열이기 때문에, 다음 두 개의 식이 성립한다.

$$a=c+d, b=c$$

 

결국, 행렬의 곱셈이 반복되면서 피보나치 수열의 n번째 항을 1000000으로 나눈 나머지를 구할 수 있다.

 

<후기>

꽤 전에 짰던 코드인데, 그때 무슨 생각이었을까... 과거의 나는 어떤 멘탈이었길래 이걸 다 짜고 있던거지?