패턴

KMP (문자열 중 특정 패턴을 찾아내는 탐색) 알고리즘 C++ 구현

개념 KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트 포스 : Brute Force) "ABCDABCE"라는 문자열에서 "ABCE"라는 패턴을 찾는다고 해보자. 모든 문자열을 일일이 비교한 경우엔 아래와 같이 탐색을 진행할 것이다. 이처럼 모든 문자열을 비교하는 브루트 포스(Brute Force) 방식은 텍스트의 길이를 N, 찾고자 하는 패턴의 길이를 M이라고 했을 때 시간 복잡도가 O(NM)이다. 이는 매우 비효율적이다...

[C++] 싱글톤 패턴, Singleton Pattern

오직 한 개의 클래스 인스턴스만을 갖도록 보장하고, 이에 대한 전역적인 접근점을 제공합니다. (GoF의 디자인 패턴 181쪽) 오직 한 개의 인스턴스만을 갖도록 보장 인스턴스가 여러 개면 제대로 작동하지 않는 상황이 종종 있다. 외부 시스템과 상호작용하면서 전역 상태를 관리하는 클래스 같은 게 그렇다. ex) 파일 시스템 API 파일 시스템 클래스로 들어온 호출이 이전 작업 전체에 대해서 접근할 수 있어야 한다. 아무 데서나 파일 시스템 클래스 인스턴스를 만들 수 있다면 다른 인스턴스에서 어떤 작업을 진행중인지를 알 수 없다. 이를 싱글턴으로 만들면 클래스가 인스턴스를 하나만 가지도록 컴파일 단계에서 강제할 수 있다. 전역적인 접근점을 제공 로깅, 콘텐츠 로딩, 게임 저장 등 여러 내부 시스템에서 파일 ..

[C++] 프로토타입 패턴, Prototype Pattern

원형이 되는 인스턴스를 사용하여 생성할 객체의 종류를 명시하고, 이렇게 만든 견본을 복사해서 새로운 객체를 생성합니다. (GoF의 디자인 패턴 169p) 위와 같이 같은 게임을 만든다고 생각해보자. 몬스터들은 영웅을 잡아먹기 위해 떼지어 다닌다. 이 몬스터 들은 스포너(spawner)를 통해 게임 레벨에 등장하는데, 몬스터 종류마다 스포너가 따로 있다. 게임에 나오는 몬스터마다 Ghost, Demon, Sorcerer 같은 클래스를 만들어보자. lass Monster { // 기타 등등.. }; class Ghost : public Monster {}; class Demon : public Monster {}; class Sorcerer : public Monster {}; 한 가지 스포너는 한 가지 몬..

[C++] 관찰자 패턴, 옵저버 패턴, Observer Pattern

객체 사이에 일 대 다의 의존 관계를 정의해두어, 어떤 객체의 상태가 변할 때 그 객체에 의존성을 가진 다른 객체들이 그 변화를 통지 받고 자동으로 업에이트될 수 있게 만듭니다. (GoF의 디자인 패턴 382p) 모델-뷰-컨트롤러(MVC) 구조를 쓰는 프로그램이 발에 차일 정도로 MVC패턴은 많이 사용되는데, 그 기반에는 관찰자 패턴이 있다. 업적 달성 좀비 100마리 죽이기 다리에서 떨어지기 위와 같은 특정 기준을 달성하면 배지를 얻을 수 있는데, 배지 종류는 수백 개가 넘는다고 하자. 업정 종류가 광범위하고 달성할 수 있는 방법도 다양하다 보니 깔끔하게 구현하기가 어렵다. 조금만 방심해도 업적 시스템 코드가 암세포처럼 구석구석 퍼져 나갈 것이다. '다리에서 떨어지기'는 어떻게든 물리 엔진이랑 연결해야..

[C++] 경량 패턴, Flyweight Pattern

공유를 통해 많은 수의 소립 객체들을 효과적으로 지원합니다. (GoF의 디자인 패턴 265p) '오래된 숲이 모습을 드러낸다.' 게임에서 흔히 볼 수 있는 설정이다. 일반적으로 이런 장면은 '경량패턴'으로 종종 구현한다. 숲에 들어갈 나무들 나무들이 화면을 가득 채운 빽뺵한 숲을 볼 때, 그래픽스 프로그래머는 1초에 60번씩 GPU에 전달해야 하는 몇백만 개의 폴리곤을 본다. 수천 그루가 넘는 나무마다 각각 수천 폴리곤의 형태로 표현해야 한다. 설사 메모리가 충분하다고 해도, 이런 숲을 그리기 위해서는 전체 데이터를 CPU에서 GPU로 버스를 통해 전달해야 한다. 나무마다 필요한 데이터는 다음과 같다. 줄기, 가지, 잎의 형태를 나타내는 폴리곤 메시 나무 껍질과 잎사귀 텍스처 숲에서의 위치와 방향 각각의..

[C++] 명령 패턴, 커맨드 패턴, Command Pattern

요청 자체를 캡슐화 하는 것입니다. 이를 통해 서로 다른 사용자(client)를 매개변수로 만들고, 요청을 대기시키거나 로깅하며, 되돌릴 수 있는 연산을 지원합니다. (GoF의 디자인 패턴 311p) 명령 패턴은 메서드 호출을 실체화 한 것이다. 실체화는 '실제하는 것으로 만든다'라는 뜻으로, 프로그래밍에서는 무엇인가를 '일급(first-class)'으로 만든다는 뜻으로 통한다. 즉, 어떤 개념을 변수에 저장하거나 함수에 전달할 수 있도록 데이터, 즉 객체로 바꿀 수 있다는 걸 의미한다. 다시 요약한다면 명령 패턴은 함수 호출을 객체로 감싼다는 것이므로 콜백을 객체지향적으로 표현한 것이다. 입력 키 변경 모든 게임에는 버튼이나 키보드등 유저 입력을 읽는 코드가 있고, 이런 코드는 입력을 받아서 의미있는 ..

RAII (Resource Acquisition Is Initialization)

RAII는 Resource acquisition is initialization의 약자로 C++설계 패턴중 하나인 키워드이며 흭득된 자원을 초기화 한다. 동적인 프로그래밍을 위해 new라는 키워드를 사용해 힙 메모리에서 할당받는다. 할당 받는순간 해당 메모리의 resource를 프로그래머는 직접 관리하게 된다. 예기치 못한 exception등... 다양한 이유로 인해 할당받은 메모리를 해제하지 못하고 Memory leak이 발생하게 된다. 뿐만 아니라 mutex의 lock에서도 발생할 수 있다. 이러한 문제들을 안전하게 관리하고자 만든 것들이 unique_ptr, shared_ptr, lock_guard 등...이 있다. 해당 클래스들은 함수가 끝나면, {}(중괄호)에서 벗어 난다면.... finally..