https://www.acmicpc.net/problem/2585


문제 이해를 잘못해서.. 해결하는데 엄청난 시간이 걸렸습니다.


이 문제는 (0, 0)에서 입력 받은 K이하의 노드를 거쳐서  (10000, 10000)으로 이동할 때 드는 연료의 최대값의 최솟값을 구하는 문제입니다.


(0, 0)을 A라고 가정하고 (10000, 10000)을 D라고 가정했을 때, A - B(임의의 노드)로 가는 연료가 1000이고 B - C(임의의 노드)로 가는 연료가 100이라면


A - B구간에서 1000만큼 필요했으므로 답은 1000이 나와야합니다.


이것을 모든 노드에 대해서 실행해보면 됩니다.


이분탐색을 이용해서 해당 비용만을 이용해서 (0, 0)에서 (10000, 10000) 목적지로 이동할 수 있는지를 계속해서 실행하면 됩니다.(bfs로)


코드입니다.

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
88
89
90
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
vii pos;
bool visit[(int)1e3 + 2];
 
int d(pii a, pii b) {
    int x = b.first - a.first;
    int y = b.second - a.second;
 
    return (int)ceil(sqrt(x * x + y * y) / 10);
}
 
bool bfs(int max_cost, int n, int k) {
    memset(visit, 0, sizeof(visit));
 
    queue<pii> q;
    q.push(mp(0, 0)); // from, k
 
    while (!q.empty()) {
        int from = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (from == pos.size() - 1) {
            if (cnt <= k + 1) return 1;
            else return 0;
        }
 
        for (int i = 1; i < pos.size(); i++) {
            if (visit[i]) continue;
 
            if (d(pos[i], pos[from]) <= max_cost) {
                visit[i] = 1;
                q.push(mp(i, cnt + 1));
            }
        }
    }
    
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, k;
    cin >> n >> k;
 
    pos.push_back(mp(0, 0));
 
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
 
        pos.push_back(mp(a, b));
    }
 
    pos.push_back(mp(1e4, 1e4));
 
    int left = 1, right = d(mp(0, 0), mp(1e4, 1e4));
 
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (bfs(mid, n, k)) right = mid - 1;
        else left = mid + 1;
    }
 
    cout << left;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 이분 탐색' 카테고리의 다른 글

[12842] 튀김 소보루  (0) 2017.08.23
[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19

https://www.acmicpc.net/problem/1647


이 문제는 MST로 해결할 수 있습니다.

MST라고 생각한 이유

1. 모든 집은 전부 연결되어야 한다.

2. 필요 없는 다리는 제거한다.(유지 비용이 작은 다리만 남겨둔다.)


이 두 가지 조건을 보고 MST라고 생각했습니다.

그렇다면 한 마을을 두 마을로 어떻게 나눌까요?


진짜 간단합니다.

두 마을로 나눴을 때 한쪽 마을에 집이 한 채 이상이라면 두 마을로 나눠진 것입니다.


즉, 크루스칼을 이용하여 n - 2개의 다리만 연결하면 됩니다.

왜 n - 1이 아닌 n - 2인지 설명해드리겠습니다.


우선 마을이 하나라고 생각하고 MST를 이용해 모든 집을 연결하겠지요?

그리고 두 마을로 나눠야하는데

제가 생각했을 때 어차피 최소 비용을 유지하려면 가장 유지비가 큰 다리를 제거하면 된다는 것입니다.

그래서 n - 1개를 연결하고 그 다리 중에 가장 큰 비용의 다리 하나를 제거하면 된다는 뜻이 됩니다.


근데 크루스칼은 어차피 최소 비용을 가진 것 부터 처리하므로 애초에 마지막 다리를 설치하지도 않은 채 n - 2개의 다리만

연결한다면 문제를 해결할 수 있습니다.


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
#include <iostream>
#include <vector>
#include <queue>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
int parent[MAX_SIZE];
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
 
    if (x != y) {
        parent[x] = y;
        
        return 1;
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) parent[i] = i;
 
    priority_queue < pair<int, pii> > pq;
 
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        pq.push(mp(-c, mp(a, b)));
    }
 
    int sum = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt < n - 2) {
        int cost = -pq.top().first;
        int a = pq.top().second.first;
        int b = pq.top().second.second;
        pq.pop();
 
        if (!merge(a, b)) continue;
        
        cnt++;
        sum += cost;
    }
 
    cout << sum;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 최소 스패닝 트리(MST)' 카테고리의 다른 글

[13418] 학교 탐방하기  (0) 2017.07.11

https://www.acmicpc.net/problem/1395


세그먼트 트리 lazy전파 유형입니다.

N만 작으면 비트마스크로 해결할 수 있을 것이라 생각했는데..

N도 너무 크고.. 흠.. 잘생각이 나지않았습니다.

스위치의 상태를 체크하려면 항상 그 범위만큼의 시간이 필요합니다.


하지만 lazy를 사용하면 해당 범위의 아래 부분은 나중에 업데이트를 하면 됩니다.

그리고 해당 범위의 노드에서 스위치 개수를 뒤집는 방법은

tree[node] = end - start + 1 - tree[node];

이용하면 됩니다.


범위의 개수에서 현재 on개수를 빼면 off개수가 나오기 때문이죠!


아래는 코드입니다.

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
88
89
90
#include <iostream>
#include <vector>
#include <cmath>
 
#define mp make_pair
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<int, int> vii;
typedef vector<ll, ll> vll;
 
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) {
    if (lazy[node]) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        lazy[node] = 0;
    }
}
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return tree[node];
    }
    else if (left <= start && end <= right) {
        tree[node] = end - start + 1 - tree[node];
 
        if (start != end) {
            lazy[node * 2] = !lazy[node * 2];
            lazy[node * 2 + 1] = !lazy[node * 2 + 1];
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int sum_query(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) {
        return 0;
    }
    else if (left <= start && end <= right) {
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return sum_query(tree, lazy, node * 2, start, mid, left, right) + sum_query(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    int tree_size = ceil(log2(n)) + 1;
    vi st(1 << tree_size);
    vi lazy(1 << tree_size);
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
 
        if (cmd) {
            cout << sum_query(st, lazy, 1, 1, n, a, b) << '\n';
        }
        else {
            update_range(st, lazy, 1, 1, n, a, b);
        }
    }
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[12844] XOR  (0) 2017.08.26
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

데코레이터 패턴 시간입니당!!!!!!!!!!!!!!!!


책에는 "상속맨, 디자인에 눈을 뜨다"라고 써있네요!

상속을 남용하는 전형적인 예를 살펴보고 객체 작성이라는 형식으로 실행중에 클래스를 꾸미는(데코레이터하는) 패턴을 배워볼거에욧


데코레이터 패턴을 배우면!!

원래 클래스의 코드는 전혀 바꾸지 않고도 기존의 객체에 새로운 임무를 부여할 수 있어요!


기존 코드는 건드리지 않은 채로 확장을 통해서 새로운 행동을 간단하게 추가할 수 있도록 하는게 바 로 데코레이터 패턴이죠!

새로운 기능을 추가하는 데 있어서 매우 유연해서 급변하는 주변 환경에 잘 적응할 수 있으면서도 강하고 튼튼한 디자인 !!


OCP라는 디자인 원칙이 있는데요

클래스는 확장에 대해서는 열려있어야 하며, 코드 변경에 있어서는 닫혀있어야 한다는 뜻입니다.


이제부터 제대로 시작합니당!


데코레이터 패턴!!!!!

정의 : 객체에 추가적인 요건을 동적으로 첨가한다.

데코레이터는 서브클래스를 만드는 것을 통해서 기능을 유연하게 확장할 수 있는 방법을 제공한다.


까페를 예로 들겠습니다.

상속을 써서 음료 가격과 첨가물(샷, 시럽, 우유, 휘핑 크림 등) 가격을 합한 총 가격을 계산하는 방법은 그리 좋은 방법이 아닙니다.

그 이유는

1. 클래스가 어마어마하게 많아짐.

2. 일부 서브클래스에는 적합하지 않은 기능을 베이스 클래스에 추가하게 됨.(아이스티에 휘핑크림을 추가할 필요는 없음)


그렇기 때문에 어떤 특정 음료에서 시작해서! 그 음료를 장식할겁니다.!!!!!!!!

하나의 예로 모카하고 휘핑 크림을 추가한 다크 로스트 커피를 들게요.


1. 다크로스트 객체를 가져온다.

2. 모카 객체로 장식한다.

3. 휘핑 객체로 장식한다.

4. 코스트 메소드를 호출한다. 이 때 첨가물의 가격을 계산하는 일은 해당 객체들에게 위임된다.



예제

추상클래스들을 먼저 보여드릴게용


음료 클래스

1
2
3
4
5
6
7
8
9
10
11
12
package abstract_package;
 
public abstract class Beverage {
    protected String description = "제목 없음";
    
    public String getDescription() {
        return description;
    }
    
    public abstract double cost();
}
 
cs


첨가물 클래스

1
2
3
4
5
6
package abstract_package;
 
public abstract class CondimentDecorator extends Beverage {
    public abstract String getDescription();
}
 
cs



이제 음료 클래스들과, 첨과물 클래스들을 보여드릴게요.


먼저 음료클래스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package beverage;
 
import abstract_package.Beverage;
 
public class DarkRoast extends Beverage {
    public DarkRoast() {
        description = "다크로스트";
    }
    
    @Override
    public double cost() {
        return 0.99;
    }
}
 
cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package beverage;
 
import abstract_package.Beverage;
 
public class Decaf extends Beverage {
    public Decaf() {
        description = "디카페인";
    }
 
    @Override
    public double cost() {
        return 1.05;
    }
 
}
 
cs


더 있는데 너무 많으므로 두개씩만 할게요 풀코드 보고싶은 분은 코드 다운로드해서 봐주세요


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package condiment;
import abstract_package.Beverage;
import abstract_package.CondimentDecorator;
 
public class Mocha extends CondimentDecorator {
    Beverage beverage;
    
    public Mocha (Beverage beverage) {    
        this.beverage = beverage;
    }
    
    public String getDescription() {
        return beverage.getDescription() + ", 모카";
    }
    
    public double cost() {
        return 0.20 + beverage.cost();
    }
 
}
 
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package condiment;
 
import abstract_package.Beverage;
import abstract_package.CondimentDecorator;
 
public class Whip extends CondimentDecorator{
    Beverage beverage;
    
    public Whip(Beverage beverage) {
        this.beverage = beverage;
    }
    
    public String getDescription() {
        return beverage.getDescription() + ", 휘핑";
    }
    
    public double cost() {
        return beverage.cost() + 0.10;
    }
}
 
cs



이제 메인클래스입니당.


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
import abstract_package.Beverage;
import beverage.DarkRoast;
import beverage.Espresso;
import beverage.HouseBlend;
import condiment.Mocha;
import condiment.Soy;
import condiment.Whip;
 
public class StarbuzzCoffee {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Beverage beverage[] = new Beverage[3];
 
        beverage[0] = new Espresso();
        beverage[0] = new Mocha(beverage[0]);
        beverage[0] = new Mocha(beverage[0]);
        beverage[0] = new Whip(beverage[0]);
 
        beverage[1] = new DarkRoast();
        beverage[1] = new Soy(beverage[1]);
        beverage[1] = new Mocha(beverage[1]);
 
        beverage[2] = new HouseBlend();
 
        for (int i = 0; i < beverage.length; i++) {
            System.out.println(beverage[i].getDescription() + " $" + beverage[i].cost());
        }
        
    }
}
 
cs



[출력결과]


에스프레소, 모카, 모카, 휘핑 $2.49

다크로스트, 두유, 모카 $1.3399999999999999

하우스 블렌드 커피 $0.89

1.3399999999999999



다 보고 싶으신 분은 풀 코드 다운로드하세요~~

Decorator_Pattern.jar



저작자표시

'CS기본지식 > 디자인 패턴' 카테고리의 다른 글

옵저버 패턴(Observer Pattern)  (0) 2017.08.25
스트래티지 패턴(Strategy Pattern)  (0) 2017.08.23

https://www.acmicpc.net/problem/2263


헉헉..

엄청 어렵네요!!..


pre, in, post 각각의 순회는 이해했지만,

완벽히 이해한 것은 아니였나봅니다.


이 문제는

in과 post를 이용하여 pre를 유추하는 문제입니다.


post와 in의 특징을 제대로 이해하고 있다면

O(N)의 시간으로 해결할 수 있습니다.


우선 post에 특징에 대해서 말씀드리겠습니다.


post는 Left - Right - Root 순으로 순회를 합니다.

그렇다면 우리가 받는 post input에서 가장 끝이 트리의 root라는 것을 알 수 있습니다.


예제를 예로 들면 1 3 2 로 들어오니 2가 root라는 것을 알 수 있죠.


두번째로 in의 특징입니다.

in은 Left - Root - Right 순으로 순회를 합니다.

여기서 중요한 점!은 바로 in의 input을 그대로 받는 것이 아닌 그의 위치를 저장하는 것입니다.


예제를 예로 들면

1 2 3 이라는 input이 들어오니, pos[1] = 0, pos[2] = 1, pos[3] = 2

이런 식으로 위치를 저장합니다.

그 이유는


in을 사용해서 우리는 left, right 서브트리와 root로 구분을 지을 수 있기 때문입니다.


post를 이용하여 root를 찾았고, root가 무엇인지 안다면 in에서 그 root를 기준으로 left와 right 서브트리로 나눌 수 있습니다.


이러한 과정을 분할하면서 계속 반복한다면 원래의 트리 모양을 유추할 수 있겠지요.


pre는 Root - Left - Right 이므로 위의 특징들을 이용하여 root를 찾아낸 후 출력하고 in의 root를 기준으로

left서브트리의 노드 수와 right 서브트리의 노드 수를 체크하여 post트리에 적용한 후 그 노드 수를 기준으로 나눠주면 됩니다.



코드입니다.

pos배열을 선언할 때 배열의 개수가 MAX_SIZE + 1인 이유는 input이 1~N까지 들어오기 때문입니다.(이것 떄문에 엄청 틀렸습니다.)


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int post[MAX_SIZE];
int pos[MAX_SIZE + 1];
 
void order(int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return;
 
    int root = post[pe];
    cout << root << ' ';
 
    order(is, pos[root] - 1, ps, ps + pos[root] - is - 1);
    order(pos[root] + 1, ie, ps + pos[root] - is, pe - 1);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0, in; i < n; i++) {
        cin >> in;
        pos[in] = i;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
 
    order(0, n - 1, 0, n - 1);
 
    return 0;
}
 
cs


저작자표시

'CS기본지식 > 자료구조' 카테고리의 다른 글

[C언어] 원형 큐(라운드 큐)  (0) 2017.09.07
[C언어] 우선순위 큐(Priority Queue)  (3) 2017.09.07
스택 계산기  (0) 2017.06.13
[1918] 후위표기식  (2) 2017.06.13
이중 연결 리스트  (0) 2017.04.22

https://www.acmicpc.net/problem/12844


lazy를 이용한 세그먼트 트리로 문제를 해결했습니다.-


XOR은 같은 값을 여러번하는 것은 의미없습니다.

한번하거나 안하거나와 같습니다.

홀수번 = 한번

짝수번 = 아예 안한 것


과 같기 떄문에 이 점을 이용해서 문제를 해결했습니다.


나머지 부분은 부분합 구하는 세그먼트 트리와 유사합니다.


코드입니다.

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[500000];
 
int init(vi &tree, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
    
    int mid = (start + end) / 2;
    return tree[node] = init(tree, node * 2, start, mid) ^ init(tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) { 
    if (lazy[node] != 0) {
        tree[node] ^= lazy[node] * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right, int value) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] ^= value * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= value;
            lazy[node * 2 + 1] ^= value;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, value) ^ update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, value);
}
 
int xor_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
    
    int mid = (start + end) / 2;
    return xor_range(tree, lazy, 2 * node, start, mid, left, right) ^ xor_range(tree, lazy, 2 * node + 1, mid + 1, end, left, right);
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int height = ceil(log2(n));
    vi tree(1 << (int)(height + 1));
    vi lazy(1 << (int)(height  + 1));
 
    init(tree, 1, 0, n - 1);
 
    int m; 
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        int cmd;
        int a, b, c;
        cin >> cmd;
 
        if (cmd == 1) {
            cin >> a >> b >> c;
            if (a > b) swap(a, b);
            update_range(tree, lazy, 1, 0, n - 1, a, b, c);
        }
        else {
            cin >> a >> b;
            if (a > b) swap(a, b);
            cout << xor_range(tree, lazy, 1, 0, n - 1, a, b)<< '\n';    
        }
    }
 
 
    return 0;
}
cs


저작자표시

'알고리즘 > 세그먼트트리, 펜윅트리' 카테고리의 다른 글

[1395] 스위치  (0) 2017.08.30
[2517] 달리기  (0) 2017.08.16
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

https://www.acmicpc.net/problem/12845


간단한 문제입니다.

레벨이 변하지 않으므로, 최대값의 레벨을 가진 카드의 양방향으로 더해나가면 해결되는 문제입니다.


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
int n;
int arr[(int)1e3];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    int M = 0;
    int pos;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
 
        if (arr[i] > M) {
            M = arr[i];
            pos = i;
        }
    }
 
    int ret = 0;
 
    for (int i = pos - 1; i >= 0; i--) {
        ret += M + arr[i];
    }
 
    for (int i = pos + 1; i < n; i++) {
        ret += M + arr[i];
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 구현' 카테고리의 다른 글

[3190] 뱀  (4) 2018.01.10
[2140] 지뢰찾기  (0) 2017.12.27
[12841] 정보대 등산  (0) 2017.08.23
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30


제가 보는 책입니다.

블로그는 참조만 해주시고 진짜 공부하려면

책 사는 것을 권장합니다.

진짜 좋은 책입니다.

Head First - Design Patterns 입니다.


오늘은 옵저버 패턴에 대해서 알려드릴게요!!!!


옵저버 패턴은 어떠한 이벤트가 발생했을 때 객체들에게 새소식을 전해줄 수 있는 패턴입니다.

객체 쪽에서는 계속해서 정보를 받을지 여부를 실행중에 결정할 수 있습니다.

옵저버 패턴은 JDK에서 가장 많이 쓰이는 패턴이라고 합니다.

일대다 관계 그리고 느슨한 결합 키워드를 항상 기억하세요~


옵저버 패턴 = 출판사 + 구독자

라고 생각하면 이해하기 쉬울 것 같습니다.

출판사는 subject, 구독자를 observer라고 부릅니다.


옵저버 패턴의 정의

한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식

일대다 의존성(subject에 observer들이 일대다로 연결되며, 의존함)을 정의함.

이미지 출처 클릭


옵저버 패턴을 구현하는 방법은 여러 가지가 있지만, 대부분 주제(subject) 인터페이스와 옵저버(observer) 인터페이스가 들어있는 클래스 디자인을 바탕.

옵저버 패턴은 느슨한 결합을 한다고 했는데

그럼 느슨한 결합은 무엇일까요??

두 객체가 느슨하게 결합되어 있다는 것은, 그 둘이 상호작용을 하긴 하지만 서로에 대해 서로 잘 모른다는 것을 의미합니다.

옵저버 패턴에서는 주제와 옵저버가 느슨하게 결합되어 있는 객체 디자인을 제공합니다.


왜일까요??


- 주제가 옵저버에 대해서 아는 것은 옵저버가 특정 인터페이스를 구현한다는 것 뿐입니다. 옵저버의 구상 클래스가 무엇인지, 옵저버가 무엇을 하는지 등에 대해서 알 필요가 없습니다.


- 옵저버는 언제든지 새로 추가할 수 있습니다. 주제는 Observer 인터페이스를 구현하는 객체의 목록에만 의존하기 때문에 언제든지 추가/삭제를 할 수 있습니다.


- 새로운 형식의 옵저버를 추가하려고 해도 주제를 전혀 변경할 필요가 없습니다. 옵저버가 되어야 하는 새로운 구상 클래스가 생겼다고 가정하면, 새로운 클래스 형식을 받아들일 수 있도록 주제를 바꿔야할 필요는 없습니다. 새로운 클래스에서 Observer 인터페이스를 구현하고 옵저버로 등록하기만 하면 됩니다. 주제 객체는 전혀 신경도 쓰지 않습니다. subject는 Observer 인터페이스만 구현한다면 어떤 객체에든지 연락을 하기 때문입니다.


- 주제와 옵저버는 서로 독립적으로 재사용할 수 있음. 주제나 옵저버를 다른 용도로 활용할 일이 있다고 해도 손쉽게 재사용할 수 있음. 그 둘이 서로 단단하게 결합되어 있지않기 때문(느슨한 결합)


- 주제나 옵저버가 바뀌더라도 서로한테 영향을 미치지는 않습니다. 둘이 서로 느슨하게 결합되어 있기 때문에 주제 혹은 옵저버 인터페이스를 구현한다는 조건만 만족된다면 어떻게 바꿔도 문제가 없습니다.


서로 상호작용을 하는 객체 사이에서는 가능하면 느슨하게 결합하는 디자인을 사용해야 한다.

느슨하게 해야하는 이유는 느슨한 결합을 사용하면 변경 사항이 생겨도 무난히 처리할 수 있는 유연한 객체지향 시스템을 구축할 수 있기 때문입니다. 객체 사이의 상호의존성을 최소화해야 합니다.



옵저버 패턴 코드 다운로드

코드에는 푸시와 풀 방식이 들어있습니다.

푸시는 subject와 observer를 인터페이스로 구현했고, 풀은 java.util의 observer와 observable을 import했습니다.


푸시방식에서는 notify를 하면 직접 subject 쪽에서 observer들을 update하지만

풀방식에서는 setChanged() 함수를 이용하여 데이터가 변했음을 알려주고,

notifyObservers()를 호출하는데 이는 데이터를 푸시하는 것이 아닌

옵저버 측에서 get함수를 이용하여 데이터를 가져다 쓰는 것입니다.


java.util.observable의 단점

- 이는 인터페이스가 아닌 클래스입니다. 그러므로 구현과 재사용성에 있어서 제약조건이 많습니다.

클래스이기 때문에 서브클래스를 만들어야하는데 이미 다른 클래스를 상속하고 있다면 다중상속이 되므로

Observable기능을 사용할 수 없습니다.


- 또한 인터페이스가 아니기 때문에 직접 구현하는 것이 불가능합니다. java.util 구현을 다른 구현으로 바꾸는 것은

불가능합니다.


- Observable 클래스의 핵심 메소드를 외부에서 호출할 수 없습니다. setChanged() 메소드는 protected로 되어있기 때문에 서브클래스에서만 호출이 가능합니다.

저작자표시

'CS기본지식 > 디자인 패턴' 카테고리의 다른 글

데코레이터 패턴(Decorator Pattern)  (0) 2017.08.28
스트래티지 패턴(Strategy Pattern)  (0) 2017.08.23

+ Recent posts

티스토리툴바