'전체 글'에 해당되는 글 32건

1. 커맨드 패턴이란

1.1 커맨드 패턴의 정의

이 정의에서 핵심은 요청을 캡슐화한다는 점이다.

요청이 캡슐화되기 떄문에 로그를 출력하거나 실행을 취소할 때 유용하게 사용 될 수 있다.

1.2 UML

위 다이어그램에서 클라이언트가 리시버와 커맨드 객체를 생산하고, 커맨드를 보낼 때는 인보커를 통해서 보내게 된다.

2. 적용 예제

Head First Desgin Pattern에 나오는 예제를 수정한 것이다.

주식회사 홈 오토메이션에서는 가정집의 전등, 차고문, 오디오, 선풍기 등을 조종할 수 있는 만능 리모컨을 개발하려고 한다.

만능 리모컨은 전자기기와 연결 할 수 있는 7개의 슬롯과 그 각각을 켜고 끄는 버튼, 그리고 하나의 취소버튼을 가진다.

그런데 문제는 전자기기들의 작동 방식이 서로 다르다는 것이다.

각 전자기기들을 클래스화한 클래스 다이어그램을 보면서 이야기 하도록 하겠다.

켜기/끄기 버튼만을 가진 리모컨으로 조종하기엔 작동 방식이 너무 제각각이다. 전등(Light)의 경우는 켜고 끄는게 다지만, 오디오(Stereo)는 작동시키기 위해 setCD() 메소드로 CD명을 입력하고, setVolume() 메소드로 볼륨도 조절해줘야하고, 선풍기는 high(), medium(), low() 메소드로 속도를 조절해야한다.

리모컨의 몇번 슬롯에 어느 전자기기가 연결될 지 알 수 없기 때문에 버튼이 눌렸을 때 if-else 문으로 슬롯과 연결된 클래스의 타입을 검사하여 실행하도록 구현되어야 할 것이다.

하지만 그렇게 구현하면 새로운 클래스가 추가될 때마다 리모컨에 있는 코드를 고쳐야 되고, 이는 버그 발생률을 높이는 원인이 된다.

이런 문제를 해결하기 위해 커맨드 패턴을 적용해보도록 하자.

2.1 커멘드 인터페이스 및 구상 클래스 정의

커맨드 패턴 적용을 위해 Command 인터페이스를 만들고 모든 커맨드 클래스들이 이 인터페이스를 구현하도록 한다.

Command 인터페이스는 다음과 같이 리시버에세 요청을 실행하라고 전달하는 execute() 메소드와 실행을 취소하라고 전달하는 undo() 메소드를 가진다.

이제 리모컨 클래스는 이 Command 인터페이스를 이용하여 execute(), undo()메소드가 어떻게 구현되었는지는 신경쓰지 않도록 구현한다.

LightOnCommand

//LightOnCommand.h
#pragma once
#include "Command.h"
#include "../HomeObejcets/Light.h"


//불 켜기 커맨드
//light의 name 어트리뷰트를 통해 어느 곳에 있는 전등인지 구별함
class LightOnCommand : public Command
{
public:
	LightOnCommand(Light* light);
	void execute();
	void undo();
private:
	Light * light = NULL;
};

//LightOnCommand.cpp
#include "LightOnCommand.h"

LightOnCommand::LightOnCommand(Light* light)
{
	this->light = light;
}

void LightOnCommand::execute()
{
	light->lightOn();
}

void LightOnCommand::undo()
{
	light->lightOff();
}

StereoOnCommand

//StereoOnCommand.h
#pragma once
#include "Command.h"
#include "../HomeObejcets/Stereo.h"

//노래 켜기 커맨드
class StereoOnCommand : public Command
{
public:
	StereoOnCommand(Stereo * stereo);
	void execute();
	void undo();
private:
	Stereo * stereo = NULL;
};

//StereoOnCommand.cpp
#include "StereoOnCommand.h"

StereoOnCommand::StereoOnCommand(Stereo * stereo)
{
	this->stereo = stereo;
}


void StereoOnCommand::execute()
{
	this->stereo->setCD(*new string("Sonyun Jump"));
	this->stereo->setVolume(13);
	this->stereo->stereoOn();
}

void StereoOnCommand::undo()
{
	this->stereo->stereoOff();
}

참고로 StereoOnCommand의 execute() 메소드에서 설정하는 CD와 볼륨 값은 임의로 넣은 값이다. 사용자 편의를 고려해서 커스텀하면 된다.

2.3.1 매크로 커맨드 구현

커맨드들 중 간혹 다수의 커맨드를 연속으로 수행해야하는 경우가 있다.

이런 커맨드를 매크로 커맨드라고 부르는데, 매크로 커맨드는 Command 인터페이스에 대한 레퍼런스를 리스트로 가지고, 그 각각의 excute() 메소드를 호출하는 것으로 execute() 메소드가 구현된다.

//MacroCommand.h
#pragma once
#include <vector>
#include <algorithm>
#include "Command.h"

using namespace std;

//다수의 커맨드를 실행하는 커맨드
class MacroCommand : public Command
{
public:
	MacroCommand(vector<Command*>& commands);
	void execute();
	void undo();
private:
	vector<Command*> commands;
};

//MacroCommand.cpp
#include "MacroCommand.h"

MacroCommand::MacroCommand(vector<Command*>& commands)
{
	this->commands = commands;
	//copy(commands.begin(), commands.end(), this->commands);
}

void MacroCommand::execute()
{
	int size = this->commands.size();
	for (int i = 0; i < size; i++)
		commands[i]->execute();
}

void MacroCommand::undo()
{
	int size = this->commands.size();
	for (int i = 0; i < size; i++)
		commands[i]->undo();
}

우리 프로젝트에서는 PartyMode이라는 커맨드를 지원한다. PartyMode는 파티를 위해서 모든 문을 열고, 모든 전등을 켜고, 오디오를 켜는 커맨드로, 매크로 커맨드 클래스로 정의된다.

//main.cpp
vector<Command*> partyOn = { kitchenLightOnCommand,bedroomLightOnCommand,garageDoorOpenCommand,stereoOnCommand };
vector<Command*> partyOff = { kitchenLightOffCommand,bedroomLightOffCommand,garageDoorCloseCommand,stereoOffCommand};
Command * partyOnCommand = new MacroCommand(partyOn);
Command * partyOffCommand = new MacroCommand(partyOff);

2.2 Invoker 역할의 RemoteController 정의

이제 위의 Command 인터페이스를 구현한 LightOnCommand, StereoOnCommand 클래스 코드를 예시로 어떻게 구현되는지 보도록 하자.

onCommands, offCommands는 각각 슬롯에 연결된 전자기기를 켜고 끄는 커맨드 클래스들을 저장한다.

각 슬롯에 커맨드를 할당하기 위해서 setCommand() 메소드로 i번 슬롯에 onCommand와 offCommand를 동시에 입력한다.

각 슬롯에 할당된 on/off 버튼을 누르기 위해서는 on/offButtonWasPushed() 메소드를 이용한다.

그리고 실행 취소를 위해서 unDoButtonWasPushed() 메소드를 사용한다.

다음은 구현된 RemoteController 클래스의 구현 코드다.

//RemoteController.h
#pragma once
#include <vector>
#include <stack>
#include <iostream>
#include "Commands/Command.h"
#include "Commands/NoCommand.h"

using namespace std;

//여러 커맨드를 묶어서 리모컨처럼 사용하는 클래스
class RemoteController
{
public:
	RemoteController();
	void setCommand(int slot, Command* onCommand, Command* offCommand);
	void onButtonClicked(int slot);
	void offButtonClicked(int slot);
	void undoButtonClicked();

private:
	//켜기 커맨드를 모은 벡터
	vector<Command*> onCommands;

	//끄기 커맨드를 모은 벡터
	vector<Command*> offCommands;

	//커맨드 실행 기록
	stack<Command*> commandStack;	
};

//RemoteController.cpp
#include "RemoteController.h"

RemoteController::RemoteController()
{
	this->offCommands.resize(7);
	this->onCommands.resize(7);

	Command * noCommand = new NoCommand();
	for (int i = 0; i < 7; i++)
	{
		this->offCommands[i] = noCommand;
		this->onCommands[i] = noCommand;
	}
}

void RemoteController::setCommand(int slot, Command* onCommand, Command* offCommand)
{
	this->onCommands[slot] = onCommand;
	this->offCommands[slot] = offCommand;
}

void RemoteController::onButtonClicked(int slot)
{
	this->onCommands[slot]->execute();
	this->commandStack.push(onCommands[slot]);
}

void RemoteController::offButtonClicked(int slot)
{
	this->offCommands[slot]->execute();
	this->commandStack.push(offCommands[slot]);
}

void RemoteController::undoButtonClicked()
{
	if (commandStack.empty())
	{
		cout << "Remote Controller Undo Caution : no command history" << endl;
		return;
	}
	cout << "undo : ";
	commandStack.top()->undo();
	commandStack.pop();
	cout << endl;
}

생성자에서 NoCommand 라는 클래스를 이용하는데, 이는 Command 인터페이스를 구현한, 아무런 기능을 하지 않는 클래스다.

슬롯이 비어있을 경우 if문을 이용하여 NULL인지 체크하는 것보다 일종의 NULL 객체인 NoCommand를 넣어 아무런 기능도 하지 않도록 구현했다.

이제 필요한 클래스들은 모두 구현되었다.

구현된 구조를 1.2절의 UML과 연관지어보면 다음과 같다.

이 시스템에서 클라이언트는 따로 클래스화 할 필요가 없어보여서 main() 함수가 클라이언트의 역할을 하도록 했다.

LightOnCommand, LightOffCommand는 Command 인터페이스를 구현한 구상 클래스다. 이 두 클래스를 이용해 전등을 켜고 끈다.

RemoteController는 Invoker의 역할이다. 7개의 슬롯에 각각의 커맨드를 할당하고 슬롯 번호로 사용한다.

이제 리모컨의 켜기/끄기 기능은 구현이 완료되었으니 undo 버튼 구현을 위한 내용들을 살펴보도록 하자.

2.3 UnDo 구현

UnDo 버튼은 직전에 실행했던 기능을 취소하는 기능이다.

우선 각 커맨드 구상 클래스에서 Undo 기능이 어떻게 구현되는지 살펴보겠다.

2.3.1 LightOn/OffCommand 클래스의 UnDo 구현

첫 번째는 가장 간단한 LightOnCommand 클래스다.

//LightOnCommand.cpp

void LightOnCommand::undo()
{
	light->lightOff();
}

LightOnCommand는 불을 켜는 커맨드이기 때문에 불을 꺼주는 것으로 Undo 기능이 구현된다.

LightOffCommand는 반대로 불을 켜주는 것으로 Undo 기능을 구현하면 된다.

//LightOffCommand.cpp

void LightOffCommand::undo()
{
	light->lightOn();
}

2.3.2 State와 Stack 이용한 FanSpeedChangeCommand, FanOffCommand 클래스의 Undo 구현

작업취소 기능을 구현할 때는 상태(State)를 저장해야하는 경우가 종종 있다.

선풍기의 경우도 그런데, Fan 클래스의 코드를 보면서 이야기해보도록 하겠다.

//Fan.h
#pragma once
#include <string>
#include <stack>
#include <iostream>

using namespace std;

//선풍기 클래스
//꺼짐, 느린속도, 중간속도, 빠른속도의 상태를 가짐
class Fan
{
public:
	enum FanStatus { Off, LowSpeed, MediumSpeed, HighSpeed };
public:
	Fan();

	/*********선풍기 속도 조절 메소드********/
	void high();
	void medium();
	void low();
	void off();	
	////////////////////////////////////////

	//선풍기의 속도를 받아옴
	FanStatus getSpeed();
	string toString();
private:
	//현재 선풍기의 상태
	FanStatus fanStatus;
};

Fan은 Off(꺼짐), LowSpeed(느리게), MediumSpeed(중간속도), HighSpeed(빠르게) 의 상태를 갖는다.

이제 커맨드 클래스에서 작업 취소 기능을 구현하는 방법을 살펴보자. 작업 취소 기능을 구현하려면 커맨드가 실행되기 이전 상태를 알아야 한다.

그러기 위해 커맨드 클래스에 Fan::FanStatus prevStatus; 필드를 추가하면 될 것 같지만, 이렇게 하면 작업 취소를 여러 번 수행 할 수 없다. 

Undo버튼을 여러번 눌렀을 때 처리 할 수가 없다는 것이다.

이 문제를 해결하기 위해 스택을 활용한다.

//FanSpeedChangeCommand.h
#pragma once
#include <stack>
#include "Command.h"
#include "../HomeObejcets/Fan.h"

//선풍기 속도 조절 커맨드
//execute 시 꺼짐->느림->보통->빠름->느림->보통... 순으로 변경됨
class FanSpeedChangeCommand : public Command
{
public:
	FanSpeedChangeCommand(Fan * fan);
	void execute();
	void undo();
private:
	Fan * fan = NULL;
	stack<Fan::FanStatus> fanStatusHistory;
};

스택을 활용하면 커맨드가 실행되기 이전 상태가 쌓이고, 작업 취소를 수행 할 때 이 스택에서 상태를 pop 하여 작업 취소에 이용하면 된다.

이제 이 스택을 활용해서 작업 취소가 어떻게 구현되는지 살펴보자.

//FanSpeedChangeCommand.cpp

void FanSpeedChangeCommand::undo()
{
	if (fanStatusHistory.empty())
	{
		cout << "FanSpeedChangeCommand undo caution : no previous Ssatus exists" << endl;
		return;
	}

	Fan::FanStatus prev = fanStatusHistory.top();
	fanStatusHistory.pop();

	cout << "fan undo : (" << fan->getSpeed() << ") -> (" << prev << ")" << endl;

	switch (prev)
	{
	case Fan::Off:
		fan->off();
		break;
	case Fan::LowSpeed:
		fan->low();
		break;
	case Fan::MediumSpeed:
		fan->medium();
		break;
	case Fan::HighSpeed:
		fan->high();
		break;
	default:
		break;
	}
}

FanOffCommand 클래스의 Undo 기능도 거의 유사하게 구현된다.

는지 살펴보자.

//FanOffCommand.cpp

void FanOffCommand::undo()
{
	if (fanStatusHistory.empty())
	{
		cout << "FanOffCommand undo caution : no previous Ssatus exists" << endl;
		return;
	}

	Fan::FanStatus prev = fanStatusHistory.top();
	fanStatusHistory.pop();

	cout << "fan undo : (" << fan->getSpeed() << ") -> (" << prev << ")" << endl;
	
	switch (prev)
	{
	case Fan::Off:
		fan->off();
		break;
	case Fan::LowSpeed:
		fan->low();
		break;
	case Fan::MediumSpeed:
		fan->medium();
		break;
	case Fan::HighSpeed:
		fan->high();
		break;
	default:
		break;
	}
}

2.3.3 Stack을 이용한 RemoteController의 Undo버튼 기능 구현

지금까지 각 커맨드 클래스에서 작업 취소 기능을 구현하는 방법을 살펴보았다.

이제는 RemoteController 클래스에서 실제로 Undo 버튼을 클릭했을 때 어떻게 처리되는지 살펴볼 차례다.

RemoteController에서는 Undo 버튼을 여러번 클릭했을 때 작업 취소가 연속적으로 실행되어야 한다.

이는 앞에서 살펴본 선풍기 관련 커맨드의 실행취소 기능의 구현과 유사해서 다시 스택을 이용해서 구현된다.

RemoteController 클래스의 정의는 위에서 기술되었으니 undoButtonClicked() 메소드만 살펴보자.

//RemoteController.cpp

void RemoteController::undoButtonClicked()
{
	if (commandStack.empty())
	{
		cout << "Remote Controller Undo Caution : no command history" << endl;
		return;
	}
	cout << "undo : ";
	commandStack.top()->undo();
	commandStack.pop();
	cout << endl;
}

commandStack은 stack<Command*>로 선언되었다.

구현된 프로젝트는 다음의 깃허브 페이지에서 확인할 수 있다.

(https://github.com/InvincibleTyphoon/CommandPatternExample/tree/master)

3. 커맨드 패턴의 장점

요구사항이 캡슐화되므로 요청을 보내는 내용의 코드 중복을 방지 할 수 있다.

작업 취소 기능을 지원하는 것은 앞서 살펴 본 바 있으니 넘어간다.

요청 내역을 큐에 저장하면 스레드 작업에 유용하다.

처리되는데 오래 걸리는 요청의 경우 스레드를 만들어 백그라운드에서 처리하는 것이 반응성을 높이는데 유용하다.

작업 큐에 다수의 커맨드 객체를 저장해두고 스레드를 여러개 만들면 각 스레드는 작업 큐에서 커맨드를 가져와 처리하면 된다. 그러면 어느 스레드가 먼저 작업을 마치든지 신경쓰지 않아도 된다.

어떤 어플리케이션에서는 모든 행동을 기록해놨다가 그 어플리케이션이 다운되었을 경우, 나중에 그 행동들을 다시 호출해서 복구 할 수 있도록 해야한다.

커맨드패턴에서는 로그를 디스크에 저장하는 store() 메소드와 로그를 읽어오는 load() 메소드를 추가하여 복구 기능을 구현 할 수 있다.

4. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

카라츠바의 빠른 곱셈

카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이다.

필요성

카라츠바 알고리즘을 소개하기에 앞서, 두자릿수 이상의 두 수를 곱하는 과정은 다음과 같다.

이를 코드로 구현하면 다음과 같이 구현 할 수 있다.

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int>& num) 
{
	num.push_back(0);

	//자릿수 올림을 처리한다.
	int size = num.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (num[i] < 0)
		{
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	//앞에 남은 0을 제거한다.
	while (num.size() > 1 && num.back() == 0)
		num.pop_back();
}

//초등학교식 정수 곱셈
vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(a.size() + b.size() + 1, 0);

	int aSize = a.size();
	int bSize = b.size();

	for (int i = 0; i < aSize; i++)
		for (int j = 0; j < bSize; j++)
			c[i + j] += a[i] * b[j];
	normalize(c);
	return c;
}

이 알고리즘의 시간복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2)이다. 2중 for문을 이용하고 있으니 이 점을 이해하기는 어렵지 않을 것이다.

카라츠바 알고리즘은 이 시간복잡도를 O(n^log(3)) 까지 낮춰주기 위해 사용된다.

log(3) = 1.585...이므로 O(n^2) 보다 훨씬 적은 곱셈을 필요로 한다.

만약 n이 10만이라고 하면 곱셈 횟수는 대략 100배 정도 차이가 난다.

아이디어

카라츠바 알고리즘이 어떻게 진행되는지 설명하기에 앞서 카라츠바 알고리즘이 시간복잡도를 O(log(3))으로 낮추기 위해 사용한 아이디어에 대해 설명하고자 한다.

자릿수가 n인 두개의 수 a,b를 단순히 곱하기 위해서는 O(n^2)이 소요되지만, 덧셈과 뺄셈을 하는데에는 O(n)시간만에 해결 할 수 있다.

카라츠바 알고리즘은 곱셈의 횟수를 줄이고, 덧셈과 뺄셈 횟수를 늘리는 방식으로 구현된다.

과정

이제 카라츠바 알고리즘이 어떻게 진행되는지 보도록 하자.

카라츠바 알고리즘은 곱하는 256자리의 두 정수 a,b를 다음과 같이 나눈다.

a1,b1은 각각 a,b의 첫 128자리, a0,b0는 각각 a,b의 뒷 128자리를 나타낸다.

이제 a * b의 계산 과정은 다음과 같이 나눌 수 있다.

이 상태에서는 n/2 크기의 두 정수의 곱셈이 총 4번 사용된다. 이 곱셈 횟수를 줄이기 위해 다음 수식을 이용한다.

이 수식을 수정하면 다음의 결과를 얻을 수 있다.

z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;

이렇게 수정하고 나면 a*b는 n/2 크기의 두 정수의 곱셈 3번, 덧셈 2번, 뺄셈 2번으로 수행 할 수 있다.

이를 재귀적으로 처리하여 a1*b1, a0*b0에 대해서도 적용하면 곱셈 결과를 얻을 수 있다.

구현

다음은 카라츠바 알고리즘을 구현한 코드다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int>& num) 
{
	num.push_back(0);

	//자릿수 올림을 처리한다.
	int size = num.size();
	for (int i = 0; i < size - 1; i++)
	{
		if (num[i] < 0)
		{
			int borrow = (abs(num[i]) + 9) / 10;
			num[i + 1] -= borrow;
			num[i] += borrow * 10;
		}
		else
		{
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
	}
	//앞에 남은 0을 제거한다.
	while (num.size() > 1 && num.back() == 0)
		num.pop_back();
}

//초등학교식 정수 곱셈
vector<int> multiply(const vector<int>& a, const vector<int>& b)
{
	vector<int> c(a.size() + b.size() + 1, 0);

	int aSize = a.size();
	int bSize = b.size();

	for (int i = 0; i < aSize; i++)
		for (int j = 0; j < bSize; j++)
			c[i + j] += a[i] * b[j];
	normalize(c);
	return c;
}

//a += b * (10^k)
void addTo(vector<int>& a, const vector<int>& b, int k)
{
	int originalASize = a.size();
	if (a.size() < b.size() + k)
		a.resize(b.size() + k);
	a.push_back(0);

	int aSize = a.size();
	for (int i = originalASize; i < aSize; i++)
		a[i] = 0;

	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i + k] += b[i];

	normalize(a);
}

// a -= b
// a>= b인 경우에만 사용 가능하다.
void subFrom(vector<int>& a, const vector<int>& b)
{
	int bSize = b.size();

	for (int i = 0; i < bSize; i++)
		a[i] -= b[i];
	normalize(a);
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b)
{
	int an = a.size(), bn = b.size();

	//a가 b보다 짧을 경우 둘을 바꾼다.
	if (an < bn)
		return karatsuba(b, a);
	//기저 사례 : a나 b가 비어있는 경우
	if (an == 0 || bn == 0)
		return vector<int>();
	//기저 사례 : a가 비교적 짧은 경우, O(n^2) 곱셈으로 변경한다.(성능을 위함)
	if (an <= 50)
		return multiply(a, b);
	int half = an / 2;

	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
	vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

	//z2 = a1 * b1
	vector<int> z2 = karatsuba(a1, b1);

	//z0 = a0 * b0
	vector<int> z0 = karatsuba(a0, b0);
	
	//z1 = ((a0 + a1) * (b0 + b1)) - z0 - z2
	addTo(a0, a1, 0);
	addTo(b0, b1, 0);
	vector<int> z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//병합 과정
	//ret = z0+z1*10^half + z2 * 10(half*2)
	vector<int> ret(z2.size() + half * 2, 0);
	addTo(ret, z0, 0);
	addTo(ret, z1, half);
	addTo(ret, z2, half * 2);
	return ret;
}

int main()
{
	vector<int> a;
	vector<int> b;
	for (int i = 0; i < 100; i++)
		a.push_back(i % 10);

	for (int i = 0; i < 73; i++)
		b.push_back(i % 10);
	vector<int> c = karatsuba(b, a);

	int cSize = c.size();
	for (int i = 0; i < cSize; i++)
		cout << c[i];

	return 0;
}

시간복잡도

이제 카라츠바 알고리즘의 시간복잡도를 따져볼 차례다.

위의 구현에서는 a의 길이가 50 이하이면 O(n^2) 곱셈 알고리즘을 이용하도록 했지만, 계산 편의를 위해서 시간복잡도 분석에서는 한 자리 숫자에 도달해야 O(n^2) 곱셈 알고리즘을 이용한다고 친다.

a,b의 자릿수 n이 2^k 이라고 할 때 재귀호출의 깊이는 k가 된다.

한번 쪼갤 때 마다 수행해야 할 곱셈이 3배(a1*b1, a0*b0, (a0+a1) * (b0+b1))로 늘어나기 때문에 마지막 단계에서는 3^k 개의 부분 문제가 있고, 마지막 단계에서는 두 수 모두 한자리 숫자니까 곱셈 한번이면 충분하다.

따라서 곱셈 횟수는 총 O(3^k)다.

여기서 n=2^k 라고 가정했으니 k=log(n)이고,

O(3^k) = O(3^log(n)) = O(n^log(3))

이다.

병합과정도 따져보자면, 병합과정은 더하기, 빼기만으로 구현된다. 더하기와 빼기는 O(n) 시간 안에 해결되고, 재귀 호출로 단계가 내려갈 때마다 숫자의 길이는 절반이 되고 문제의 개수는 3배가 되기 때문에, 깊이 i에서 병합에 필요한 연산 횟수는 ((3/2)^i) * n 이다.

따라서 병합을 위해 필요한 총 연산 수는

이 함수는 n^log(3)과 같은 속도로 증가한다.

따라서, 최종 시간복잡도는 O(n^log3)이 된다.

출처

알고리즘 문제 해결전략 - 인사이트

1. Singleton 패턴이란

1.1 정의

싱글톤 패턴은 일반적으로 클래스의 생성자를 private으로 선언하고, 클래스 안에 static으로 자기 자신에 대한 레퍼런스를 두어 그 레퍼런스를 참조하게 하는 식으로 구현된다.

1.2 UML

Singleton 클래스는 instance라는 이름으로 자기 자신에 대한 레퍼런스를 static으로 가지고 접근 제한자는 private이다. 그리고 Singleton 클래스의 외부에서 이 클래스에 접근할 때는 getInstance()라는 static메소드를 통해 이 레퍼런스에 접근한다.

1.3 구현예시

UML 보다는 구현 예시로 보는 것이 이해가 빠를 듯 하다.

class Singleton
{
public:	
	//싱글톤 객체를 받는다.
	static Singleton* getInstance()
{
if(instance == NULL)
instance = new Singleton();
return instance;
}
static Singleton* instance;
};

*C++에서 static Singleton* instance; 라고 선언만 해두면 instance가 정의되지 않았기 때문에 컴파일 오류가 난다. 원래라면 .cpp 파일에 Singleton::Singleton* instance; 라고 한 줄 적어주어야 오류가 안 나는데, 여기서는 이해를 위해서 해당 내용은 생략하였다.

getInstance() 메소드는 내부에 static으로 선언된 instance 변수가 NULL인지 확인하고, NULL이라면 새로운 Singleton 객체를 생성한 후 그 주소를 리턴하고, NULL이 아니라면 instance 변수에 있는 객체에 대한 주소를 리턴한다.

이런식으로 하면, 외부의 어떤 클래스에서든지 Singleton::getInstance()->method() 이런 식으로 Singleton 객체에 접근 할 수 있다.

1.4 싱글톤 패턴 적용시 고려사항

개인적인 경험으로, 싱글톤 패턴을 한번 사용해 보면 구현하기가 굉장히 편하고, 또 여기저기에 적용하기가 쉬워서 싱글톤 패턴을 남용하게 될 수도 있다.

싱글톤 패턴도 당연히 단점을 가지고 있기 때문에 싱글톤 패턴은 남용하지 않도록 다음의 원칙을 준수해야 한다.

싱글톤 패턴은 위의 두 가지가 모두 만족되는 경우에만 사용해야한다.

싱글톤 패턴을 적용한 클래스는 2개 이상의 인스턴스가 존재 할 수 있도록 설계를 변경하기 어렵다. 그렇기 때문에 싱글톤 패턴을 적용 할 때는 해당 클래스의 인스턴스가 하나여야함을 보장 할 수 있을 때에만 적용해야한다.

다른 모든 클래스들에서 접근 되는 것이 아니라면, 굳이 싱글톤 패턴을 적용할 필요가 없다.

2. 적용 예제

이 예제는 Head First Design Pattern의 예제를 가져온 것이다.

요즘은 거의 모든 초콜릿 공장에서 초콜릿을 끓이는 초콜릿 보일러를 컴퓨터로 제어한다. 초콜릿 보일러는 초콬릿을 채워 넣고, 끓이고, 보일러 안의 초콜릿을 비워내는 작업을 한다.

초콜릿 보일러는 한개만으로도 충분한 양의 초콜릿을 끓일 수 있고, 비싸기 떄문에 공장마다 단 하나의 초콜릿 보일러만을 가진다고 한다.

그리고 초콜릿 보일러는 다른 모든 클래스에서 접근 가능하게 구현되어야 한다. 초콜릿 보일러는 뜨거운 초콜릿을 관리하기 때문에 사고가 나게 하지 않기 위해 여러 안전장치들이 관리하고, 추후에 시스템에 이런 안전장치들을 클래스화하여 추가할 것이다.

그래서 초콜릿 보일러에 싱글톤 패턴을 적용하여 다음과 같이 구현한다.

<ChocolateBoiler.h>
#pragma once
#include <iostream>

using namespace std;

//초콜릿을 끓이는 초콜릿 보일러 클래스
//싱글톤 패턴을 적용하여 구현됨
class ChocolateBoiler
{
public:	
	//싱글톤 객체를 받는다.
	static ChocolateBoiler* getInstance();

	//보일러에 초콜릿을 채워 넣는다.
	void fill();

	//초콜릿을 끓인다.
	void boil();

	//보일러 안에 담긴 초콜릿을 비워낸다.
	void drain();

	bool isEmpty();	
	bool isBoiled();
private:
	bool empty;
	bool boiled;
	ChocolateBoiler();
};

<ChocolateBoiler.cpp>
#include "ChocolateBoiler.h"

ChocolateBoiler::ChocolateBoiler()
{
	empty = true;
	boiled = false;
}

ChocolateBoiler* ChocolateBoiler::getInstance()
{
	static ChocolateBoiler* instance;
	if (instance == NULL)
	{
		cout << "ChocolateBoiler 객체 생성!" << endl;
		instance = new ChocolateBoiler();
	}
	return instance;
}

void ChocolateBoiler::fill()
{
	if (!isEmpty())
		return;
	empty = false;
	boiled = false;
	cout << "Chocolate Boiler 채워짐" << endl;
}

void ChocolateBoiler::boil()
{
	if (isEmpty() || isBoiled())
		return;
	boiled = true;
	cout << "Chocolate Boiler 끓여짐" << endl;
}

void ChocolateBoiler::drain()
{
	if (isEmpty() || !isBoiled())
		return;
	empty = true;

	cout << "Chocolate Boiler 비워짐" << endl;
}

bool ChocolateBoiler::isEmpty()
{
	return empty;
}

bool ChocolateBoiler::isBoiled()
{
	return boiled;
}

이제 ChocoloateBoiler 객체에 접근할 때는 다음과 같이 사용하면 된다.

ChocolateBoiler::getInstance()->fill();
ChocolateBoiler::getInstance()->boil();
ChocolateBoiler::getInstance()->drain();

3. Singleton 패턴의 장점

위의 2가지 장점이 Singleton 패턴을 사용하는 주된 이유이자 Singleton 패턴 적용시 꼭 지켜야 할 점이다.

게으르게 생성할 수 있다는 것은, 프로그램 실행 중에 인스턴스를 생성 할 수 있다는 것이다.

이는 Singleton 패턴을 적용하지 않고 전역변수를 사용 했을때에 비해서 장점인데, 전역변수를 사용하면 프로그램 실행시에 인스턴스를 바로 생성해야한다.

이렇게 할 때 문제점은, 생성된 인스턴스가 프로그램이 실행 되는 동안 한번도 사용되지 않을 경우 자원이 낭비된다.

그렇기 때문에 게으르게 생성되는 것이 Singleton의 장점이라고 할 수 있다.

인스턴스의 개수를 변경하기가 자유롭다는 말이 참 혼란스럽다. 싱글톤 패턴은 클래스의 인스턴스가 유일함을 보장 할 때만 사용해야 하는데, GoF의 디자인 패턴 책에서는 인스턴스의 갯수 변경이 자유롭다는 것을 장점이라고 설명한다.

물론 싱글톤 인스턴스에 대한 레퍼런스를 배열이나 링크드 리스트 등을 사용해서 구현하면 여러개의 인스턴스를 가지는 싱글톤 클래스를 구현 할 수는 있다.

싱글톤 패턴은, 여러개의 인스턴스를 가지는 싱글톤 클래스를 구현 할 수 있긴 하지만, 기본적으로는 한개의 인스턴스만이 존재해야 할 때 적용해야한다고 생각하면 될 듯하다.

4. Singleton 패턴의 단점

단일 책임의 원칙은 모든 클래스가 하나의 책임만을 가져야 한다는 원칙이다.

싱글톤 클래스는 클래스의 작업을 처리하는 역할 뿐 아니라 자신의 인스턴스에 대한 접근을 관리하는 역할에 대해서도 책임을 져야한다.

이렇게 하는게 전체적인 설계를 간단하게 만들 수 있어서 장점이기도 하지만, 단일 책임의 원칙을 어긴다는 점도 고려해 봐야한다.

싱글톤 패턴을 적용하면 여러 클래스나 컴포넌트가 싱글톤 클래스에 의존하게 된다. 이는 시스템의 Coupling(결합도)를 높이는 결과를 가져오기 때문에 주의해야한다.

싱글톤 클래스는 생성자가 private으로 지정되기 때문에 상속이 불가능 한데, 이를 protected나 public으로 고치면 다른 클래스에서 인스턴스를 만들 수 있게 되서 더이상 싱글톤이라고 할 수 없게 된다.

생성자 문제 뿐만 아니라, 싱글톤 클래스는 static 변수를 바탕으로 하기 때문에 모든 서브클래스들이 그 변수를 공유하게 된다.

이를 해결하기 위해서는 '레지스트리'를 구현해두어야 한다.

멀티 스레드를 적용하면 여러 스레드에서 한개의 싱글톤 클래스에 접근하게 된다. 이는 동기화 문제를 발생시킬 수 있으니 volatile 키워드를 통해 Double Checking Locking을 적용하거나 getInstance() 메소드에 synchronized 키워드를 적용하여 동기화 해야한다.

그런데 synchronized 키워드를 적용하면 스레드에서 getInstance() 할 떄마다 속도가 느려지는 문제가 발생한다.

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

- 위키피디아 Lazy Initialization

https://en.wikipedia.org/wiki/Lazy_initialization

- Code Project Singleton Pattern – Positive and Negative Aspects

https://www.codeproject.com/Articles/307233/Singleton-Pattern-Positive-and-Negative-Aspects-2

- 위키피디아 단일 책임 원칙 

https://ko.wikipedia.org/wiki/%EB%8B%A8%EC%9D%BC_%EC%B1%85%EC%9E%84_%EC%9B%90%EC%B9%99

바뀌는 부분은 캡슐화 한다.

코드에 새로운 요구사항이 있을 때마다 바뀌는 부분이 있다면, 바뀌는 부분은 바뀌지 않는 다른 부분으로부터 골라내서 분리해야한다. 그래야 바뀌지 않는 부분에 영향을 미치지 않은 채로 그 부분만 고치거나 확장 할 수 있기 때문이다.

예시

 간단한 예시로, 날아다니는 기능과 꽉꽉 소리를 내는 기능을, 그리고 수영하는 기능을 가진 오리(Duck) 클래스를 구현하는 경우를 들어 보겠다.

오리에도 여러 종류가 있는데, 청둥오리(MallardDuck), 붉은머리오리(RedheadDuck), 고무오리(RubberDuck), 나무오리(DecoyDuck)가 그들이다.

각각의 오리는 꽉꽉 소리를 내는 방법도,  날아다니는 방법도 서로 다르다.

여기까지만 생각하면 상속을 이용해서 다음과 같이 디자인 할 수 있었을 것이다.

이 구조로 구현하면 MallardDuc, RedheadDuck, RubberDuck 클래스들이 제각각 quack(), fly(), swim() 메소드를 알아서 구현 하면 된다.

하지만 여기엔 몇 가지 문제점이 있다. 

RubberDuck은 고무오리이기 때문에 날 수 없고, DecoyDuck은 나무오리이기 때문에 날 수도 없고, 꽉꽉소리도 낼 수 없다. 즉, 없는 기능을 메소드로 가지는 것이다.

그리고 꽉꽉 소리를 내는것에 대해서, MallardDuck과 RedheadDuck은 꽉꽉 하고 소리를 내지만, RubberDuck은 삑삑 하고 소리를 낸다.

요약하면 quack(), fly() 메소드는 서브클래스마다 바뀌는 부분인 것이다.

물론 서브클래스들에서 두 메소드를 적절히 정의하면 가능하긴 하다. 그러면 다음과 같이 구현 될 것이다.

하지만 이 방법들로는 코드 중복이 발생하기 때문에 코드의 보수성이 떨어진다. (MallardDuck과 RedheadDuck의 quack() 메소드가 동일. RubberDuck과 DecoyDuck의 fly() 메소드가 동일)

이 예시에서 quack(), fly() 메소드는 바뀌는 부분에 속하고, swim() 메소드는 바뀌지 않는 부분에 속한다.(물론 swim() 메소드도 구현하기에 따라서 바뀌는 부분이 될 수도 있지만, 여기서는 모두 동일하게 구현된다고 하자)

이렇게 바뀌는 부분은 다른 클래스(혹은 인터페이스)로 빼내어 구현해야한다.

바뀌는 부분을 따로 빼내어 다음과 같이 구현할 수 있다.

이와 같이 구현하면 코드 중복문제도 해결되고, 새로운 기능의 추가도 한결 쉬워진다.

가령 Duck의 서브클래스로 RocketDuck이 추가되고, 이 RocektDuck은 로켓을 타고 날아다닌다고 하면, FlyBehavior 인터페이스를 구현하는 FlyByRocekt 구상 클래스를 추가하면 끝이다.

또, MallardDuck 객체중 10% 확률로 날 수 없는 객체가 생성된다고 할 때, 그 MallardDuck 객체에게 FlyBehavior로 FlyNoWay 구상 클래스를 추가해 주면 그만이다.

1. Abstract Factory 패턴이란

1.1 Abstract Factory 패턴의 정의

정의만읽어서는 이게 무슨 내용인지 알기가 어렵다. UML과 함께 보도록 하자.

1.2 UML

2. 적용 예제

Head First Desgin Pattern에 나오는 예제를 수정한 것이다.

앞부분 내용은 Factory Method 패턴 때 썼던 글과 똑같으니 대충 읽어봐도 괜찮을 듯 하다.

객체마을 피자가게에서는 클래스를 이용하여 판매하는 피자 종류를 관리하고, 피자를 주문받는다.

피자가게 관리를 위해서 다음의 클래스 구조를 이용하고 있었다.

우선 피자 인터페이와 구상 클래스 중 하나인 CheesePizza 클래스는 다음과 같이 정의된다.

<Pizza.h>
#pragma once
#include <string>

using namespace std;

class Pizza
{
public:
	virtual void prepare() = 0;		//피자의 재료를 준비한다.
	virtual void bake() = 0;		//피자를 굽는다
	virtual void cut() = 0;			//피자를 자른다.
	virtual void box() = 0;			//피자를 박스에 담는다.
	virtual string toString() = 0;	//피자의 종류를 스트링으로 리턴한다.
};

<CheesePizza.h>
#include <iostream>
#include "Pizza.h"

using namespace std;

class CheesePizza : public Pizza
{
public:
	CheesePizza();
	void prepare() override;
	void bake() override;
	void cut() override;
	void box() override;
	string toString() override;
};

객체마을 피자가게를 나타내는 PizzaStore 클래스에서 피자를 주문하는 orderPizza 메소드는다음과 같이 구현된다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;


//피자 객체 생성
if(type.compare("cheese") == 0)
pizza = new CheesePizza();
else if(type.compare("pepperoni") == 0)
pizza = new PepperoniPizza();
else if(type.compare("clam") == 0)
pizza = new ClamPizza();
else if(type.compare("veggi") == 0)
pizza = new VeggiPizza();




//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

그런데 객체마을 피자나라의 가게 관리 프로그램이 유명해지면서, 여러 도시의 피자가게들이 이 프로그램을 이용 할 수 있게 해달라고 요청했다.

우리는 이 프로그램의 클래스 구조를 수정하여 여러 도시의 피자가게들이 이 프로그램을 이용 할 수있게 새로 만들어야한다.

문제점은, 각 지역마다 피자를 만드는 방식에 차이가 있다는 것이다.

어떤 도시에서는 피자를 만들때 빵은 얇고, 치즈는 조금 적게 넣는 편이고, 또 다른 도시에서는 빵을 두껍게하고 소스를 듬뿍 뿌려 맛을 낸다.

이를 반영하기 위해 피자 클래스는 다음과 같이 지역별로 나뉘어야 한다.

그런데 변경된 피자 클래스 구조를 반영하여, orderPizza() 메소드를 수정하면 다음과 같이 구현 될 것이다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;


//피자 객체 생성
if(type.compare("ChicagoCheese") == 0)
pizza = new ChicagoCheesePizza();
else if(type.compare("ChicagoPepperoni") == 0)
pizza = new ChicagoPepperoniPizza();
else if(type.compare("ChicagoClam") == 0)
pizza = new ChicagoClamPizza();
else if(type.compare("ChicagoVeggi") == 0)
pizza = new ChicagoVeggiPizza();
else if(type.compare("NYCheese")==0)
pizza = new NYCheesePizz();
else if(type.compare("NYVeggi")==0)
pizza = new NYVeggiPizza();
...




//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

이렇게 되면 이 프로그램을 이용하는 피자가게가 늘어 날 때마다 if-else 문이 점점 늘어나게 된다.

이런 문제를 해결하기 위해서 추상 팩토리 패턴을 적용하여 피자 객체 생성의 역할을 팩토리에게 넘기도록 다음의 구조로 수정한다.

러기 위해서 이제 팩토리 메소드 패턴을 적용하여, 피자가게와 피자 클래스를 다음과 같은 구조로 만든다.

이 다이어그램과 1.2의 UML과 비교하면, 각 요소는 다음과 같이 맵핑된다.

PizzaStore - Client

PizzaFactory - AbstractFactory

NYPizzaFactory, ChicagoFactory - ConcreteFactory1,2

Pizza 인터페이스 - Product 인터페이스

NYCheesePizza,NYVegiPizza,...ChacigoClamPizza,ChacigoPepperoniPizza - ConcreteProduct

그리고 PizzaFactory, NYPizzaFactory는 다음과 같이 정의/구현된다.

<PizzaFactory.h>

#pragma once
#include <string>
#include "../Pizza/Pizza.h"

class PizzaFactory
{
public:
	//type을 기준으로 피자를 리턴
	//만약 없는 타입이라면 NULL 리턴
	virtual Pizza* createPizza(const string& type) = 0;
};

<NYPizzaFactory.h>
class NYPizzaFactory : public PizzaFactory
{
public:
	NYPizzaFactory();

	Pizza* createPizza(const string& type) override;
};

<NYPizzaFactory.cpp>

NYPizzaFactory::NYPizzaFactory()
{
}

Pizza* NYPizzaFactory::NYPizzaFactory::createPizza(const string& type)
{
	Pizza * pizza = NULL;

	if (type.compare("cheese") == 0)
		pizza = new NYCheesePizza();
	else if (type.compare("pepperoni") == 0)
		pizza = new NYPepperoniPizza();
	else if (type.compare("clam") == 0)
		pizza = new NYClamPizza();
	else if (type.compare("veggi") == 0)
		pizza = new NYVeggiPizza();

	return pizza;
}

이렇게 구현하고 나면, 사용 할 때는 PizzaStore를 생성 할 때는 다음과 같이 각 분점에 맞는 PizzaFactory를 넘겨주면 된다.

//뉴욕 피자 팩토리를 넘겨줘서 뉴욕식 피자를 만드는 PizzaStore 생성
PizzaStore nyPizzaStore(&nyPizzaFactory);

//시카고 피자 팩토리를 넘겨줘서 시카고 피자를 만드는 PizzaStore 생성
PizzaStore chicagoPizzaStore(&chicagoPizzaFactory);

구현된 프로젝트는 다음의 깃허브에서 확인 할 수 있다.

(https://github.com/InvincibleTyphoon/AbstractFactoryPattern/tree/master)

책에서는 Java를 사용하지만, 개인적으로 C++을 더 선호하는 관계로, 구현은 C++로 했다.

3. Abstract Factory 패턴의 장점

객체를 생성하는 부분이 팩토리에 캡슐화되므로 코드 중복을 방지 할 수 있다.

구상 클래스가 아닌 추상 클래스/인터페이스에 맞춰 구현 할 수 있기 때문에 특정 구현에 덜 의존적이고, 프로그램을 더 유연하게 만들어 준다.

구상 팩토리가 생산해내는 제품별로 클래스를 분류 할 수 있다. 이 덕분에 제품군을 대체하기 쉽고, 서로 연관된 여러 제품들을 만들어야 할 때 유용하다.

한 제품군을 생산하는 팩토리는 프로그램 내에서 한개로 충분하다. 그래서 Abstract Factory 패턴을 적용할 때는 싱글톤 패턴으로 구현하는 것도 좋은 방법이 될 수 있다.

4. Abstract Factory 사용시 유의사항(단점)

Abstract Factory 인터페이스가 생성 할 수 없는 새로운 종류의 제품이 생긴다면 그 제품을 반영하기 위해서는 Abstract Factory 와 모든 구상 팩토리들을 수정해야한다.

가령 위의 피자가게 예제에서 피클을 생산하는 기능을 추가하려면, PizzaFactory 인터페이스에 createPickle() 메소드가 추가되어야하고, NYPizzaFactory, ChicagoPizzaFactory 클래스에서 createPickle() 메소드를 구현해야한다.

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

1. Factory Method 패턴이란

1.1 Factory Method 패턴의 정의

정의만읽어서는 이게 무슨 내용인지 알기가 어렵다. UML과 함께 보도록 하자.

1.2 UML

여기서 ConcreteProduct와 ConcreteCreator 여러개의 구상 클래스들을 하나로 묶은것으로 봐도 된다.

즉, ConcreteProduct1,2,3... 이런식으로 여러 종류의 클래스가 Product 인터페이스를 구현 할 수 있고, ConcreteCreatort에 대해서도 마찬가지다.

Creator 인터페이스는 factoryMethod()를 통해 Product 인터페이스 객체를 생성한다. 하지만 Creator클래스는 Product 인터페이스의 구상 클래스들 중 어떤 클래스를 생성할 지 알 수 없다.

어떤 구상 클래스를 생성할지는 ConcreteCreator 클래스에서 factoryMethod()를 오버라이드하여 결정한다.

* Product 인터페이스 객체를 생성한다는 말이 조금 헷갈릴 수도 있을 것 같은데, 추상 클래스나 인터페이스는 원래 객체화가 불가능하다. 

객체화를 할 때는 당연히 Product 인터페이스를 구현한 구상 클래스를 객체화해야하고, 이 구상 클래스를 객체화 한다는 의미로 Product 인터페이스 객체를 생성한다는 말을 사용한 것이다.

2. 적용 예제

Head First Desgin Pattern에 나오는 예제이다.

이전에 Simple Factory 글을 쓸 때 나왔던 예제의 확장판이다.

객체마을 피자가게에서는 클래스를 이용하여 판매하는 피자 종류를 관리하고, 피자를 주문받는다.

피자가게 관리를 위해서 다음의 클래스 구조를 이용하고 있었다.

우선 피자 인터페이와 구상 클래스 중 하나인 CheesePizza 클래스는 다음과 같이 정의된다.

<Pizza.h>
#pragma once
#include <string>

using namespace std;

class Pizza
{
public:
	virtual void prepare() = 0;		//피자의 재료를 준비한다.
	virtual void bake() = 0;		//피자를 굽는다
	virtual void cut() = 0;			//피자를 자른다.
	virtual void box() = 0;			//피자를 박스에 담는다.
	virtual string toString() = 0;	//피자의 종류를 스트링으로 리턴한다.
};

<CheesePizza.h>
#include <iostream>
#include "Pizza.h"

using namespace std;

class CheesePizza : public Pizza
{
public:
	CheesePizza();
	void prepare() override;
	void bake() override;
	void cut() override;
	void box() override;
	string toString() override;
};

객체마을 피자가게를 나타내는 PizzaStore 클래스에서 피자를 주문하는 orderPizza 메소드는다음과 같이 구현된다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;


//피자 객체 생성
if(type.compare("cheese") == 0)
pizza = new CheesePizza();
else if(type.compare("pepperoni") == 0)
pizza = new PepperoniPizza();
else if(type.compare("clam") == 0)
pizza = new ClamPizza();
else if(type.compare("veggi") == 0)
pizza = new VeggiPizza();




//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

그런데 객체마을 피자나라의 가게 관리 프로그램이 유명해지면서, 여러 도시의 피자가게들이 이 프로그램을 이용 할 수 있게 해달라고 요청했다.

우리는 이 프로그램의 클래스 구조를 수정하여 여러 도시의 피자가게들이 이 프로그램을 이용 할 수있게 새로 만들어야한다.

문제점은, 각 지역마다 피자를 만드는 방식에 차이가 있다는 것이다.

어떤 도시에서는 피자를 만들때 빵은 얇고, 치즈는 조금 적게 넣는 편이고, 또 다른 도시에서는 빵을 두껍게하고 소스를 듬뿍 뿌려 맛을 낸다.

이를 반영하기 위해 피자 클래스는 다음과 같이 지역별로 나뉘어야 한다.

그런데 변경된 피자 클래스 구조를 반영하여, orderPizza() 메소드를 수정하면 다음과 같이 구현 될 것이다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;


//피자 객체 생성
if(type.compare("ChicagoCheese") == 0)
pizza = new ChicagoCheesePizza();
else if(type.compare("ChicagoPepperoni") == 0)
pizza = new ChicagoPepperoniPizza();
else if(type.compare("ChicagoClam") == 0)
pizza = new ChicagoClamPizza();
else if(type.compare("ChicagoVeggi") == 0)
pizza = new ChicagoVeggiPizza();
else if(type.compare("NYCheese")==0)
pizza = new NYCheesePizz();
else if(type.compare("NYVeggi")==0)
pizza = new NYVeggiPizza();
...




//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

이렇게 되면 이 프로그램을 이용하는 피자가게가 늘어 날 때마다 if-else 문이 점점 늘어나게 된다.

이런 문제를 해결하기 위해서는 PizzaStore 클래스가 각 지역의 가게들 별로 나누어질 필요가 있다.

그러기 위해서 이제 팩토리 메소드 패턴을 적용하여, 피자가게와 피자 클래스를 다음과 같은 구조로 만든다.

이 다이어그램과 1.2의 UML과 비교하면, 각 요소는 다음과 같이 맵핑된다.

PizzaStore 인터페이스 - Creator 인터페이스

NYPizzaStore, ChicagoPizzaStore - ConcreteCreator

Pizza 인터페이스 - Product 인터페이스

NYCheesePizza,NYVegiPizza,...ChacigoClamPizza,ChacigoPepperoniPizza - ConcreteProduct

그리고 PizzaStore, NYPizzaStore, ChicagoPizzaStore는 각각 다음과 같이 정의/구현된다.

<PizzaStore.h>
#pragma once
#include <string>
#include "../Pizza/Pizza.h"

using namespace std;

//피자 가게 추상 클래스
class PizzaStore
{
public:
      //피자를 주문.
	Pizza* orderPizza(const string& type); 
protected:
        // 피자를 생성. 없는 타입이면 NULL 리턴.
	virtual Pizza* createPizza(const string& type) =  0;
};

<PizzaStore.cpp>
#include "PizzaStore.h"

PizzaStore::PizzaStore()
{
}

Pizza* PizzaStore::orderPizza(const string& type)
{
	Pizza * pizza;
	pizza = createPizza(type);

	pizza->prepare();
	pizza->bake();
	pizza->cut();
	pizza->box();

	return pizza;
}

<NYPizzaStore.cpp>
#include "NYPizzaStore.h"

NYPizzaStore::NYPizzaStore()
{
}

Pizza * NYPizzaStore::createPizza(const string& type)
{
	if (type.compare("cheese"))
		return new NYCheesePizza();
	else if (type.compare("veggi"))
		return new NYVeggiPizza();
	else if (type.compare("clam"))
		return new NYClamPizza();
	else if (type.compare("pepperoni"))
		return new NYPepperoniPizza();

	return NULL;
}

<ChicagoPizzaStore.cpp>
#include "ChicagoPizzaStore.h"

ChicagoPizzaStore::ChicagoPizzaStore()
{
}

Pizza * ChicagoPizzaStore::createPizza(const string& type)
{
	if (type.compare("cheese"))
		return new ChicagoCheesePizza();
	else if (type.compare("veggi"))
		return new ChicagoVeggiPizza();
	else if (type.compare("clam"))
		return new ChicagoClamPizza();
	else if (type.compare("pepperoni"))
		return new ChicagoPepperoniPizza();

	return NULL;
}

구현된 프로젝트는 다음의 깃허브에서 확인 할 수 있다.

(https://github.com/InvincibleTyphoon/FactoryMethodPattern)

책에서는 Java를 사용하지만, 개인적으로 C++을 더 선호하는 관계로, 구현은 C++로 했다.

3. Factory Method 패턴의 장점

Factory Method 패턴에서는 객체생성시 저수준 구성요소인 ConcreteProduct 대신 고수준 구성요소인 Product에 의존 하게된다.

피자가게 예제에서, PizzaStore 인터페이스는 피자 객체를 생성할 때, 저수준 구성요소인 NYCheesePizza, ChicagoClamPizza 등에 의존하지 않고, 고수준 구성요소인 Pizza에 의존한다.

객체의 생성을 서브클래스가 담당하기 때문에 생성할 객체 타입을 예측 할 수 없을 때 유용하고, 변화에 더 유연하게 대처 할 수 있다.

가령 위의 피자가게 예제에서, 캘리포니아(Califonia)의 피자가게에서도 이 프로그램을 이용 할 수 있게 해달라고 한다면 CalifoniaCheesePizza 등의 피자 클래스와 CalifoniaPizzaStore 클래스를 추가 해주면 되고, 뉴욕 피자가게에서 더이상 ClamPizza를 판매하지 않는다고 하면 NYClamPizza 클래스를 삭제하고 NYPizzaStore 클래스의 createPizza() 메소드에서 ClamPizza를 주문하는 부분을 삭제하면 된다.

그리고 구상 클래스가 아닌 추상 클래스/인터페이스에 맞춰 구현 할 수 있다는 점도 프로그램의 유연성을 늘려준다.

4. Factory Method 패턴 이용 시 유의 할 점(단점)

C#를 예로 들면 C#에서는 인터페이스를 제외한 추상 클래스, 일반 클래스를 다중 상속 할 수 없다. 그래서 Creator가 모든 메소드를 가상 메소드로 선언한 인터페이스이거나, ConcreteCreator의 유일한 부모 클래스가 되어야 한다.

그리고 그 외의 대부분의 언어에서도 다중 상속을 사용하면 모호성이 발생할 수 있기 때문에 다중상속은 이용하지 않는 것을 권장한다.

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- GoF의 디자인 패턴(Pearson Addison Wesley)

- 위키피디아 : Factory Method Pattern

(https://en.wikipedia.org/wiki/Factory_method_pattern)

- 윤성우저 열혈C++프로그래밍(Orange 

Simple Factory는 사실 디자인 패턴에 속하지 않는다. 하지만 프로그래밍을 하는데 있어서는 자주 사용되기도 하고, Factory Method 패턴이나 Abstract Factory 패턴과 많이 유사하기 때문에, '팩토리'의 대략적인 개념을 잡기위해 디자인 패턴 카테고리에 포함시켰다.

1. Simple Factory이란

Simple Factory는 객체를 생성하는 역할을 팩토리 클래스가 전담하게 하는 방법이다.

UML과 함께 보도록 하자.

여기서 Client는 createProduct() 메소드를 통해 SimpleFactory에게 객체 생성을 전담하고 있다.

이렇게 하면 ConcreteProduct 객체들을 필요로하는 클래스가 여러개 있을 때, SimpleFactory 클래스를 통해 객체를 생성하기 때문에 ConcreteProduct 객체를 생성하는 부분에 대한 코드 중복을 방지 할 수 있다.

2. 적용 예제

Head First Desgin Pattern에 나오는 예제이다.

객체마을 피자가게에서는 클래스를 이용하여 판매하는 피자 종류를 관리하고, 피자를 주문받는다.

피자가게 관리를 위해서 다음의 클래스 구조를 이용하고 있었다.

우선 피자 인터페이와 구상 클래스 중 하나인 CheesePizza 클래스는 다음과 같이 정의된다.

<Pizza.h>
#pragma once
#include <string>

using namespace std;

class Pizza
{
public:
	virtual void prepare() = 0;		//피자의 재료를 준비한다.
	virtual void bake() = 0;		//피자를 굽는다
	virtual void cut() = 0;			//피자를 자른다.
	virtual void box() = 0;			//피자를 박스에 담는다.
	virtual string toString() = 0;	//피자의 종류를 스트링으로 리턴한다.
};

<CheesePizza.h>
#include <iostream>
#include "Pizza.h"

using namespace std;

class CheesePizza : public Pizza
{
public:
	CheesePizza();
	void prepare() override;
	void bake() override;
	void cut() override;
	void box() override;
	string toString() override;
};

객체마을 피자가게를 나타내는 PizzaStore 클래스에서 피자를 주문하는 orderPizza 메소드는다음과 같이 구현된다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;

//피자 객체 생성
if(type.compare("cheese") == 0)
pizza = new CheesePizza();
else if(type.compare("greek") == 0)
pizza = new GreekPizza();
else if(type.compare("pepperoni") == 0)
pizza = new PepperoniPizza();

//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

여기서 조개피자(Clam Pizza)와 야채피자(Veggi Pizza)가 

추가되고, 잘 팔리지 않는 그리스식 피자(Greek Pizza)가 제외된다고 하자 그러면 코드는 다음과 같이 수정된다.

Pizza* PizzaStore::orderPizza(string type){
Pizza pizza;

//피자 객체 생성
//바뀌는 부분
if(type.compare("cheese") == 0)
pizza = new CheesePizza();
else if(type.compare("greek") == 0)
pizza = new GreekPizza();
else if(type.compare("pepperoni") == 0)
pizza = new PepperoniPizza();
else if(type.compare("clam") == 0)
pizza = new ClamPizza();
else if(type.compare("veggi") == 0)
pizza = new VeggiPizza();

//피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
//바뀌지 않는 부분
pizza.perpare();
pizza.bake();
pizza.cut();
pizza.box();
return pizza;
}

orderPizza() 메소드에서 가장 문제가 되는 점은 판매하는 피자의 종류가 바뀔 때 마다 코드를 수정해야 한다는 점이다.

즉, 피자 객체를 생성하는 부분은 바뀌는 부분이다.

이제 바뀌는 부분을 알아냈으니 이 부분을 캡슐화 하면 된다.

바뀌는 부분인 객체를 생성하는 부분을 캡슐화 하기 위해서 팩토리 패턴을 적용하여 다음과 같은 구조로 구현한다.

여기서 SimplePizzaFactory가 피자의 생성을 담당한다.

SimplePizzaFactory의 createPizza() 메소드는 다음과 같이 구현된다.

<SimplePizzaFactory.cpp>

Pizza* SimplePizzaFactory::createPizza(const string& type)
{
	Pizza * pizza = NULL;

	if (type.compare("cheese") == 0)
		pizza = new CheesePizza();
	else if (type.compare("pepperoni") == 0)
		pizza = new PepperoniPizza();
	else if (type.compare("clam") == 0)
		pizza = new ClamPizza();
	else if (type.compare("veggi") == 0)
		pizza = new VeggiPizza();
	
	return pizza;
}

이제 객체를 생성하는 역할을 SimplePizzaFactory에게 전담시켰으니 orderPizza() 메소드를 다음과 같이 수정한다.

<PizzaStore.cpp>

Pizza* PizzaStore::orderPizza(const string& type)
{
 //팩토리를 통해 피자 객체 생성
	SimplePizzaFactory factory;
	Pizza* pizza = factory.createPizza(type);

        //피자 재료를 준비하고, 굽고, 자르고, 박스에 담아서 피자를 준비.
	pizza->prepare();
	pizza->bake();
	pizza->cut();
	pizza->box();

	return pizza;
}

이제 피자 객체의 생성을 SimplePizzaFactory 클래스가 전담하기 때문에, 또 다른 클래스가 피자 객체를 생성해야 하는 상황이 생긴다면 이 SimplePizzaFactory를 이용하면 된다.

구현된 프로젝트는 다음의 깃허브에서 확인 할 수 있다.

(https://github.com/InvincibleTyphoon/SimpleFactoryPattern)

책에서는 Java를 사용하지만, 개인적으로 C++을 더 선호하는 관계로, 구현은 C++로 했다.

3. Simple Factory의 장점

Simple Factory의 장점은 이 한마디로 정리 될 수 있다.

객체를 생성하는 부분을 한 클래스에 캡슐화하면, 여러 클래스에서 어떤 클래스의 객체를 생성할 때, 그 클래스를 생성하는 코드 중복을 방지 할 수 있다.

가령 위의 예제에서 PizzaStore 클래스 뿐만 아니라, 피자에 대한 설명을 찾아서 활용하는 PizzaShopMenu 클래스, 피자를 준비 할 때 피자를 박스에 포장(box() 메소드 호출)한 후에 또 봉지에 싸서 포장해야하는 HomeDelivery 클래스가 추가되고, 피자의 메뉴에 변경이 발생하면 PizzaStore,PizzaShopMenu,HomeDelivery 세 클래스에서 피자 객체를 생성하는 부분을 수정해야하는 어려움이 있다.

하지만 객체 생성을 SimplePizzaFactory 클래스가 전담하면 SimplePizzaFactory 클래스만 수정하면 된다.

4. 레퍼런스

- Head First Design Pattern(O'REILLY media)

1. Decorator 패턴이란

1.1 Decorator 패턴의 정의

정의만읽어서는 이게 무슨 내용인지 알기가 어렵다. UML과 함께 보도록 하자.

1.2 UML

ConcreteDecoratorA, ConcreteDecoratorB는 Component를 상속받는 모든 종류의 클래스를 장식하기 위해 사용된다. 그래서 ConcreteComponent 뿐만 아니라 Decorator 클래스들도 장식 할 수 있다.

2. 적용 예제

Head First Desgin Pattern에 나오는 예제이다.

스타버즈 커피샵은 클래스를 이용하여 판매하는 음료들을 관리한다. 스타버즈 커피에서 판매하는 음료들은 다음과 같은 클래스 구조로 구성되었다.

Beverage라는 인터페이스는 가격을 계산하기 위한 cost 값과, 음료의 설명을 위한 description 값을 가진다. 자세한 가격 계산 및 description에 관한 것은 Beverage 인터페이스를 구현한 구상 클래스들의 몫이다.

그런데 여기서 커피를 주문 할 때 스팀 우유, 두유, 모카(초콜릿), 휘핑 크림 등의 첨가물을 추가했을때, 첨가물을 포함한 음료의 총 가격을 계산할 수 있는 기능이 필요해졌다.

이에따라 우리는 이 클래스 구조를 4가지 종류의 첨가물(스팀우유, 두유, 모카, 휘핑크림)을 포함한 음료의 총 가격을 계산 할 수 있도록 수정해야한다.

첨가물을 이 시스템에 추가할 방법을 찾아야 하는데, 어떤 방법이 있을까?

여기에 Decorator 패턴을 적용해 보자.

CondimentDecorator는 음료에 추가 될 수 있는 첨가물 데코레이터를 나타내는 인터페이스이며, SteamdMilk, Mocha 등의 클래스는 이 첨가물 인터페이스를 구현한다.

여기서 눈여겨 볼 점은 CondimentDecorator가 Beverage를 구성요소로 가진다는 점이다. CondimentDecorator가 구성요소로 가진 Beverage가 첨가물이 더해질 음료가 된다.

가령, Mocha 객체가 beverage로 HouseBlended를 가지면 이 음료는 모카 하우스 블렌디드 커피가 된다.

그리고 첨가물은 첨가물이 더해진 음료도 장식 할 수 있다. 그래서 다음과 같은 구조도 가능하다.

이 음료의 이름은 라떼 더블모카 하우스 블렌디드 커피가 될 것이다.

그리고 우리의 목표였던 가격 계산은 다음과 같이 수행 할 수 있다.

다음은 최상위 인터페이스인 Beverage의 구현 코드이다.

#pragma once
#include

using namespace std;

//The base class for beverages
class Beverage
{
public:
	virtual float getCost() = 0;
	virtual const string& getDescription() = 0;
protected:
	float cost; //$ notation
	string description;
};

Beverage 인터페이스는 음료의 가격을 계산하는 getCost() 메소드와 getDescription() 메소드를 갖는다.

다음은 Beverage 인터페이스를 구현한 HouseBlended 클래스다.

<HouserBlended.h>
#pragma once
#include "Beverage.h"

//House Blended Coffee
class HouseBlended : public Beverage
{
public:
	HouseBlended();
	
	const string& getDescription() override;
	float getCost() override;
};

<HouserBlended.cpp>
#include "HouseBlended.h"

HouseBlended::HouseBlended()
{
	this->cost = 0.89;
	this->description = "House Blended Coffee";
}

const string& HouseBlended::getDescription()
{
	return description;
}

float HouseBlended::getCost()
{
	return cost;
}

음료의 getCost(), getDescription 메소드의 구현은 단순히 클래스 내에 cost값과 description 값을 리턴하도록 구현한다.

다음은 Decorator 패턴을 위해 구현한 CondimentDecorator 클래스다.

#pragma once
#include "../Beverage.h"

//Decorator interface for Beverage
class CondimentDecorator : public Beverage
{
protected:
	Beverage * beverage;
	string cattedString;	//string for returning the concatenated string.
							//it's not a good way to return new object in c++, because it's not deleted automatically.
};

장식할 음료에 접근하기 위해 Beverage* beverage; 필드를 갖는다.

cattedString은 getDescription() 메소드 구현을 위해서, 두개의 string 객체를 합쳐서 리턴해야하는데, 리턴할 스트링 값을 담기 위해 사용된다.

return string1 + string2; 와같이 리턴하면, 합쳐진 결과 string 객체는 지역변수처럼 함수가 종료되면서 메모리 공간이 해제되어 사라져버린다. 그래서 필드 값으로 리턴 할 값을 담을 공간을 만들어 주었다.

다음은 Decorator 인터페이스를 구현한 구상 클래스인 Mocha 클래스를 보자. 

<Mocha .h>
#include "CondimentDecorator.h"

//Mocha condiment
class Mocha : public CondimentDecorator
{
public:
	Mocha(Beverage* const beverage);
	float getCost() override;
	const string& getDescription() override;
};

<Mocha .cpp>
#include "Mocha.h"

Mocha::Mocha(Beverage* const beverage)
{
	this->beverage = beverage;
	this->cost = 0.2;
	this->description = "Mocha, ";
}

float Mocha::getCost()
{
	return cost + beverage->getCost();
}
const string& Mocha::getDescription()
{
	cattedString = description + beverage->getDescription();
	return cattedString;
}

Mocha 클래스는 가격을 계산할 때, 자신의 가격 + beverage의 가격을 더해서 리턴한다.

getDescription() 메소드도 유사하게 구현되었고, CondimentDecorator를 구현한 모든 구상 클래스가 동일한 구조다.

구현한 프로젝트는 다음 깃허브 페이지에서 확인 할 수 있다. https://github.com/InvincibleTyphoon/DecoratorPattern

책에서는 Java를 사용하지만, 개인적으로 C++을 더 선호하는 관계로, 구현은 C++로 했다.

3. Decorator 패턴의 장점

둘 다 객체지향 설계 원칙과 관련되는 이야기다.

상속이 객체지향 설계에서 강력한 힘을 발휘하긴 하지만, 일반적으로 상속보다 구성을 우선시 해야한다. 두 클래스의 관계에 있어서 상속 관계보다는 구성 관계가 더 느슨하기 때문에, 구성이 상속에 비해 변화에 더 유연하게 대처할 수 있다.

기존 코드를 수정하면 아무래도 새로운 클래스를 작성하는 것 보다 오류를 범할 위험성이 있다. 수정해야 할 코드에 의존하는 클래스가 많다면 그 코드를 수정하는 것이 각각의 클래스에 어떤 영향을 미칠지 다 고려해야한다. 

하지만 새로운 클래스를 만드는 것은 새로 만든 클래스에 오류가 없는지만 고려하면 된다.

4. 주의 사항

5. 레퍼런스

- Head First Design Pattern(O'REILLY media)

- 위키피디아 데코레이터 패턴 : https://en.wikipedia.org/wiki/Decorator_pattern

- 위키피디아 Composition over inheritance : https://en.wikipedia.org/wiki/Composition_over_inheritance#Benefits

- 위키피디아 개방-폐쇄원칙 : https://ko.wikipedia.org/wiki/개방-폐쇄_원칙