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


아이디어

  • 백트래킹 - 조합 : 백트래킹 리스트 중 마지막것 다음부터 순회하며 백트래킹 수행

시간복잡도 계산

  • 10^N : 1e8 > 가능

자료구조

  • 백트래킹 리스트 : vector
    • 최대값 : 8이하의수 > INT 가능

코드(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
#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> v;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    //리스트 중 마지막것 다음부터 순회하며 백트래킹 수행
    int last = 0;
    if(!v.empty()) last = v.back();
    
    for(int i=last+1; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

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

백준 15652 N과 M (4)  (0) 2021.03.15
백준 15651 N과 M (3)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14

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

아이디어

  • 백트래킹 - 순열
    • 이전값 중복체크만 해주면 됨

시간복잡도 계산

  • 백트래킹 : 10^N : 1e8 > 가능

자료구조

  • 백트래킹 vector

    • 최대 수 : 8이하 > INT 가능

코드(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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> v;
bool chk[10];
int N,M;
 
void dfs() {
    // 개수 가득 차면 출력
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    for(int i=1; i<=N; i++) {
        if(chk[i]) continue;
        chk[i] = 1;
        v.push_back(i);
        
        dfs();
        
        chk[i] = 0;
        v.pop_back();
        
    }
}
 
int main() {
    fill(chk, chk+10, 0);
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

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

백준 15651 N과 M (3)  (0) 2021.03.15
백준 15650 N과 M (2)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14

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


아이디어

  • 이전에 계산한 값을 재활용 할 수 있음 > DP
    • 각 조건이 복잡하니까 2차원 DP로
    • DP[Y][X] : Y위치에서 X가 0이면, 이전에 한칸으로 온 경우, 1이면 이전에 2칸으로 온 경우
    • DP[Y][0] = DP[Y-1][1]
    • DP[Y][1] = max(DP[Y-2][0], DP[Y-2][1])
  • 초기값 설정
    • DP[1][0] = map[1]
    • DP[1][1] = 0
    • DP[2][0] = map[1] + map[2]
    • DP[2][1] = map[2];
      • DP[N][0], DP[N][1] 중 큰값 출력

시간복잡도 계산

  • O(N * 2)

자료구조

  • map[Y] : 계단 최대 1e4 > INT 가능
  • DP[Y][X] :
    • 최대값 : 1e4 * 300 = 3e6 > INT 가능

코드(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
#include <iostream>
 
using namespace std;
 
int map[310];
int dp[310][2];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0], &dp[309][2], 0);
    int N; cin >> N;
    for(int i=1; i<=N; i++) cin >> map[i];
    
    dp[1][0] = map[1];
    dp[1][1] = 0;
    
    dp[2][0] = map[1] + map[2];
    dp[2][1] = map[2];
    
    
    for(int i=3; i<=N; i++) {
        dp[i][0] = dp[i-1][1] + map[i];
        dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + map[i];
    }
    
    cout << max(dp[N][0], dp[N][1]) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 케이스 2차원 DP : 조건이 복잡할 때, 각 케이스에서의 dp

비슷한 문제

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

백준 15650 N과 M (2)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15
백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14

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


아이디어

  • BFS를 사용해서 지훈이와 불을 각각 하나씩 이동해주자
  • 이떄 지훈이가 밖으로 넘어가면 종료

시간복잡도 계산

  • BFS(V+E)
    • V : O(RC)
    • E : O(RC*4)
    • 총합 : O(RC)

자료구조

  • map[1000][1000]
  • BFS queue<pair<int, int>>
    • 좌표 최대 1000
  • 시간 t : 최대 1000

코드(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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
char map[1010][1010];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pi2> jihoon;
    queue<pi2> fire;
    
    int R,C; cin >> R >> C;
    for(int j=0; j<R; j++) {
        for(int i=0; i<C; i++) {
            cin >> map[j][i];
            if(map[j][i] == 'J') jihoon.push(make_pair(j,i));
            else if(map[j][i] == 'F') fire.push(make_pair(j,i));
        }
    }
    
    int t=0;
    while(1) {
        t++;
        // 지훈 먼저 이동
        int jsize = jihoon.size();
        if(jsize == 0) break;
        
        while(jsize--) {
            auto ej = jihoon.front(); jihoon.pop();
            int ey = ej.first;
            int ex = ej.second;
            
            // 만약 현재 위치가 불이라면 이동불가
            if(map[ey][ex] == 'F') continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                // 탈출하면 종료
                if(!(ny>=0 && ny < R && nx >=0 && nx < C)) {
                    cout << t << '\n';
                    return 0;
                }
                
                // .일떄만 이동
                if(map[ny][nx] == '.' ) {
                    map[ny][nx] = 'J';
                    jihoon.push(make_pair(ny, nx));
                }
            }
            
        }
        
        // 불 이동
        int fsize = fire.size();
        while(fsize--) {
            auto ef = fire.front(); fire.pop();
            int ey = ef.first;
            int ex = ef.second;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
 
                if(ny>=0 && ny < R && nx >=0 && nx < C) {
                    if(map[ny][nx] == 'J' || map[ny][nx] == '.') {
                        map[ny][nx] = 'F';
                        fire.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        
        
    }
    
    cout << "IMPOSSIBLE";
    
    return 0;
}
 
cs

문제유형

  • BFS - 경찰과 도둑
    • 경찰은 쫓고, 도둑은 탈출
    • bfs로 맵을 인자로하면 메모리 차지가 너무크므로, 경찰, 도둑 좌표를 인자로

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

백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14

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


아이디어

  • 최소비용으로 목적지에 도착해야함 >> 다익스트라
  • 다익스트라 알고리즘 내에서 간선을 통해서 이동한 값이 더 작을경우 갱신

시간복잡도 계산

  • 다익스트라 알고리즘 : O(ElgE)
    • 여기서 E : N^2 * 4
    • O(N^2 * lg N^2)

자료구조

  • 현재 거리값 dist : 최대값 N^2 * 10 = 2e5
  • 전체 지도 map : 최대값 10

코드(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
61
#include <iostream>
#include <queue>
#include <tuple>
 
using namespace std;
typedef tuple<int, int, int> ti3;
 
int dist[150][150];
int map[150][150];
const int inf = 3e5;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=0;
    while(1) {
        
        fill(&dist[0][0], &dist[149][150], inf);
        
        int N; cin >> N;
        if(N==0) break;
        
        for(int j=0; j<N; j++) {
            for(int i=0; i<N; i++) {
                cin >> map[j][i];
            }
        }
        
        priority_queue<ti3, vector<ti3>, greater<ti3>> pq;
        
        // 출발점
        dist[0][0] = map[0][0];
        pq.push({dist[0][0], 0, 0});
        
        while(!pq.empty()) {
            int ec, ey, ex;
            tie(ec,ey,ex) = pq.top(); pq.pop();
            
            if(dist[ey][ex] != ec) continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny >= 0 && ny < N && nx >= 0 && nx < N) {
                    if(dist[ny][nx] > dist[ey][ex] + map[ny][nx]) {
                        dist[ny][nx] = dist[ey][ex] + map[ny][nx];
                        pq.push({dist[ny][nx], ny, nx});
                    }
                }
            }
        }
        
        t++;
        cout << "Problem " << t << ": " << dist[N-1][N-1] << '\n';
    }
    
    
    return 0;
}
cs

문제유형

  • 2차원 다익스트라
    • 목적지 도착하는데 최소 비용 문제
    • 현재 비용 표시되는 배열 추가해서, 현재보다 작으면 업데이트

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

백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13

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


아이디어

  • BFS 사용해서 연결된 노드 구하기(Flood Fill)
    • 전체 노드 순회하면서 체크 안되어있는 노드 발견할경우 BFS 수행
      • 이떄마다 전체 그림 카운트 수 증가
      • 그리고 그림 가장 넓은값 구하기

시간복잡도 계산

  • BFS : O(V+E)
    • V : 모든 노드수 : O(NM)
    • E : 노드에서 간선수 4방향 : O(4NM)
    • N과 M 최대값이라고 가정시
    • 총합 : O(5N^2)
      • O(5*N^2) = 5 * 25e4 : 125e4 = 1.25e6

자료구조

  • 그림 개수 cnt : 최대 N^2 = 25e4 : INT 가능
  • 그림 최대 크기 maxv : 최대 N^2 = 25e4 : INT 가능
  • BFS에서 사용하는 큐 queue<pair<int, int>>

코드(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
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <queue>
 
using namespace std;
 
int map[510][510];
bool chk[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int N,M;
 
int bfs(int y, int x) {
    int cnt=0; // 그림 크기
    
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    chk[y][x] =1;
    
    while(!q.empty()) {
        auto eq = q.front(); q.pop();
        int ey = eq.first;
        int ex = eq.second;
        cnt++; // 그림 크기 증가
        
        for(int k=0; k<4; k++) {
            int ny = ey + dy[k];
            int nx = ex + dx[k];
            if(ny>=0 && ny < N && nx>=0 && nx < M) {
                if(map[ny][nx] == 1 && chk[ny][nx] == 0) {
                    chk[ny][nx] = 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
    
    return cnt;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&chk[0][0], &chk[509][510], 0);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    int cnt=0;
    int maxv= 0;
    
    // 체크되어있지 않은 경우 bfs 수행
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(map[j][i] == 1 && chk[j][i] == false) {
                maxv = max(maxv, bfs(j,i));
                cnt++;
            }
        }
    }
    
    cout << cnt << '\n';
    cout << maxv << '\n';
    
    
    return 0;
}
 
cs

문제유형

  • BFS - Flood Fill
    • 이어져있는 노드를 연결하는 문제
    • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

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

백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13

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


아이디어

  • N번째까지 순회하면서 숫자를 확인
  • 순회할때 조건
    • 1자리수는 통과
    • 자리수 올라갈떄, 10 곱한뒤에, 가장 마지막 수보다 작은것들만 추가
    • 그럼 이전에 감소한 수를 재사용해야함 > 큐를 사용해서 이전에 계산한 값 넣어주기
  • 일의 자리 일때 조심!

시간복잡도 계산

  • N까지 순회 : O(N)
  • 마지막 일의자리 10개 순회 : O(10)

자료구조

  • queue <long long>
    • 최대 숫자 될수 있는수 10자리 > long long 사용
    • 감소하는 수이기 때문에 숫자가 총 10개

코드(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
#include <iostream>
#include <queue>
 
using namespace std;
typedef long long ll;
 
int main() {
    int N; cin >> N;
    
    // 1의 자리 미리 출력
    // 큐에 넣은 후 출력하려고하면 복잡해짐
    if(N <=9) {
        cout << N << '\n';
        return 0;
    }
    
    queue<ll> q;
    for(int i=0; i<=9; i++) q.push(i);
    
    int cnt=9;
    
    while(!q.empty()) {
        ll eq = q.front(); q.pop();
        
        // 일의자리 구해서 작은수까지 순회
        int lastNum = eq%10;
        for(int i=0; i<lastNum; i++) {
            
            ll ev = eq*10 + i;
            q.push(ev);
            cnt++;
            if(cnt==N) {
                cout << ev << '\n';
                return 0;
            }
        }
    }
    
    cout << -1 << '\n';
    
    return 0;
}
 
cs

문제유형

  • 브루트포스 - 큐
    • 특정 순번의 값을 확인해야할때
    • 이전에 사용한 값을 재활용 할수 있을 때
    • 큐에 넣고, 뽑으면서 다음 값을 구함

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

백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13

세줄 정리

  • 상태에 따라서 다르게 동작해야할 때
  • 케이스가 추가될 때마다 코드를 수정하는 것이 복잡해짐
  • 상태를 각각의 클래스로 만들고, 각 상태에서 메서드를 제공

디자인 패턴 적용 안한경우

단점

  • if else 구문을 사용하기 때문에, 상태가 추가될 경우, VendingMachine 클래스 수정해줘야함
    (이를 개방 폐쇄의 원칙에 어긋난다고 합니다.)
  • if else 구문을 추가해주고, 그때의 메소드를 추가

상황

  • 자판기 소프트웨어에서
  • 제품이 판매 가능하면 상품이 나오고,
  • 제품이 매진되었으면 상품이 나오지 않고 빨간 불빛을 표시

if else로 구현할 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class VendingMachine {
private String state = “AVAILABLE”; // SOLDOUT or AVAILABLE
    
    public void select() {
        if(state.equals(“AVAILABLE”)) provideProduct();
        else if(state.equals(“SOLDOUT”)) redRight();
    }
 
    private void provideProduct() {
        ...
    }
 
    private void redRight() {
        ...
    }
}
 
cs

제품이 한개 남았을때는 초록색 불빛 기능 추가 될때

1
2
3
4
5
6
7
8
9
10
11
public class VendingMachine {
private String state = “AVAILABLE”; // SOLDOUT or AVAILABLE or ONELEFT
    
    public void select() {
        if(state.equals(“AVAILABLE”)) provideProduct();
        else if(state.equals(“SOLDOUT”)) redRight();
        else if(state.equals(“ONELEFT”)) greenRight();
    }
 
}
 
cs

상태 패턴

State Pattern UML

개념

  • 각각의 상태 객체가 기능을 제공
  • 콘텍스트는 상태 객체를 가지고, 상태 객체에서 기능을 실행

장점

  • 상태가 많아져 클래스 개수는 증가하지만, 코드의 복잡도는 증가하지 않음
  • 상태별 동작을 수정하기가 쉬움
    • if else의 경우 각각의 상태에서 실행하는 메소드를 찾아서 수정해줘야함

VendingMachine(Context)

1
2
3
4
5
6
7
8
9
10
11
12
public class VendingMachine {
    private State state;
 
    public VendingMachine(State state) {
        this.state = state;
    }
 
    public void select() {
        state.select();
    }
}
 
cs

상태 인터페이스

1
2
3
4
public interface State {
    public void select();
}
 
cs

상태 인터페이스 구현한 상태 클래스

1
2
3
4
5
6
7
8
9
10
11
public class AvailableState implements State {
    @Override
    public void select() {
        provideProduct();
    }    
 
    private void provideProduct() {
        ...
    }
}
 
cs

상태 패턴 vs 전략 패턴

사전지식 : 전략패턴

두 패턴 모두 각각의 상황에 따라서 다른 동작을 할때, 각 상황을 별도의 클래스로 다루는 것이 동일하다
상태 패턴의 경우 상태를 클래스로 다루고, 전략 패턴은 전략을 클래스로 다룬다는 것이 동일하다
하지만, 결국 두개가 같은게 아닐까? 라는 의문이 들었고, 찾아본 결과 답은 다음과 같다.

상태 패턴은 상태 객체에서 상태를 바꿀 수 있고, 전략 패턴은 불가능하다

상태 패턴을 먼저 살펴보자. 위의 예제에서 ONELEFT(음료수 하나 남은 상황) 상태에서 자판기에서 음료수를 뽑는다면, 상태가 SOLDOUT으로 바뀌어야한다. (위 코드에서 구체적으로 구현하지는 않았다… 여러분의 이해를 돕기위해서 ㅎㅎ) 이와 같이 상태패턴은 상태 객체에서, 콘텍스트 객체의 상태 변경까지 포함한 개념이다.

전략 패턴을 보자.
별도의 상태를 관리하지 않고, 한번 전략이 선택되면 실행되고 끝이다. 바뀌지 않는다.
예를들면, 고객의 등급에 따라 다른 할인 혜택을 적용할경우

정리하자면,

  • 공통점 : 상태 패턴과 전략 패턴은 각각 상태와 전략을 객체화 해서 관리
  • 차이점 : 상태 패턴은 상태를 관리하고, 전략 패턴은 전략을 관리하지 않음

출처

- https://defacto-standard.tistory.com/47

- https://en.wikipedia.org/wiki/State_pattern

- 개발자가 반드시 정복해야할 객체 지향과 디자인 패턴(최범균 저) Ch.07

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

[디자인 패턴] 템플릿 메서드 패턴(Template Method Pattern)  (0) 2021.03.13
[디자인 패턴] 전략 패턴(Strategy Pattern)  (0) 2021.03.13

세줄 정리

  • 상속을 통해 상위 클래스의 기능 확장할때 사용하는 대표적 방법
  • 전체 흐름은 동일한데 일부 기능이 다른 경우, 템플릿 메서드 정의 후 상속받은 클래스에서 다른 메서드 정의
  • 자바에서는 추상클래스를 사용해서 구현
    template method pattern uml

예시

상황

  • 손님이 결제를 할때 현금, 카드로 계산하는 경우
  • 결제수단을 받아오고 돌려주는 방법은 똑같음
  • 하지만 현금이냐, 카드냐 결제 하는 방법이 다름

추상클래스 Calculator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public abstract Calculator {
 
    // 탬플릿 메서드
    public void pay(int price) {
        takePayment(); // 결제 수단 받아옴
        doPayment(); // 결제 수행
        returnPayment(); // 결제 수단 돌려줌
        
    }
 
    protected void takePayment() {
        ...
    }
 
    protected void doPayment() {
        ...
    }
 
 
    // 클래스마다 달라지는 부분
    protected abstract void doPayment();
    
}
 
cs

클래스 CashCalculator

1
2
3
4
5
6
7
public class CahCalculator extends Calculator {
    @Override
    protected void doPayment() {
        ...
    }
}
 
cs

특징

특징1. 부모 클래스가 흐름 제어

  • 템플릿 메서드 패턴은 부모 클래스의 템플릿 메서드가 자식 클래스의 메서드를 호출
  • 일반적인 경우, 자식 클래스가 흐름 제어(자식 클래스가 부모 클래스 기능 재사용할지 결정)
  • 예시 : SuperCar 클래스의 turnOn() 메소드는 부모 클래스의 turnOn() 재사용 여부를 결정
1
2
3
4
5
6
7
public class SuperCar extends ZetEngine {
    @Override
    public void turnOn() {
        if(notReady) beep();
        else super.turnOn(); // 자식 클래스에서 부모 클래스 기능 재사용여부 결정
    }
}
cs

특징2. 템플릿 메서드 접근제어자

  • 템플릿 메서드 안에서, 자식 클래스마다 달라지는 메서드의 경우 하위 타입에서만 재정의 할수 있어야해서 protected 사용

특징 3. hook 메소드

  • hook 메서드
    • 부모클래스에서 default 기능을 정의해두거나, 비워둬서
    • 자식클래스에서 오버라이드 하도록 만들어준 메소드
  • 자식 클래스마다 달라지는 메서드의 경우, 기본구현을 제공할 수도 있고 안할수도 있는데
  • 기본구현을 제공하는 메서드를 hook 메서드라고 함

자바에서 사용하는 경우 : AbstractMap<K,V> 클래스

  • HashMap, TreeMap은 AbstractMap을 상속받아 구현하며
  • AbstractMap(추상클래스)는 Map 인터페이스를 implements해서 get 메소드 구현해야함
  • AbstractMap 상속받은 HashMap, TreeMap은 get() 메소드 가지지만 자신만의 구현방법으로 다르게 구현되어있음

출처

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

[디자인 패턴] 상태 패턴(State Pattern)  (0) 2021.03.13
[디자인 패턴] 전략 패턴(Strategy Pattern)  (0) 2021.03.13

세줄 정리

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

다이어그램

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

+ Recent posts

티스토리툴바