📘 TIL – 피보나치 수
1. 처음 접근: 재귀(Recursion) 방식
피보나치 수열의 정의는 그 자체로 재귀적입니다.
(단, )
처음에는 이 정의를 그대로 코드로 옮겨 깔끔하게 구현하려 했습니다. 하지만 이 방식은 n이 커질수록 치명적인 결함을 보입니다.
2. 재귀 피보나치의 한계: 시간 초과
재귀 방식의 가장 큰 문제는 중복 계산입니다.
위 그림처럼 를 구하기 위해 을 호출하고, 그 안에서 다시 여러 번 가 반복적으로 호출됩니다.
- 시간 복잡도:
- 결과: 이 조금만 커져도 호출 수가 기하급수적으로 폭발하여 코딩 테스트에서 시간 초과가 발생합니다.
3. 해결 방법: 동적 계획법 (DP)
중복 계산을 피하기 위해 "이미 계산한 결과는 저장해두고 재사용하자"는 전략을 사용합니다.
int solution(int n) {
const int MOD = 1234567;
// 계산 결과를 저장할 테이블(배열) 생성
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// 이미 계산된 dp[i-1]과 dp[i-2]를 사용함 (중복 계산 X)
dp[i] = (dp[i-1] + dp[i-2]) % MOD;
}
return dp[n];
}이유: 각 항은 단 한 번만 계산되며, 배열에서 바로 값을 꺼내 쓰기 때문에 연산 횟수가 번에 비례합니다.
시간 복잡도:
4. DP의 핵심: 시간과 공간의 트레이드 오프
"시간을 줄이기 위해 공간을 쓴다."
- 재귀: 시간 소모가 크지만 추가적인 메모리(공간) 사용은 적음.
- DP: 메모리(배열)를 추가로 사용하지만 실행 시간을 획기적으로 단축함.
코딩 테스트에서는 일반적으로 시간 효율성이 훨씬 중요합니다.
5. 공간 최적화: 배열 없이 풀기
피보나치처럼 직전 두 개의 값만 필요한 경우, 굳이 크기 의 배열을 만들지 않아도 됩니다.
int solution(int n) {
const int MOD = 1234567;
if (n == 0) return 0;
int a = 0; // F(n-2) 역할
int b = 1; // F(n-1) 역할
for (int i = 2; i <= n; i++) {
int c = (a + b) % MOD; // 현재 값 계산
a = b; // 값 밀어내기
b = c;
}
return b;
}시간 복잡도: 공간 복잡도: (변수 몇 개만 사용)
6. 재귀와 DP, 언제 사용해야 할까?
✅ 재귀가 효율적인 경우
- 각 호출이 독립적이고 중복 계산이 없는 경우.
- 트리/그래프 DFS, 백트래킹(순열, 조합), 분할 정복(Merge Sort 등).
❌ 재귀를 피해야 하는 경우 - 같은 계산이 반복되는 점화식 문제.
- 재귀 깊이가 시스템 스택 제한을 넘길 정도로 큰 경우.
7. 결론: 문제 풀기 전 스스로 던질 질문
코드 작성 전 다음 3가지를 체크하면 풀이 방향이 보임.
- 같은 계산을 여러 번 하게 되는가? (Yes → 재귀 피하기)
- 작은 문제의 결과를 저장해서 쓸 수 있는가? (Yes → DP 고려)
- 이전 몇 개의 값만으로 다음 값을 구할 수 있는가? (Yes → 공간 최적화 가능)
📘 TIL – Unreal Engine 몬스터 AI 시스템 설계: Behavior Tree & Blackboard 구조화
1. 몬스터 시스템 전체 구조 설계
단순히 플레이어를 추적하는 AI가 아니라, 목적 지향적인 AI를 구축하는 것을 목표로 했습니다.
- 설계 목표: 몬스터는 무조건 플레이어를 쫓지 않으며, 최종 목표인 창고(Warehouse)를 우선시합니다.
- 공격 판단: 플레이어나 바리케이드가 경로를 직접적으로 방해할 때만 공격을 수행하여 불필요한 어그로 쏠림(Kiting)을 방지합니다.
- 설계 핵심: 모든 판단 기준을 Blackboard 중심으로 설계하여 코드 상의 분기문을 최소화했습니다.
2. Monster 데이터 구조 분리 (Rank / Type)
확장성을 위해 "강함"을 나타내는 Rank와 "행동 양식"을 나타내는 Type을 완전히 분리했습니다.
| 구분 | 항목 | 내용 |
|---|---|---|
| Rank (강함) | Normal, Elite, Boss | HP, 이동속도, 데미지 배율, 특수 패턴 여부 |
| Type (종류) | Zombie, Bomber, Sniper | 공격력, 사거리, 이동 보정, BT Override 가능 |
Data Management:
RankPresetTable과TypePresetTable이라는 별도의 DataTable로 관리하여 데이터 에셋만 수정하면 새로운 몬스터를 쉽게 생성할 수 있습니다.
3. Monster C++ 핵심 구조
몬스터 클래스에서 상황에 맞는 Behavior Tree를 유연하게 선택할 수 있도록 구현했습니다.
// Monster.h
/** 몬스터가 실행할 최종 Behavior Tree를 결정하여 반환 */
UBehaviorTree* GetBehaviorTreeToRun() const;
// Monster.cpp
UBehaviorTree* AMonster::GetBehaviorTreeToRun() const
{
// 1. TypePreset에서 특정 종류별로 덮어쓴 BT가 있다면 그것을 우선 반환 (ResolvedBehaviorTree)
// 2. 특별한 설정이 없다면 BP 자식 클래스에서 설정한 기본 BT 반환 (DefaultBehaviorTree)
return ResolvedBehaviorTree ? ResolvedBehaviorTree : DefaultBehaviorTree;
}4. AIController의 역할 정의
AIController는 무거운 로직을 담지 않고 오직 실행자(Executor)의 역할만 수행.
AIController의 책임:
- Monster 객체로부터 실행할 BT를 수신하여 실행.
- Blackboard 초기 변수(Warehouse, Dead 여부 등) 세팅.
- 판단 로직은 Monster와 Blackboard에 맡기고 자신은 실행만 담당.
C++// AIController 실행부 예시
void AMonsterAIController::OnPossess(APawn* InPawn)
{
Super::OnPossess(InPawn);
if (AMonster* Monster = Cast<AMonster>(InPawn))
{
UBehaviorTree* BT = Monster->GetBehaviorTreeToRun();
if (BT)
{
RunBehaviorTree(BT);
}
}
}5. Blackboard: AI의 공유 메모리
Blackboard는 AI가 현재 상태를 파악하고 판단하는 '기준표' 역할을 합니다.
| 키 이름 | 용도 |
|---|---|
| WarehouseActor | 최종 이동 목표 지점 |
| CurrentTarget | 경로를 막고 있어 제거해야 할 공격 대상 |
| bIsDead | 사망 여부 (BT 즉시 중단 및 전이용) |
| SpecialLogic | 엘리트/보스 몬스터의 특수 패턴 분기용 데이터 |
6. Behavior Tree의 역할 분담
Behavior Tree의 각 노드는 명확한 역할 분담을 가집니다.
- Decorator (조건): "행동 여부 판단" (예: bIsDead가 true인가?)
- Task (실행): "실제 행동 수행" (예: MoveTo, Attack)
- Service (감시): "상태 주기적 업데이트" (예: Monster 상태를 읽어 BB에 반영)
7. 최종 Behavior Tree 흐름 시각화
Selector 노드를 활용하여 우선순위에 따른 흐름을 구성했습니다.
Plaintext[Root]
└─ Selector
├─ Death (1순위)
│ └─ (Decorator: bIsDead == true) → Task: Die
│
├─ SpecialAttack (2순위)
│ └─ (Decorator: SpecialLogic != 0) → Task: SpecialAttack
│
├─ Attack (3순위)
│ └─ (Decorator: CurrentTarget IsSet) → Task: Attack
│
└─ Move (기본 행동)
├─ Service: UpdateMonsterState (상태 감시 및 BB 동기화)
├─ Task: CheckPathObstacles (경로 장애물 체크)
└─ Task: MoveTo(WarehouseActor)8. 오늘의 핵심 인사이트
- BT는 로직이 아니라 흐름이다: 코드 레벨의 복잡한 if문을 BT의 우선순위 구조로 시각화하여 설계해야 한다.
- 판단 기준의 데이터화: 모든 AI 판단 근거는 Blackboard에 있어야 외부에서도 제어가 용이하다.
- 경량화된 Controller: AIController는 최대한 '멍청하게' 유지하고 실행에만 집중하게 하는 것이 유지보수에 유리하다.
- Default + Override 구조: 기본적인 지능을 갖추되 데이터 테이블을 통해 특정 타입만 지능을 교체하는 방식은 확장성이 압도적으로 높다.
