디자인 패턴 - strategy pattern

Programming/Design Pattern 2012. 2. 10. 21:46

안녕하세요 .
블로그 포스팅을 아무렇게나 이것저것 마구잡이로 하고 있는 nolleh 입니다 .

이번엔 요새 스터디를 하고 있는 디자인 패턴에 관해 정리해볼까합니다 .
(안드로이드와 - 영상처리도 업로드해야하는데 ,.. 영상처리는.... 맷랩도 깔려있지 않아서야 .. ;;; )
책을 보고 공부하는데 책의 내용을 내것으로 만들어서 이를 나중에 필요할때마다 다시 읽으며 곱씹어보기위해 정리하려합니다.

저도 아직 배우는 입장이기 때문에 모든 정보가 맞다고는 보장할 수 없음을 양해해 주시기 바라며 ,
잘못된 정보가 있다면 지적해주세요 . 정정해나가겠습니다. ^^ 


1. 디자인 패턴 ?

프로그래머들이 많이들 이야기하는 객체지향적 프로그래밍이 유지보수등에 매우 중요한 역할을 하지만,
추상화, 캡슐화, 은닉, 상속, 다형성 등등만의 지식만으로는 해결되지 않는 많은 설계적 상황이 존재합니다 .
우리가 고민할 법한 이런 상황들을 많은 경험을 쌓으신 선임프로그래머(? 적당한 표현이 생각나지 않네요) 들이 패턴화 해서 알려진 것들이 디자인 패턴이라고 합니다.

Definition!
소프트웨어 개발 방법에서 사용되는 디자인 패턴은, 프로그램 개발에서 자주 나타나는 과제를 해결하기 위한 방법 중 하나로, 과거의 소프트웨어 개발 과정에서 발견된 설계의 노하우를 축적하여 이름을 붙여, 이후에 재이용하기 좋은 형태로 특정의 규약을 묶어서 정리한 것이다. 알고리즘과 같이 프로그램 코드로 바로 변환될 수 있는 형태는 아니지만, 특정한 상황에서 구조적인 문제를 해결하는 방식을 설명해 준다.


예컨데  ,
코드의 중복성을 제거하기 위해 ( 중복성은 가장 우선시 되는 제거 대상!  ) vehicle (탈것) 이라는 superClass를 생각해봅시다. run() , stop() 등의 기능(메서드)가 있을 수 있겠네요 .

탈것에는 자동차도, 비행기도, 배도 있죠.
잘 알다시피, subClass로 구성할 수 있습니다.

엔진을 돌리기위해 주유하는 기능도 있어야하겠네요. refuel();

여기까진 객체지향의 상속구조만으로 구현하는데 아무 문제가 없습니다.
그런데 -
탈것에 인력거(!!)를 추가해달라는 요청을 받았습니다.

<Problem 1 - 일부 subclass에는 필요없는, 있어서도 안되는 기능의 추가>

가고 (run) , 멈추는 (stop) 기능들은 인력거에 있어도 아무 문제없지만, 주유(refuel)의 기능은 필요가 없습니다.
어떻게 해야할까요 ?

1. superclass에 그냥 추가 되있지만 호출만하지 않으면 되지 않냐 ?

이 주장은 객체지향의 지향점과 조금 다릅니다.
인력거가 refuel을 호출하지 말아야 한다는 것을 알고있어야 한다는건 결국 은닉을 할 수 없다는 얘기가 되니까요 .
다른 개발자가 인력거를 이용할때 refuel을 호출해 버릴 수가 있거든요. 아까운 기름....! 버그의 여지가 있습니다.

2. run()과 stop()은 부모에 그대로 두고 interface를 이용해서 각각의 subclass에서 refuel을 구현하는건 어때 ?

자동차나 비행기나 배나 주유하는건 같은데 , 각각 구현을 따로 해야하는 상황입니다.
이런 코드의 중복성은 탈 것의 종류가 늘어남에따라 유지보수를 기하급수적으로 힘들게 할거에요!

또 객체지향적으로 어떤 방법이 있을까요 ?
흠... 우리가 알고있는 상속만으로는 이 문제를 쉽게 해결하기가 어려워 보입니다.


<Design Pattern - Strategy Pattern>

Problem 1의 요는 이렇습니다.
탈 것이라면 다 같이 있어야하는 기능 (run(),stop()) 은 상속을 통해(다 쓸거니까) 중복성을 제거했으면 좋겠고,
일부 subclass에 없는 기능은 필요한 녀석들만 이용하되, 중복되지 않았으면 좋겠다!

그럼 일단 2. 의 생각과 같이 run()과 stop()을 부모에 그대로 두고 자동차 ~ 인력거까지 탈것의 자식으로 둬봅시다.
문제가 되는 refuel()은 Refuelable 라는 인터페이스를 만들어 거기에 메서드로 붙여봐요 .
여기까진 2.와 같습니다.
단 , refuelable 로 끝내는 것이 아니라 - 주유 가능한 탈것을 위한 클래스를 또 만듭니다.
class RefuelableVehicle implements Refuelable {
        public void refuel(){
                 //기름을 넣자.
       }
} 


라는 클래스를 만들고 Vehicle 이 객체의 인스턴스를 가지고 있다가 위임 - 다른 객체의 인스턴스를 갖고 그 객체의 기능을 호출함 - 을 합니다.
다음과 같이요.
class Vehicle {
protected Refuelable refuable; //위임을 받을 객체
        public void doRefuel(){
                refuable.refuel();
        }
        public void run(){
                //부다다다당~
        }
        .....stop()..... {} ...
}

자동차는 다음과 같겠네요.
class Car extends Vehicle {
        Car(){
               refuelable = new RefuelableVehicle();
        }
}


이제 우리의 말썽쟁이 인력거는 어떻게 하죠 ?
인력거는 refuelable하지 않으니까, RefuelableVehicle()을 이용하면 안될거같아요.
주유가능하지 않은 탈것을 만들어봅시다.
class NoNeedToRefuelableVehicle() implements Refuelable {
        public void refuel(){
                 system.out.println("주유가 필요없어요. 기름 다시 가져가세요." );
        }
}

이제 다 되었습니다.
class vehicleMovedByPersonsPull extends Vehicle {
        vehicleMovedByPersonsPull(){
               refuelable = new NoNeedToRefuelableVehicle();
        }
}

이제 다른 개발자가 주유기능을 이용하기 위해서는 
어떤 탈것인지 신경쓸 필요없이  doRefuel() 을 불러주면됩니다.

주유 가능하지 않은 인력거는 알아서 주유를 하지 않을거거든요 !


이렇게 변할 수 있는 단위로 따로 클래스를 만들어서 위임하는 패턴을 스트래티지 패턴이라고 합니다.

Definition!
스트래티지 패턴(Strategy pattern) 에서는 알고리즘군을 정의하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만든다.
스트래티지를 활용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있다.

ACM-ICPC 2010년도 인터넷 예선 문제 - 1 . Three Bowling Pin

Programming/Algorithm 2010. 10. 6. 23:51

acm 홈페이지에서 문제가 없어졌네요 ;
파일 없는데 .. 인쇄해 둔 것만 있구..

혹시 이거 문제 올렸다고 저작권 같은 문제가 생기진 않겠죠 ? ' - ' ) ;;;
뭐 이미 예선 결과도 다 나오고 했으니까 .. 올려도 문제 없을거라 믿고 올립니다.

어쨌든 이 문제는 볼링 점수 계산기를 짜는겁니다.
전체 10 프레임에 , 기본적으로 한 프레임당 투구를 두번하죠.
기본적으로 쓰러트린 핀의 수만큼 점수가 올라갑니다.
단 , 스페어 처리시 (프레임의 첫 투구에서는 핀을 다 쳐내지 못했는데 두번째 투구에서 남은 모든 핀을 쳐내는 것)  
해당 프레임이후 다음 투구까지의 점수가 + 됩니다.
스트라이크 처리시에는(프레임의 첫 투구에서 모든 핀을 쳐내는 것) 다음 두번의 투구까지의 점수가 +됩니다.
때문에 10번째 프레임에서 스페어 혹은 스트라이크가 나왔을때는 점수 계산을 위해 추가 투구가 필요합니다.

이게 기본 볼링룰이죠 ..
다만 이 문제에서는 볼링핀이 3개입니다.

보기 편하게 '/'로 각 프레임을 나눴을때
1 2 / 3 / 2 1 / 2 0 / 1 0  / 2 0 / 0 1 / 1 2 / 0 1 / 3 1 1

각 프레임의 점수는
6 / 6 / 5 / 2 / 1 / 2 / 1 / 3 / 1 / 5

따라서 최종 점수는
12 + 7 + 3 + 4 + 6 = 32

입력
입력의 첫째는 언제나 그렇듯 테스트케이스의 수( 1<= T <= 100 )를 입력합니다.
각 테스트 케이스의 첫 줄은 총 투구 횟수가 입력됩니다.
다음으로 그 투구 횟수만큼 각 투구 결과를 표기합니다. (위의 예에선 1 2 3 2 1 .... 3 1 1 )

출력
점수를 출력합니다.
단, 만약 핀은 3개인데 5개를 넘어뜨린다던가 하는 말도 안되는 입력 상황에서는 error를 출력합니다.

Problem A 였던만큼 가장 쉬운 문제였겠죠 ?
그냥.. 요구하는대로 짜면 됩니다.;;;;

ACM-ICPC 2010년도 O.T. 문제 2 - Delivery

Programming/Algorithm 2010. 10. 4. 14:59


우리네 농부들은 예로부터 콩을 수확하기 위해 땅을 파고 콩 세 알을 묻었다. 한 알은 땅에 사는 벌레가 먹고, 한 알은 하늘을 날아다니다 먹이를 찾아 들르는 새가 먹고, 나머지 남은 한 알이 자라면 인간이 거두어들여 먹었다.
ICPC(Impressive Crab Porridge Corporation)는 게살죽을 전문적으로 팔면서 동시에 이웃 사랑을 직접 실천하는 사회적 기업이다. 어운동에 위치한 ICPC는 주변 정남대학교와 가기대학교 학생들이 자주 찾는데 게살죽의 인상적인 맛을 알고 나서 단골이 된 학생이 많다. 몸이 안 좋을 때에 특히 생각나는데, 배달도 가능하다. 특히 밤샘 연구로 건강을 챙기기 힘든 주변 학교의 독거 대학원생들이 식사를 거르지 않도록 죽을 배달하는 무상 급식 사업을 벌이고 있다. 이는 나라의 미래에 조금이라도 보탬이 되고자 하는 사장 조송범씨의 사회적 기업 정신이다.
학생들의 생활에 조금이라도 보탬이 되도록 배달 아르바이트는 학생만을 대상으로 고용을 하는데, 맛있는 죽을 한정된 수의 고객에게 제공하다 보니 수지타산을 맞추기 빠듯하여 한 명의 배달원 만을 고용하고 있다. 이 한 명의 배달원이 주문 배달도 하면서 무상 급식 사업까지 도와준다. 특히 배달에 있어서 사장 조성범씨의 깐깐함이 묻어 나오는 것은 배달 순서에 있어서 선착순 원칙이다. 주문 배달에 대해서 먼저 주문한 사람에게 먼저 배달되어야 하며, 무상 급식에 있어서도 먼저 신청한 사람에게 먼저 배달되어야 한다. 단, 돈을 지불하는 주문 배달한 사람과 무상 급식을 신청한 사람의 순서는 무관하다. 예를 들어서, A, B, C의 순서로 배달 주문이 들어오고 X, Y, Z의 순서로 무상 급식 신청이 들어오게 되면 B는 반드시 A에게 배달된 다음에 배달되어야 하며 C 보다 먼저 배달을 받아야 하지만 X, Y, Z의 배달 순서와는 상관이 없다.
ICPC의 사회 서비스를 도와주기 위해, 한 명의 배달원이 배달 주문, 무상 급식 신청 두 가지 모두를 최단 거리로 배달할 수 있는 프로그램을 작성하시오. ICPC에서 출발하며 ICPC의 위치는 (0, 0)으로 가정한다.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트케이스의 첫 줄에는 배달 주문의 수와 무상 급식 신청의 수 N (1  N  20), M (1  M  20)이 공백 하나를 사이에 두고 주어진다. 그 다음 N 줄에 걸쳐 각 배달 주문의 위치가 순서대로 한 줄에 하나씩 좌표 (x, y)로 주어지고, 그 다음 M 줄에 걸쳐 각 무상 급식 신청 위치가 한 줄에 하나씩 좌표 (x, y)로 주어진다(0  x  100, 0  y  100, x, y 는 정수). x와 y는 하나의 공백을 사이에 두고 주어진다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 한 명의 배달원이 두 종류의 배달을 마칠 수 있는 최단 거리를 출력하시오. 단, 소수점 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

Sample Input

3
2 3
1 1
2 1
1 0
2 0
3 0
4 5
35 53
19 15
43 59
21 37
35 77
81 26
23 65
95 52
76 45
4 1
74 41
80 65
74 99
93 99
82 89

Output for the Sample Input

5.0
407.8
165.2


 어렵다!! 단순하게 생각했다간 큰 코 다친다. 
현재 위치에서 가장 짧은곳 부터 가면 될 거 같지만,(탐욕적 알고리즘) 이 방법이 항상 최소의 값을 가진다고 단언 할 수 없다. 때문에 되추적(Back Tracking)같은 방법을 이용 해야 하는데,  되추적을 이용하려면 Tree 와 같은 자료구조를 형성해야 하는데 이게 만만치 않다. 포인터를 조작하는 일이다보니 엑세스 위반도 자주 일어난다.
실제 시험에 나왔다면 그냥 나중에 쉬운 문제들 풀고 시간남을때 한번 봐주는 문제.

필자는 OT시간땐 다 못풀고, 오기생겨서 집에서 알고리즘을 짜서 다음날 코딩을 해봤는데도 1~2시간 가량 디버그에 열중해야 했다. 역시 포인터,재귀는 편리하지만 어렵다 ㅠ

필자의 풀이의 과정을 말로 풀어보자면 이렇다.
1. 트리 클래스(구조체)형성
2. 루트 노드를 만들고
3. 재귀로 계속해서 노드를 생성한다.
4. 3에서 만약 weight(거리)가 지금까지의 최저값보다 크다면 해당 가지에서의 노드 생성을 중지한다
5. 트리가 완성되면 모든 과정을 중지한다.