싱글톤 패턴 싱글톤 패턴이란 프로그램 내에 단 하나의 인스턴스만 존재하도록 하는 디자인 패턴이다. GoF에 따르면 싱글톤 패턴은 클래스가 자체의 인스턴스 하나만을 인스턴스화 하도록 보장하며, 해당하는 하나의 인스턴스에 대한 글로벌 액세스를 제공한다고 한다. 즉, 전체 씬에서 행동을 조정하는 오브젝트가 정확히 하나만 필요할 때 유용한 패턴이다. 메인 게임 루프를 관리하는 매니저가 딱 하나만 필요하다거나, 한 번에 하나의 파일 관리자만 파일 시스템에 작성하기를 원하는 경우가 그 예시이다. 이러한 관리자 레벨 오브젝트는 대체로 싱글톤 패턴 적용에 좋다. 하지만 싱글톤 패턴을 무분별, 부적절하게 사용하면 불필요한 전역 상태나 종속성이 발생할 수 있어 사용에 유의해야 한다. 쉽게 사용할 수 있지만 오용되기 쉬운..

유한 오토마타의 닫힘 성질먼저 유한 오토마타의 닫힘 성질에 대한 정리를 살펴보자. 만약 L1, L2가 정규 언어라면, L1 ∪ L2, L1 ·L2, L1*은 정규 언어이다. 즉, 정규 언어는 합집합, 접속, 클로저에 대해 닫혀있다. 정규 언어의 합집합은 간단하게 두 문법의 Product rule을 합쳐주어 두 정규 언어를 합집합 연산 할 수 있다. P1: S1 -> 0S1 S1 -> 0, P2: S2 -> 1S2 S2 -> 1의 두 문법이 생성하는 언어의 합집합을 구해보자. 위 정리에서 정규 언어의 합집합은 두 문법의 생성 규칙을 합쳐주면 된다고 하였으니, 합집합에 대한 생성 규칙 P는 P1 ∪ P2 ∪ {S -> S1 | S2}로 다음과 같다.P: S -> S1 S -> S2 ..

동치 관계를 이용한 상태수 최소화 앞선 포스팅에서 NFA를 DFA로 변환하는 방법을 알아보았다. 그런데 DFA를 만들었을 때, 상태수가 너무 많으면 상태 전이표의 크기가 커져 많은 기억 공간을 차지하게 되고 어휘 분석 프로그램이 복잡해질 수 있다. 이때, 우리는 몇 가지 방법을 이용해 상태수를 줄일 수 있다. ω ∈ $Σ^*$에 대해 만약 q1에서 ω를 다 본 상태가 q3이고, q2에서 ω를 다 본 상태가 q4일 때, q3, q4중 하나만 종결 상태에 속하면 q1은 q2로부터 구별된다(distinguish)고 한다. 이 정리에 따르면 구별되지 않는 상태들은 같은 형태의 입력 스트링을 인식하므로 모두 합쳐버릴 수 있다. 이것을 동치 관계를 이용해 합치는 방법은 아래와 같다. 1. 상태를 종결 상태와 ..

서론 객체지향 설계, 디자인 패턴과 관련된 강의를 1학기때 수강하고 최근에 몇몇 문서를 찾아보던 중, 유니티에서 작성한 ' 디자인 패턴 및 SOLID 원칙으로 코딩 스킬 업그레이드' 문서를 발견하였다. 실제로 게임 프로그래밍 관련 과목을 들을 때 코드 설계를 주먹구구식으로 해버린 부분이 너무 많아서 좀 힘들었는데, 이런 문서를 발견하여 한번 읽어보며 디자인 패턴도 리캡해보기로 하였다. 오브젝트 풀 FPS 게임에서 총알을 발사할 때마다 총알 오브젝트를 생성(Instantiate), 파괴(Destroy)하는 과정을 자주 수행하게 되면 끊김 현상이나 스파이크가 발생하는 원인이 될 수 있다. 게임을 포함한 모든 프로그램들에서 끊김 현상이 발생하는 것은 사용자에게 썩 좋은 경험이 아닐 것이다. 따라서 우리는 게..

NFA에서 DFA로의 변환 앞 포스팅에서는 비결정적 유한 오토마타인 NFA에 대해 알아보았다. 확실히 DFA에 비해서 NFA는 전이 가능한 상태수가 많아져 확연히 복잡하게 느껴졌을 것이다. 실제로 NFA는 언어의 구조를 쉽게 표현할 수 있지만 DFA보다 프로그램으로 구현하기 어렵다. NFA에서 스트링을 인식하는 과정은 어떤 상태에서 전이 함수를 거쳐 또 다른 상태로 전이되는 것으로 진행된다. 이때, NFA는 여러 상태로 전이 가능하므로 상태들의 집합에서 심벌을 보고 또 다른 상태 집합으로 전이된다. 여기서 상태 집합이라는 말에 주목해보자. {a, b, c}와 같은 상태 집합을 아예 X로 간주한다면, NFA도 결정적으로 전이될 수 있다. 상태들의 집합 Q가 유한 집합이기 때문에 $2^{Q}$ 역시 유한 집..

지도 학습 지도(Supervised) 학습이란 정답이 제공되는 데이터를 활용하여 기계를 학습시키는 것으로 회귀(Regression), 의사 결정 트리(Decision Tree), 분류기 생성 등의 문제가 있다. 분류(Classification)는 Object의 class를 예측하고, 회귀는 Object의 다음 값을 예측하며, SVM(Support Vector Machine)은 분류와 회귀의 분석을 위해 사용하는 모델이다. 의사 결정 트리 이제 지도 학습 중 하나인 의사 결정 트리(Decision Tree)에 대해 알아보자. 의사 결정 트리는 feature에 따라 샘플을 구분하는 모델로, 한 번은 결정 트리를 본 적이 있을 것이다. 위는 위키디피아에서 발췌한 것으로 타이타닉 호 탑승객의 생존 여부를 나타..

상당히 오랜만에 돌아온 형식언어 관련 포스팅. 8월에 뭔가 바쁜 일들이 많아서 미루고 미루다가 결국 개강이 1주일밖에 남지 않아버렸다. 기억을 되짚으며 비결정적 유한 오토마타, NFA에 대해 알아보자. 비결정적 유한 오토마타 바로 앞 포스팅에서는 결정적 유한 오토마타인 DFA에 대해 알아보았는데, DFA는 상태 전이 함수의 결과가 1개이다. 즉, 상태 q에서 전이 함수를 거치면 하나의 상태로만 전이된다. NFA는 DFA와 반대로 상태 q에서 전이 함수를 거치면 여러 상태로 전이할 수 있다. 아래의 NFA 예시를 하나 살펴보자. M = ({q0, q1, q2, q3, qf}, {0, 1}, δ, q0, {qf})δ01q0{q1, q2}{q1, q3}q1{q1, q2}{q1, q3}q2{qf}∅q3∅{qf}..

유한 오토마타(FA) 이전 포스팅에서 정규 문법이 주어지면 이 문법이 생성하는 언어를 알 수 있다고 하였다. 즉, 정규 문법을 정규 표현식으로 치환하여 정규 문법이 생성하는 언어를 알 수 있다. 이제는 형식언어론의 꽃, 유한 오토마타를 알아보자. 일반적으로 언어에 대한 인식기(recognizer)는 입력으로 스트링을 받아서 이 스트링이 그 언어의 문장이면 "Yes", 아니라면 "No"를 답한다. 이러한 인식기 중 가장 간단한 형태는 Finite Automata라 불리는 유한 오토마타이며, 유한 오토마타는 어휘 분석기 구현에 사용된다. 문법은 nonterminal 심벌, terminal 심벌, 시작 심벌, 생성 규칙으로 총 4개의 요소로 구성되는 반면 유한 오토마타(FA)는 5개의 요소로 정의된다. ..