CS23 [알고리즘] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy Algorithm) 이란? 그리디 알고리즘은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황 만을 쫓아 최종적인 해답에 도달하는 방법입니다. 따라서 가장 직관적인 알고리즘 설계 패러다임 중 하나라고 볼 수 있습니다. 여러 경우 중 하나를 결정할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다. 그리디는 현재도 최적이면서 최종적으로도 최적인 문제들입니다. 따라서 현재 상황에서 최적인 해를 찾으면 됩니다. 탐욕 알고리즘 문제를 해결하는 방법 1. 선택 절차 (Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다. 2. 적절성 검사 (Feasibility Check): 선택된 해가 문제의 조.. 2022. 9. 27. 팩토리 메서드 패턴 코드를 짜면서 객체를 할당할 때 우리는 'new'를 사용합니다. 예를 들어 오리를 종류별로 만든다고 하면 아래와 같이 조건에 따라 만들게 됩니다. Duck duck; if (picnic) { duck = MallardDuck(); } else if () { duck = new DecoyDuck(); } else if (inBathTub) { duck = new RubberDuck(); } 이 코드를 보면 구상 클래스의 인스턴스가 여러 개 있으며, 그 인스턴스의 형식은 실행 시에 주어진 조건에 따라 결정된다는 사실을 알 수 있습니다. 이런 코드를 변경하거나 확장할 때는 코드를 다시 확인하고 새로운 코드를 추가하거나 기존 코드를 제거해야 합니다. (OCP에 위배됩니다) 따라서 코드를 이런 식으로 만들면 관리.. 2022. 8. 17. 템플릿 메서드 패턴 (Template Method Pattern) 템플릿 메서드 패턴은 전체적으로 동일하면서 부분적으로는 다른 구문으로 구성된 메서드의 코드 중복을 최소화할 때 유용합니다. 다른 관점에서 보면 동일한 기능을 상위 클래스에서 정의하면서 확장/변화가 필요한 부분만 서브클래스에서 구현할 수 있도록 합니다. 엘리베이터 제어 시스템을 예시로 생각해볼 때 엘리베이터는 움직이는 동안 문이 닫혀있는지 체크해야합니다. 따라서 엘리베이터를 움직이는 Motor와 Door 클래스의 연관 관계를 정의해야 합니다. enum DoorStatus { CLOSED, OPENED } enum MotorStatus { MOVING, STOPPED } enum Direction { UP, DOWN, LEFT, RIGHT } class Door { private DoorStatus door.. 2022. 8. 12. 데커레이터 (Decorator Pattern) 패턴 데커레이터 패턴은 기본 기능에 추가할 수 있는 기능의 종류가 많을 경우에 각 추가 기능을 Decorator 클래스로 정의한 후 필요한 Decorator 객체를 조합함으로써 추가 기능을 설계하는 방식입니다. 예를 들어 요리하는 기구의 기능이 삶다, 튀기다, 굽다, 찌다라는 4개의 기능이 있을 경우 총 15가지의 조합이 가능해집니다. 이 조합을 모두 하나의 객체를 상속받게 되면 15개의 객체가 되어 너무 많은 객체가 만들어집니다. 따라서 이런 부분들을 조합에 따라 객체를 만드는 것이 아닌 Decorator 객체로 각 기능을 만들어 조합하는 방식으로 가는 것이 더 효율적입니다. // Cut, Steam, Fry, Grill abstract class Cook { public abstract void show(.. 2022. 8. 8. 옵저버 패턴 (Observer Pattern) 옵저버 패턴은 데이터의 변경이 발생했을 경우 상대 클래스나 객체에 의존하지 않으면서 데이터 변경을 통보하고자할 때 유용합니다. 상적을 출력하는 기능 있다고 할 때 입력된 점수를 저장하는 ScoreRecord 클래스와 점수를 목록의 형태로 출력하는 DataSheetView 클래스가 필요하다. 성적이 입력된 경우, ScoreRecord 클래스의 addScore 메서드가 실행될 때 성적을 출력하려면 ScoreRecord 클래스는 DataSheetView를 참조해야 합니다. import java.util.ArrayList; import java.util.List; public class ScoreRecord { private List scores = new ArrayList(); private DataSheet.. 2022. 8. 2. 커맨드 패턴 (Command Pattern) 커맨드 패턴은 이벤트가 발생했을 때 실행될 기능이 다양하면서도 변경이 필요한 경우에 이벤트를 발생시키는 클래스를 변경하지 않고 재사용하고자 할 때 유용하다. 버튼을 눌러 램프를 킨다는 상황을 가정으로 코드를 구현해보면 Button Class가 Lamp를 주입받아 버튼을 눌렀을 떄 lamp의 turnOn 함수가 실행되는 것을 확인할 수 있습니다. public class Lamp { public void turnOn() { System.out.println("Lamp On"); } } public class Button { private Lamp theLamp; public Button(Lamp theLamp) { this.theLamp = theLamp; } public void pressed() { th.. 2022. 7. 27. 스테이트 패턴 선풍기나 형광등의 경우 전원을 키거나 끌 수 있다. 켜져있거나 꺼져 있는 "상태"에 대한 처리가 스테이트 패턴의 핵심이다. 상태란 객체가 시스템에 존재하는 동안, 즉 객체의 라이프 타임 동안 객체가 가질 수 있는 어떤 조건이나 상황을 표현한다. ex) 어떤 액티비티 등을 수행하거나 특정 이벤트가 발생하기를 기다리는 것이다. 상태 진입은 객체의 한 상태에서 다른 상태로 이동하는 것을 말한다. ex) 선풍기가 전원이 켜진 상태로 진입 형광등을 키고 끄는 과정을 하나의 객체로서 코드로 표현하자면 아래와 같습니다 public class Light { private static int ON = 0; private static int OFF = 1; private int state; public Light() { .. 2022. 7. 22. 싱글톤 패턴 (Singleton Pattern) 프린터를 관리하는 프로그램이 있다고 가정하자. public class Printer { public Printer() {} public void print(Resource r) { ... } } Printer 클래스를 사용해 프린터를 이용하려면 new Printer()로 생성하면 된다. 하지만 new Printer()를 하면 무한대로 프린터를 할당할 수 있기 때문에 Printer 생성을 막고자하면 private로 선언하면 된다. public class Printer { private Printer() {} public void print(Resource r) { ... } } 이렇게 되면 외부에서 Printer를 만들 수 없어서 인스턴스를 제공하는 함수를 생성해야 한다. public class Print.. 2022. 7. 18. 스트래티지 패턴 (Strategy Pattern) public abstract class Robot { private String name; public Robot(String name) { this.name = name; } public String getName() { return name; } public abstract void attack(); public abstract void move(); } public class Robot1 extends Robot { public Robot1(String name) { super(name; } public void attack() { System.out.println("I have punch"); } public void move() { System.out.println("I can only walk.. 2022. 7. 6. 이전 1 2 3 다음
