반응형

C++ 소스 코드 62

11.2 너비 우선 탐색(정점과 간선 그래프) [디딤돌 자료구조와 알고리즘 with C++]

11.2 너비 우선 탐색(정점과 간선 그래프) 이번에는 정점과 간선 집합 그래프에서 너비 우선 탐색 코드를 구현합시다. 그래프와 Heuristic, Edge에 관한 코드는 10.4 깊이 우선 탐색(정점과 간선 그래프) 코드와 같으니 참고하세요. 먼저 깊이 우선 탐색하는 순서를 이해하기 쉽게 구현한 코드를 구현합시다. int main(){먼저 그래프를 생성하고 정점과 간선을 추가하세요. Graph *graph = new Graph();//그래프 동적 생성 for(int i = 0; iAddVertex(i); } graph->AddEdge(0, 1);//간선 추가 graph->AddEdge(0, 2);//간선 추가 graph->AddEdge(1, 2);//간선 추가 graph->AddEdge(1, 3);//..

11.1 너비 우선 탐색(인접 행렬) 구현(디딤돌 자료구조와 알고리즘 with C++)

11.1 너비 우선 탐색(인접 행렬) 구현 제일 먼저 인접 행렬로 너비 우선 탐색을 구현해 보아요. 그래프와 Heuristic에 관한 코드는 10.3.3 깊이 우선 탐색(인접 행렬) 코드와 같으니 참고하세요. 먼저 깊이 우선 탐색하는 순서를 이해하기 쉽게 구현한 코드를 구현합시다. int main(){먼저 그래프를 생성하고 간선을 추가하세요. Graph *graph = new Graph(9);//그래프 동적 생성 graph->AddEdge(0, 1);//간선 추가 graph->AddEdge(0, 2);//간선 추가 graph->AddEdge(1, 2);//간선 추가 graph->AddEdge(1, 3);//간선 추가 graph->AddEdge(2, 4);//간선 추가 graph->AddEdge(3, 6)..

10.4 깊이 우선 탐색(정점과 간선 그래프)

10.4 깊이 우선 탐색(정점과 간선 그래프) 이번에는 그래프를 정점(Vertex)과 간선(Edge) 집합으로 표현한 후에 깊이 우선 탐색을 구현해 보아요. 먼저 간선을 정의합시다. 여기에서는 방향성 없는 그래프로 표현할게요.class Edge{간선의 두 정점을 멤버 필드로 추가하세요. int vt1; int vt2;public:생성할 때 두 개의 정점을 입력 인자로 받습니다. Edge(int vt1,int vt2);특정 점정을 포함하는지 판별하는 메서드를 제공하세요. bool Exist(int vt)const;두 개의 정점을 포함하는지 판별하는 메서드도 제공하세요. bool Exist(int vt1, int vt2)const;하나의 정점을 입력 인자로 받은 후에 나머지 정점을 반환하는 메서드도 제공하세..

26. 방문자 패턴(Visitor Pattern) [Escort GoF의 디자인 패턴]

26. 방문자 패턴(Visitor Pattern) 26.1 개요 프로그래밍하다 보면 여러 구성 요소로 구성된 개체를 정의해야 하는 경우는 매우 흔한 일입니다. 그리고 특정 명령을 수행함에 있어 내부 구성 요소 개체들의 형식에 따라 적용해야 할 구체적 행위가 다른 경우가 있습니다. 이 경우에 방문자 패턴을 사용하면 개체들의 형식에 따라 적용해야 할 구체적 행위를 분리하여 정의할 수 있습니다. 이는 새로운 행위를 정의할 필요가 생길 경우에도 구성 요소 형식을 변경하지 않으면서 추가할 수 있게 됩니다. 방문자 패턴에서는 개체를 구성하는 여러 요소 개체들에게 요소의 형식에 따라 수행할 구체적 작업을 방문자에 정의하게 됩니다. 대신 요소의 형식에서는 방문자를 수용하는 메서드를 제공하고 방문자를 통해 자신을 제어하..

25. 템플릿 메서드 패턴(Template Method Pattern) [Escort GoF의 디자인 패턴]

25. 템플릿 메서드 패턴(Template Method Pattern) 25.1 개요 템플릿 메서드 패턴은 특정 연산을 수행하는 단계별로 수행해야 할 행위에 대한 약속을 기반 클래스에서 정의하고 각 단계별로 수행하는 구체적 구현은 파생 클래스에서 재정의하는 형태의 패턴입니다. 비슷한 형태의 프로그램을 작성에 필요한 뼈대를 일반화하여 제공하는 것은 실무에서 자주 사용하는 기법입니다. 일반화 과정을 통해 작성된 뼈대가 마련되어 있다면 실제 프로그래밍할 때에는 이를 기반으로 세부적인 기능만 재정의를 하여 효과적으로 프로그래밍할 수 있습니다. 그리고 설계 단계에서 뼈대에 대한 부분을 고민하지 않아도 되어 비용을 줄일 수 있고 기술 노하우를 축적할 수 있게 해 줍니다. 이를 위해서 템플릿 메서드 패턴에서는 특정 ..

24. 전략 패턴(Strategy Pattern) [Escort GoF의 디자인 패턴]

24. 전략 패턴(Strategy Pattern) 24.1 개요 프로그래밍하다 보면 같은 문제를 해결하는 여러 가지 방법 중에 무엇을 사용하는 것이 효과적인지 고민을 하는 경우가 많습니다. 어떤 때에는 일단은 효율이 떨어져도 개발 비용이 적게 드는 방법으로 해결을 하고 차후에 개선된 알고리즘을 사용하여 교체를 하는 방법을 사용하기도 합니다. 이 경우에 알고리즘에 대한 추상화를 통해 전략 패턴을 적용하면 효과적으로 작업을 진행할 수 있습니다. 전략 패턴은 동일한 문제를 해결하기 위한 여러 알고리즘을 일반화하여 사용하는 부분에서 특정 알고리즘에 종속적이지 않고 독립적으로 사용할 수 있게 하는 패턴입니다. 전략 패턴에서는 구체적으로 어떠한 방법으로 문제를 해결해야 할 지를 결정하지 못한 경우에 해당 부분만을 ..

23. 상태 패턴(State Pattern) [Escort GoF의 디자인 패턴]

23. 상태 패턴(State Pattern) 23.1 개요 프로그래밍하다 보면 개체의 상태에 따라 구체적인 행위가 다르게 작성해야 하는 경우가 있습니다. 상태 패턴은 이와 같이 상태에 따라 동작을 다르게 해야 하는 부분만 별도의 클래스로 정의를 하는 패턴입니다. 상태 패턴에서는 특정 형식의 개체가 상태에 따라 동작을 다르게 하는 행위를 조사하여 추상 클래스로 만듭니다. 그리고 각 상태에 따라 구체적인 행동을 하는 파생 클래스들을 정의하게 됩니다. 이와 같이 정의하면 특정 형식에서 해당 부분은 별도의 상태 개체를 통해 수행하게 됩니다. 상태 패턴을 이용하면 개발자는 본다면 특정 형식의 상태의 추가나 삭제에 빠르고 유연하게 대처할 수 있게 됩니다. 23. 2 시나리오 이번에 EH Camera 업체에서는 단순..

22. 감시자 패턴(Observer Pattern) [Escort GoF의 디자인 패턴]

22. 감시자 패턴(Observer Pattern) 22.1 개요 감시자 패턴은 하나의 개체가 여러 개체의 상태변화를 감지하는 역할을 담당하게 하는 패턴입니다. 특정 개체의 상태가 바뀌게 되었을 때 이를 반영해야 하는 개체가 여러 개 있을 수 있습니다. 이 경우에 다른 개체의 상태가 바뀌었을 때 자신도 변화를 갖어야 하기 때문에 결합도가 강하여 유연하게 프로그래밍하기 힘들어집니다. 이 경우에 감시자 패턴을 사용을 하면 결합도를 느슨하게 하여 유연한 프로그래밍을 할 수 있게 해 줍니다. 감시자 패턴에서는 감시자는 다른 개체의 상태의 변화를 통보를 받는 역할과 이 변화를 구독하기를 원하는 개체에게 알려주는 역할을 합니다. 이를 위해 감시자 개체는 상태의 변화가 발생하는 주 개체에게 상태 변화에 대한 통보를 ..

21. 메멘토 패턴(Memento Pattern) [Escort GoF의 디자인 패턴]

21. 메멘토 패턴(Memento Pattern) 21.1 개요 메멘토 패턴은 개체의 상태를 기록해 놓았다가 원래 상태로 복원을 할 필요가 있을 때 기록해 놓은 것을 사용되는 패턴입니다. 메멘토 패턴은 실행 취소 기능을 지원하고자 할 때 많이 사용됩니다. 간단한 예를 들어볼께요. 어떤 응용에서 특정 기능을 수행할 것을 요청하기 전에 원본 개체에게 메멘토 개체를 요청합니다. 원본 개체는 자신의 상태 정보에 대한 스냅샷인 메멘토 개체를 생성하여 반환합니다. 그리고 특정 기능을 수행하다가 수행 이전 상태로 복원이 필요하게 되면 반환 받았던 메멘토 개체를 원본 개체에게 전달하여 복원할 것을 요청합니다. 원본 개체는 전달받은 메멘토 개체에 보관해 두었던 이전 상태 값을 얻어와서 자신의 상태를 복원을 하는 것입니다..

20. 중재자 패턴(Mediator Pattern) [Escort GoF의 디자인 패턴]

20. 중재자 패턴(Mediator Pattern) 20.1 개요 중재자 패턴은 프로그램의 상호작용을 해야 하는 개체들이 서로 복잡하게 관계를 맺고 있을 경우에 상호작용에 관련된 행동을 별도의 형식으로 정의하여 중재하는 개체를 만드는 패턴입니다. 프로그램을 작성하다 보면 복잡한 상호작용을 해야 하는 경우 개체들 간의 결합도는 강하게 되고 유연성이 떨어져서 재사용하기 힘든 경우가 발생합니다. 특히, 하나의 개체에서 다른 개체에게 일방적으로 명령을 하는 것이 아니라 명령을 받는 개체도 특정 조건에서 명령을 내린 개체에게 명령을 내릴 수 있는 경우에는 구조적으로 취약하게 됩니다. 이와 같은 경우에 중재자 패턴을 사용하면 전체적으로 강한 결합도를 부분적으로만 결합도가 강한 상태를 유지하고 많은 부분에서 결합도를..

반응형