반응형 분류 전체보기313 백준 14621 : 나만 안되는 연애 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [ 문제풀이 ] 결국 모든 정점을 구성하는 최소 신장 트리를 만드는 것이기 때문에 크루스칼이나 프림 알고리즘을 활용하면 쉽게 해결할 수 있다. 3가지 특징 중 2, 3번 특징은 MST를 의미하며 1번 특징만 고려해서 같은 성별의 대학교만 연결 못되도록 간선을 처리해주면 된다. import java.io.BufferedReader; import java.io.. 2021. 7. 28. 브릿지 패턴(Bridge Pattern) 브릿지 패턴(Bridge Pattern)은 구조(Structural) 패턴 중 하나로써 구현부에서 추상층을 분리하여 각자 독립적으로 변형할 수 있게 하는 패턴이다. 간단하게 얘기하면 다양한 기능과 구현을 가질 수 있는 주제? 일 경우 기능 부분과 구현 부분을 분리하여 각각 추상화를 통해 확장 및 유지 보수가 용이하도록 설계하는 디자인 패턴이다. 브릿지 패턴의 구조는 다음과 같다. Abstraction : 기능 부분의 추상 인터페이스, 구현 부분의 클래스를 통해 구현 부분의 메서드를 호출 RefinedAbstraction : Abstraction 인터페이스의 기능을 확장한 클래스 Implementor : 구현 부분의 추상 인터페이스, Abstracion의 기능을 구현하기 위한 기능을 정의 Concre.. 2021. 7. 27. 추상 팩토리 패턴(Abstract Factory Pattern) 추상 팩토리 패턴은 생성(Creational) 패턴 중 하나로써 구체적인 클래스에 의존하지 않고 서로 연관되거나 의존적인 객체들의 조합을 만드는 인터페이스를 제공하는 패턴이다. 간단하게 얘기하면 관련성이 높은 여러 종류의 객체를 따로 생성하지 않고 팩토리라는 공장을 통해 생성하는 디자인 패턴이다. 추상 팩토리 패턴의 구조는 다음과 같다. 이전에 공부한 팩토리 메서드 패턴과 이름이 굉장히 비슷하다. 두 패턴 모두 객체의 생성을 캡슐화를 통해 Factory 클래스에게 위임하여 객체를 생성하는 공통점이 있지만 팩토리 메서드 패턴은 한 팩토리당 한 종류의 객체만 생성할 수 있고 추상 팩토리 패턴은 한 팩토리에서 서로 연관된 여러 종류의 객체를 생성할 수 있다는 차이가 존재한다. 무슨 말인지 이해가 안 .. 2021. 7. 27. 빌더 패턴(Builder Pattern) 빌더 패턴은 생성(Creational) 패턴 중 하나로써 복합 객체의 생성 과정과 표현 방법을 분리하여 동일한 생성 절차에서 서로 다른 표현 결과를 만들 수 있게 하는 패턴이다. 간단하게 얘기하면 복잡한 객체를 생성하는 과정을 추상화하여 서브 클래스에게 넘겨 서브 클래스에서 객체를 생성하도록 하는 디자인 패턴이다. 빌더 패턴의 구조는 다음과 같다. Director : 내부적으로 Builder 인터페이스 객체를 통해 Product를 생성하는 클래스 Builder : Product에 필요한 기능을 가지는 인터페이스 ConcreteBuilder : Builder 인터페이스를 상속받아 구체적으로 기능을 구현하고 Product를 생성하는 클래스 Product : 생성해야 할 복합 객체 간단한 예시를 통해 .. 2021. 7. 27. 프로토타입 패턴(Prototype Pattern) 프로토타입 패턴은 생성(Creational) 패턴 중 하나로써 생성할 객체들의 타입이 프로토타입인 인스턴스로부터 결정되도록 하며, 인스턴스는 새 객체를 만들기 위해 자신을 복제(clone) 하는 패턴이다. 프로토타입은 완제품을 출시하기 전에 테스트할 수 있는 시제품, 원형을 의미한다. 간단하게 얘기하면 객체를 수정하거나 테스트할 때마다 매번 새로운 객체를 생성하지 않고 기존에 만들어놨던 객체(시제품)를 복제하여 필요한 부분만 수정하는 디자인 패턴이다. 프로토타입 패턴의 구조는 다음과 같다. Prototype : 시제품(공통적인 기능)을 정의하는 인터페이스 ConcretePrototype : 시제품을 실제로 구현하는 클래스 간단한 예시를 통해 프로토타입 패턴을 이해해 보자. 2차원 좌표에 도형을 .. 2021. 7. 27. 백준 2169 : 로봇 조종하기 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net [ 문제풀이 ] 처음에는 dfs + dp로 풀었는데 중복 방문 부분을 놓쳐서 TLE가 발생하였다. 해결하려고 하였지만 자꾸 실패해서 dp로 해결하였다. 왼쪽, 오른쪽, 아래쪽으로만 로봇이 움직일 수 있다는 조건을 잘 생각해보면 같은 높이에서는 절대로 좌/우측을 번갈아서 이동할 수 없다는 것을 알 수 있다. 따라서 dp 테이블을 다음과 정의하자. dp[0][i][j] : (i, j) 최댓값.. 2021. 7. 27. 팩토리 메서드 패턴(Factory Method Pattern) 팩토리 메서드 패턴은 생성(Creational) 패턴 중 하나로써 상위 클래스에게 알려지지 않은 구체 클래스를 생성하는 패턴이며, 하위 클래스가 어떤 객체를 생성할지를 결정하도록 하는 패턴이다. 간단하게 얘기하면 상위 클래스에서 객체를 직접 생성하지 않고, 팩토리(공장)라는 하위 클래스에게 위임하여 객체를 생성하도록 하는 디자인 패턴이다. 팩토리는 결국 비슷한 기능을 수행하는 객체를 만들어내기 때문에 템플릿 메서드 패턴을 활용할 수 있다. 팩토리 메서드 패턴의 구조는 다음과 같다. Product : 팩토리 메서드로 생성할 객체의 공통 인터페이스 ConcreteProduct : 생성할 객체를 구현하는 클래스 Creator : 팩토리 메서드를 정의하는 추상 클래스 ConcreteCreator : 팩토.. 2021. 7. 26. 템플릿 메서드 패턴(Template Method Pattern) 템플릿 메서드 패턴은 행위(Behavioral) 패턴 중 하나로써 알고리즘의 구조를 메서드에 정의하고 하위 클래스에서 알고리즘 구조의 변경 없이 알고리즘을 재정의하는 패턴이다. 간단하게 얘기하면 비슷한 알고리즘을 수행하는 친구들을 각각 별도의 클래스로 구현하지 말고 공통적인 기능을 템플릿이라는 틀(추상 클래스)로 만들어 사용하고 추가적인 기능은 각자 재정의하여 구현하는 방법이다. 템플릿 메서드 패턴의 구조는 다음과 같다. AbstractClass : 템플릿 메서드를 정의하는 추상 클래스, templateMethod()는 operation1(), operation2()를 순서대로 실행하는 메서드 ConcreteClass : 상속받은 AbstractClass의 operation1(), operation.. 2021. 7. 26. 어댑터 패턴(Adapter Pattern) 어댑터 패턴(Adapter Pattern)은 구조(Structural) 패턴 중 하나로써 클래스의 인터페이스를 사용자가 기대하는 다른 인터페이스로 변환하는 패턴으로, 호환성이 없는 인터페이스 때문에 함께 동작할 수 없는 클래스들이 함께 작동하도록 해주는 방법이다. 간단하게 얘기하면 해외여행 갈 때 자주 들고 가는 돼지코 어댑터를 생각하면 쉽다. 우리나라는 220V를 사용하지만 해외여행을 가다 보면 110V를 사용하는 곳도 있을 것이다. 하지만 돼지코 어댑터를 사용한다면 110V를 사용하는 곳에서도 220V를 사용할 수 있다. 이처럼 서로 호환성이 없지만 함께 작동하도록 해주는 것이 어댑터 패턴이다. 어댑터 패턴의 구조는 다음과 같다. Target : Adapter가 구현하는 인터페이스이며 Client.. 2021. 7. 26. 이전 1 ··· 18 19 20 21 22 23 24 ··· 35 다음 반응형
