세줄 정리

  • 각 케이스에 따라 다른 알고리즘이 사용될 때
  • 케이스가 추가될 때마다 코드를 수정하는 것이 복잡해짐
  • 이때, 케이스에 따른 알고리즘을 객체로 분리

다이어그램

strategy pattern uml

  • Strategy : 전략을 추상화시킨 인터페이스
  • Concrete Strategy : 각 케이스에 맞는 클래스로 구체적인 알고리즘을 제공
  • Context : Strategy를 실행 시킴

예시

상황

  • 손님에 따라 다른 할인 전략을 제공하려고 한다
  • 첫 손님에게 10% 할인
  • 덜 신선한 상품은 20% 할인을 제공

디자인 패턴 적용하지 않은 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Public class Calculator {
    public int calculate(boolean firstGuest, List<Item> Items) {
        int sum = 0;
        for(Item item : items) {
            if (firstGuest) {
                sum +=Item.getPrice() * 0.9; // 첫 손님 10% 할인
            } else if(!Item.isFresh()) {
                sum += item.getPrice() * 0.8; // 덜 신선한 상품 20% 할인
            } else {
                sum += item.getPrice();
            }
        }
        return sum;
    }
}
 
cs

위 코드의 문제

  • 할인 전략이 추가될때마다, 메서드를 수정하는 것이 어려워짐
  • calculate 메소드에 파라미터가 추가되어야 하며
  • else if 문이 하나 추가되어야함

디자인 패턴 적용한 경우

  • 케이스에 따른 전략을 클래스로 나눈 후에
  • 각 전략을 콘텍스트에서 실행
  • 각 전략은 콘텍스트에서 직접 선택되지 않고, 콘텍스트 사용자가 생성자를 통해 전달
  • 할인 정책이 추가될경우, 새로운 Strategy 클래스를 만들면 됨

Context 클래스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Public class Calculator {
 
    private DiscountStrategy discountStrategy; // 할인 정책을 인터페이스로 가져옴
 
    public Calculator(DiscountStrategy discountStrategy) {
        this.discountStrategy = discountStrategy; // 할인 정책 생성자를 통해 전달
}
 
public int calculate(List<Item> items) {
    int sum = 0;
    for(Item item : items) {
        sum += discountStrategy.getDiscountPrice(item);
}    
return sum;
}
}
 
cs

Strategy 인터페이스

1
2
3
4
5
6
public interface DiscountStrategy {
 
    int getDiscountPrice(Item item);
 
}
 
cs

Strategy 콘크리트 클래스

1
2
3
4
5
6
7
public class FirstGuestDiscountStrategy implements DiscountStrategy {
    @Override
    public int getDiscountPrice(Item item) {
        return item.getPrice() * 0.9;
}
}
 
cs

calculator 실행 코드

1
2
3
4
5
6
7
8
9
10
private DiscountStrategy strategy;
 
 
public int firstCustomerCalculate() { // 첫 고객이 구매할때
    strategy = new FirstGuestDiscountStrategy();
    Calculator cal = new Calculator(strategy);
 
    return cal.calculate(Items);
}
 
cs

출처

'객체 지향 프로그래밍 > 디자인 패턴' 카테고리의 다른 글

[디자인 패턴] 상태 패턴(State Pattern)  (0) 2021.03.13
[디자인 패턴] 템플릿 메서드 패턴(Template Method Pattern)  (0) 2021.03.13

문제링크 : https://www.acmicpc.net/problem/9019


아이디어

  • BFS를 사용해서 최소 시간을 구하자

    • 각 숫자에 대해 각각 연산한 뒤 값이 맞으면 출력
    • 값이 다르면 큐에 넣고 계속 수행
    • 이때 연산한 값을 가지고 있기 위해서, q에 과거 수행한 연산도 같이 등록

  • 주의해야할 것

    • L과 R 연산에서 4자리를 맞추기 위해 0을 채운 뒤 연산 수행
    • 그리고 반환할때는 앞의 0을 없애기

시간복잡도 계산

  • BFS연산 최대 1e4번
  • D, S 연산 : O(1)
  • L, R 연산 : O(1)

인트 계산

  • q<pair<int, string>> : 숫차 최대값이 1e4로 정해져 있어서 괜찮음

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <queue>
#include <string>
 
using namespace std;
 
 
bool chk[10010];
int main() {
 
    int T; cin >> T;
    while(T--) {
        // 메모리 초기화
        fill(chk, chk+10010, 0);
        
        int N,M; cin >> N >> M;
        queue<pair<int, string>> q;
        q.push(make_pair(N, ""));
        chk[N] = 1;
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int en = eq.first;
            string cal = eq.second;
            
            // 비교
            if(en == M) {
                cout << cal << '\n';
                break;
            }
            
            int calD =en*2%10000;
            if(chk[calD] == 0) {
                q.push(make_pair(calD, cal+"D"));
                chk[calD] = 1;
            }
            
            int calS = en-1;
            if(calS == -1) calS = 9999;
            if(chk[calS] == 0) {
                q.push(make_pair(calS, cal+"S"));
                chk[calS] = 1;
            }
            
            int cl = en%1000 * 10 + en/1000;
            if(chk[cl] == 0) {
                q.push(make_pair(cl, cal+"L"));
                chk[cl] = 1;
            }
            
            int cr = en%10 * 1000 + en/10;
            if(chk[cr] == 0) {
                q.push(make_pair(cr, cal+"R"));
                chk[cr] = 1;
            }
        }
    }
    
    return 0;
}
 
cs

문제유형

  • BFS - 최소 거리 구하기

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09

문제링크 : https://www.acmicpc.net/problem/1747


아이디어

  • 큰수에 대해 각각 소수인지, 팰린드롬인지 확인해보자
  • 예외의 수 1을 조심!!

시간복잡도 계산

  • 큰 수에 대해서 : O(N)
  • 소수인지 확인 : O(sqrt(N))
  • 팰린드롬인지 확인 : O(lg(N))
  • 총합 : O(NlgN * sqrt(N))
    • 시간 초과될것 같지만
    • 더 팰린드롬인지 확인을 먼저할경우
    • 시간복잡도를 줄일수 있음

인트 계산

  • 큰 수가 어느수까지 가는지 예상하기가 어려우니 가장 큰 수(1000000)를 입력해보고 가능한지 확인해보자

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string>
#include <cmath>
#include <climits>
 
using namespace std;
 
bool chk_pelin(int N) {
    string s = to_string(N);
    string subs = s.substr(0,(s.size()+1)/2);
    
    
    for(int i=0; i<subs.size(); i++){
        if(subs[i] != s[s.size()-1-i]) return 0;
    }
    return 1;
}
 
bool chk_prime(int N) {
    if(N==1) return 0;
    
    for(int i=2; i<=sqrt(N); i++) {
        if(N%i == 0) return 0;
    }
    return 1;
}
int main() {
    int N; cin >> N;
    
    for(int i=N; i<INT_MAX; i++) {
        if(chk_pelin(i)) {
            if(chk_prime(i)) {
                cout << i << '\n';
                return 0;
            }
        }
    }
    return 0;
    
}
 
cs

문제유형

  • 문자열 - 팰린드롬
    • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
    • 문자열 반 자른뒤 앞과 뒤가 같은지 확인 : O(N)
    • 문자열 하나에 대해 범위를 다르게 해서 팰린드롬을 확인해야하는 경우 DP 사용
      • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
      • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우 팰린드롬
      • 문자길이 1,2, 3이상일때 각각 나눠서 수행

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 10775 공항  (0) 2021.03.09

+ Recent posts

티스토리툴바