✅ 한 것들

---

• 백준
• 지원서 작성
• Frog on Lotus

⚔️ 백준

---

2749 피보나치 수 3

#include"2749.h"
using namespace std;
const int MOD = 1000000;
typedef long long ll;

map<ll, int> dict;

int Fibo_L(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	else return Fibo_L(n - 1) + Fibo_L(n - 2);
}

ll Fibo(ll n)
{
	if (n <= 3) return Fibo_L(n);
	if (dict.count(n)) return dict[n];
	ll res;
	if (n % 2 == 0) // 짝수일 경우
	{
		ll a = Fibo(n / 2) % MOD;
		ll b = Fibo(n / 2 + 1) % MOD;
		ll c = Fibo(n / 2 - 1) % MOD;
		res = a * (b + c) % MOD;
	}
	else // 홀수일 경우
	{
		ll a = Fibo((n + 3) / 2) % MOD;
		ll b = Fibo((n - 1) / 2) % MOD;
		ll c = Fibo((n + 1) / 2) % MOD;
		ll d = Fibo((n - 3) / 2) % MOD;
		res = (a*b + c*d) % MOD;
	}
	dict[n] = res;
	return res;
}


void B2749::Solution()
{
	long long n;
	cin >> n;
	cout << Fibo(n);
}

실수

• n<=3 조건을 <3으로 걸어서 3이면 무한히 안 끝났었음
• 점화식 전개할 때 각각 F_2, F_1으로 놔야 하는데 둘 다 F_1으로 놔버려서 식 잘못 정리됐었음
• 캐싱 도입 안 했더니 계산량이 지수적으로 증가해서 시간 초과.

#include <iostream>
using namespace std;
long long arr[2000001];
int main() {
    arr[0] = 0;
    arr[1] = 1;
    long long N;
    cin>>N;
    N%=1500000;
    for(int i=2;i<=N;i++)
        arr[i]=(arr[i-1]+arr[i-2])%1000000;
    cout<<arr[N];
}

피사노 주기를 이용하면 어처구니 없게 짧게 풀 수 있다. 속도는 약간 더 느리긴 함.

🎮 Frog on Lotus

---

스테이지 기반 기획으로 다시 되돌아감.
1 → 2 → 3 → 4로 커밋이 진행됐다면 4 revert, 3 revert해야 2로 conflict 없이 돌아갈 수 있었다.

시간을 담당하는 TimeManager가 있고,
스테이지를 담당하는 StageManager가 있다.
일정 시간이 지나면 TimeManager에서 StageManager에서 stage를 멈춰야 하고,
stagemanager에서 게임을 다시 시작하려면 timemanager의 시간을 다시 재개하는 작업이 필요하다.
아무리 봐도 순환 참조가 불가피해보이는데, 이를 어떻게 해결하는가?

라고 물어봤더니

1. 이벤트 (Observer) 패턴 : 이벤트 구독으로 해결해라. 결합도 사라짐.
2. 인터페이스로 의존성 역전 : 순환 참조 직접 해결은 아니고 결합도 낮춤
3. 중재자 생성 : GameManager를 만들어서 걔한테 요청 다 보내기. 너무 비대해질수도 있긴 함.

라고는 했는데, 다 구조가 더 복잡해지고 각 tradeoff가 뭔지도 모르겠고 best practice인지도 의심되고 해서 내일 더 리서치해봐야할듯.