오늘 학습 진행 내용
챌린지반 2일차 : 오토마타와 State Machine
State Machine
신호등과 자판기가 스테이트 머신인 이유?
상태를 가져서(신호, 동전 없음, 동전 있음, 음료수 배출 등)
상태를 변화 시킬 수 있는 입력->트랜지션->출력 구조 형태가 있어야 됨
상태값 활용하는 곳
게임에서는
상호작용 대상(예: 문, 아이템) 같은 입력에 대해서 여러 가지의 상태를 결과로 출력될 수 있음(트랜지션 조건에 따라서)
보스는 같은 공격 함수 처리가 상태(페이즈, 체력) 에 따라서 다른 동작을 하는 형태(Data-Driven)
UI의 메뉴,로딩, 플레잉 이런 부분들도 상태로 나타낼 수 있는 형태
언리얼 엔진에서 대표적으로 쓰이는 곳
Animation Blue Print(ABP) -> State Machine
Behavior Tree -> 행동 기준 처리(안에 존재하는 Task, 조건 평가하는 로직이 상태 기준)
State Tree -> 상태 기준으로 조건 나누어서 처리(GamePlay TAg)
GAS -> GamePlay Tag 기준으로 조건 처리
Software
소프트웨어에서 State 쓰이는 곳
Network Protocol -> 상태 기준으로 처리(TCP,UDP)
컴파일러
게임에서는 State Machine을 많이 쓰고 많은 문제가 발생하는지?
ABP에서 발생할 수 있는 State Machine 없이 구현할 경우 문제
Idle, Jog, Walk, Run 등 다양한 애니메이션 종류에 따라서 각각 조건 변수들이 만들어져야 하고 조건에 따라서 변경 상태값 기준으로 다른 조건 변수들도 계속 업데이트하면서 변하게 됨(비효율적)
오토마타
계산기를 이론화해서 이미지화 혹은 추상적인 모델을 그래프화
오토마타는 많은 이론 별 종류는 다양함
수학적으로 표현해야 컴퓨터로 나타내고 자동화가 가능
종류
유한 오토마타(FA) : 유한한 상태만 저장(정규 표현식, 게임 AI)
푸시다운 오토마타(PDA) : 현재 상태 + 스택 메모리 추가(파서, 컴파일러)
튜링 머신(TM) : 무한(이론상) 테이프 메모리(이론적 계산 모델)
NFA는 게임에 적용할 수 없는 이유?
하나의 입력에 대해서 다른 결과를 도출할 수 있어서
몇개의 결정(트렌지션)이 결정되어 있지 않아서
DFA는 하나의 상태에 대해서 하나의 전환이 무조건 매칭이 되어서
게임에서 사용 가능
스테이트 패턴
상태 패턴은 객체의 내부 상태에 따라 해당 객체가 행동을 변경할 수 있도록 하는 디자인 패턴
OnEnter,OnUpdate,OnExit 이런 식으로 상태 변화 적용
불편한 점도 존재
예시)Idle, Jump, Walk, Fly 등등 상태의 종류가 굉장히 많아졌을 때 하나의 현재 상태값만 가지고 관리는 힘듬
멤버 변수(디커플링)의 상태값 형태로 만들면 해결 가능(여러 종류의 상태값을 동시에 가지는 형태)
상속 형태로 처리해버리면 상태 끼리의 의존성이 커져버리게 됨
HSM(계층형 상태 머신 방식)이라고 부름
여담) 면잡 빈출 질문
class, Struct의 차이가 뭘까요?
기본 접근 제어
struct는 public이 기본 접근, class는 private가 기본 접근
C++ 코딩테스트 공부
TIL: 문자열 나누기 문제로 정리한 Greedy 사고법 & DP 구분 기준
📌 문제 상황 요약
문자열을 앞에서부터 순회하며
첫 글자를 기준 문자로 잡고
기준 문자(eq)와 다른 문자(uneq)의 개수가 같아지는 순간
문자열을 분리하고 카운트하는 문제를 구현하던 중,
eq = 1로 시작해야 하는 이유와
이 문제가 왜 Greedy인지가 헷갈렸다.
1️⃣ eq = 1로 시작해야 하는 이유
❓ 처음 의문
char x = s[i];
int eq = 1; // 왜 1부터 시작하지?
int uneq = 0;
왜 기준 문자를 잡자마자 eq = 1을 주는지 직관이 안 섰다.
✅ 핵심 이유
기준 문자는 이미 문자열에 “포함된 상태”에서 비교를 시작하기 때문
문제 정의를 그대로 풀어보면:
첫 글자를 기준 문자로 잡고
같은 문자 수와 다른 문자 수가 같아지는 순간 분리한다
이 말은 곧:
기준 문자는 이미 1개 사용된 상태
이후 문자들을 보며 균형을 맞춘다는 뜻이다.
그래서 초기 상태는 반드시:
eq = 1; // 기준 문자 x는 이미 하나 존재
uneq = 0; // 아직 다른 문자는 없음
❌ eq = 0으로 시작하면 생기는 문제
기준 문자를 잡아놓고도 카운트에 포함하지 않는 상태
균형 시점이 밀리거나 아예 안 맞음
분리 타이밍이 깨짐
👉 문제 정의와 코드 상태가 불일치
🧠 비유로 이해하기
기준 문자 x는 이미 팀 A 선수 1명이 경기장에 들어온 상태인데
점수판을 0부터 시작하는 것과 같다.
2️⃣ 이 문제의 정석 Greedy 구조
🧩 사고 흐름
문자열의 맨 앞에서 시작
→ 첫 문자를 기준으로 확정
→ 같은 문자 / 다른 문자 누적 카운트
→ 개수가 같아지는 순간 즉시 분리
→ 남은 문자열에 대해 반복
💻 정석 코드 형태
while (i < n) {
char x = s[i];
int eq = 1, uneq = 0;
int j = i + 1;
while (j < n && eq != uneq) {
if (s[j] == x) eq++;
else uneq++;
j++;
}
answer++;
i = j;
}앞에서 결정하면 뒤는 신경 쓸 필요 없음
문자열을 실제로 자르지 않고 인덱스만 이동
조건 만족 즉시 종료
3️⃣ 이 문제를 Greedy로 떠올려야 했던 이유
🔑 문제에서 보이는 Greedy 신호들
“첫 글자를 기준으로”
“같아지는 순간 분리”
“앞에서부터”
“가능한 한 빨리 자른다”
👉 현재 선택이 미래에 영향을 주지 않음
앞에서 어떻게 잘라도
남은 문자열은 똑같은 문제 구조로 남는다.
4️⃣ DP vs Greedy 구분 기준 (문제 읽을 때 체크)
✅ Greedy로 가야 하는 경우
지금 선택해도 남은 문제가 변하지 않는다
되돌릴 필요가 없다
조건 만족 시 즉시 종료한다
미래를 미리 볼 필요가 없다
👉 이 문제는 전부 해당
❌ DP로 가야 하는 경우
지금 선택이 미래 선택 가능성을 바꾼다
이전 결과를 저장해야 한다
“최대 / 최소 / 경우의 수”가 핵심이다
같은 상태가 여러 번 등장한다
📋 실전 체크리스트
문제 읽고 아래를 바로 떠올리자:
☐ 지금 선택이 미래를 바꾸는가?
☐ 되돌아가야 할 가능성이 있는가?
☐ 이전 결과를 저장해야 하는가?
☐ 부분 문제가 서로 의존하는가?
☐ 미래를 미리 봐야 하는가?
YES가 2개 이상 → DP
전부 NO → Greedy
