어휴.. 엄청 어렵네요..


이분 매칭일 것이라고 생각은 했는데


어떻게 적용해야할까?가 문제였습니다.


중복되는 강의를 제외하고 어떻게 연결을 하지.. 라는 엄청난 고민...


나는 바보였다!!!!!!!!!!!!...


중복된 과목끼리 선을 만들어서 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
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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
 
#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, m;
 
vi edge[2001];
bool visit[2001];
 
int A[2001];
int B[2001];
 
vi vi_left;
 
bool f(int idx) {
    visit[idx] = 1;
 
    for (int i = 0; i < edge[idx].size(); i++) {
        int to = edge[idx][i];
 
        if (!B[to] || (!visit[B[to]] && f(B[to]))) {
            B[to] = idx;
            A[idx] = to;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        int a;
        char major;
 
        cin >> a >> major;
        
        if (major == 'c') {
            vi_left.push_back(a);
        }
    }
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    int ret = n;
 
    for (int i = 0; i < vi_left.size(); i++) {
        memset(visit, 0, sizeof(visit));
 
        ret -= f(vi_left[i]);
    }
 
    cout << ret;
 
    return 0;
}
cs


저작자표시

'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[1671] 상어의 저녁식사  (0) 2017.07.02
[1017] 소수 쌍  (0) 2017.06.27
[6086] 최대유량  (1) 2017.06.03

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


흠.. 딱 보자마자!

이분탐색이 떠올랐습니다.


왜냐하면.. 그만큼 빵을 먹는데 걸린 시간을 알아야 한다고 생각했기 때문입니다.


그래서 이분 탐색으로 빵을 먹는데 걸린 가장 근접한 시간을 구합니다.


그거까진 어렵지 않았는데..

문제는

누가 먹었는지 유추하는 부분이었습니다.


문제의 예제를 보면

3명이 25개를 먹는데 걸리는 시간은 15초가 걸립니다.


그 이유는


1번은 1초

2번은 3초

3번은 5초라고 입력이 들어왔는데


15초면 1번은 16개를 먹을 수 있고

2번은 6개

3번은 4개


이렇게해서 총 26개를 먹을 수 있습니다.


1000-975는 25인데 26개를 먹으면 안되지 않나요??

네 맞습니당!

25개만 먹어야합니다.


그러면 14초를 한번 예로 들어볼까요

1번은 15개

2번은 5개

3번은 3개 

이렇게 총 23개를 먹을 수 있죠

그렇기 때문에 가장 근접한 시간은 15초입니다.


여기서 저는 나머지를 이용하여 해당 시간에 가장 근접한 집합을 구했습니다.

15초일 때 가장 근접한 집합은 1,2,3번 셋다 가능합니다.

3명 다 먹는 시간이 나누어 떨어지기 때문입니다.


그래서 15초에 총 먹은 수 26개에서 우리가 25개를 빼고

그 집합의 끝에서 찾아보면 답을 얻을 수 있습니다.


집합의 크기는 3(1, 2, 3) 그리고 15초에 먹은 수 26 - 우리가 구해야하는 수 25

1이 나오죠!


집합의 오른쪽부터 1이동한 정답은 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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#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 t[(int)1e5];
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, tmp;
    cin >> n >> tmp;
    n -= tmp;
 
    int k;
    cin >> k;
 
    for (int i = 0; i < k; i++) {
        cin >> t[i];
    }
 
    int left = 0, right = 1e5;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        int eat = 0;
 
        for (int i = 0; i < k; i++) {
            eat += mid / t[i] + 1;
        }
 
        if (eat >= n) right = mid - 1;
        else left = mid + 1;
    }
 
    //left시간
    vi ret;
    int sum = 0;
    int v = 1e3; // 가장 근접한 나머지 값
 
    for (int i = 0; i < k; i++) {
        int rest = left % t[i];
        sum += left / t[i] + 1;
 
        if (rest < v) {
            ret.clear();
            ret.push_back(i + 1);
            v = rest;
        }
        else if (rest == v) ret.push_back(i + 1);
    }
 
    sum -= n; // left초 동안 먹은 빵의 양에서 우리가 구하고자 하는 빵의 양을 뺌
 
    cout << ret[ret.size() - 1 - sum]; // 백터의 끝에서 sum을 빼주면 답을 얻을 수 있음.
 
    return 0;
}
 
cs


저작자표시

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

[2585] 경비행기  (0) 2017.08.30
[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/12841


단순 구현? 일 것 같습니다.


횡단보도를 한 번만 할 수 있다?


즉. 왼쪽길로 쭉 가다가 횡단보도 한번 건너서 오른쪽 길로 쭉 갈 수 밖에 없습니다.

여기서 두가지 예외는 왼쪽 길로 아예 안가고 횡단 보도를 바로 건너서 오른쪽 길로 쭉 가는 방법과

왼쪽 길로 쭉 가서 횡단 보도를 건너서 정보대에 도착하는 방법이 있는데

사실 예외라고 하기엔.. 예외처리를 안해줘도 되기 때문에....ㅎㅎ...



그림으로 표현하면 이렇습니다!

빨간색길과 검은색길 초록색 길!


다 같은 말이죠


그렇다면 i번째에서 횡단보도를 건너는 거리의 식은


거리i = i번째 까지의 왼쪽 길 연속 합 + 횡단 보도 i의 거리 + 1부터 정보대까지의 오른쪽 거리 - 1부터 i까지의 거리


입니다.!


코드는 아래와 같습니다.


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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
#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 cross[MAX_SIZE + 1];
ll edge[MAX_SIZE + 1][2];
 
int main() {
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) cin >> cross[i];
 
    for (int i = 0; i < 2; i++) {
        for (int j = 2; j <= n; j++) {
            cin >> edge[j][i];
            edge[j][i] += edge[j - 1][i];
        }
    }
 
    ll ret = 1e16;
    int idx = 0;
 
    for (int i = 1; i <= n; i++) {
        ll tmp = edge[i][0] + cross[i] + edge[n][1] - edge[i][1];
 
        if (tmp < ret) {
            ret = tmp;
            idx = i;
        }
    }
 
    cout << idx << ' ' << ret;
 
    return 0;
}
 
cs


저작자표시

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

[2140] 지뢰찾기  (0) 2017.12.27
[12845] 모두의 마블  (0) 2017.08.26
[1700] 멀티탭 스케줄링  (0) 2017.08.01
[1992] 쿼드 트리  (0) 2017.07.30
[14488] 준오는 급식충이야!  (0) 2017.07.29


제가 보는 책입니다.

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

책 사는 것을 권장합니다.

진짜 좋은 책입니다.

Head First - Design Patterns 입니다.


Strategy_Pattern.jar

아래에서 설명할 스트래티지 패턴의 예제입니다.

다운로드 받으시고 실행하시면 좀 더 이해하기 수월하실 겁니다.

자바파일입니다.


문제의 시작

어떤 팀은 성공적인 오리 연못 시뮬레이션 게임을 만들었다.

이 게임에서의 오리는 헤엄도 치고 꽥꽥거리는 소리도 내는 매우 다양한 오리 종류를 보여줄 수 있다.

처음으로 이 오리를 디자인한 사람들은 Duck이라는 수퍼클래스를 만들었고,

Duck 클래스를 확장하여 다른 종류의 오리들을 만들었다.


Duck클래스에는 quack(), swim(), display()등의 메소드가 존재한다.


이제 오리들을 날아다닐 수 있게 하고 싶다.

그렇다면!


어떻게 해결해볼까??

수퍼클래스인 Duck클래스에 fly() 메소드를 추가하면 되지 않을까??

정말 간단하다.


하지만 문제가 발생했다. 날 수 있는 오리도 있지만, 날지 못하는 오리 인형 같은 것들이 날라다니기 시작한 것이다.

수퍼클래스에 fly() 메소드가 추가되면서 일부 서브클래스에는 적합하지 않은 행동이 전부 추가된 것이다.


상속을 활용하여 코드를 재사용할 수 도 있지만 이런 부작용이 발생할 수 있다.


오리 종류마다 quack()메소드(울음 소리)를 오버라이드 한 것처럼 fly() 메소드 또한 오버라이드하면 되지않을까!?

오리 인형은 아무 동작도 하지않게 오버라이드하면 되겠다!


하지만 이 방법 또한 문제가 많다.

오리의 종류마다 오버라이드를 한다면 모든 오리의 행동을 알기 힘들다는 것이다.

또한, 런타임 도중에 오리의 특징을 바꾸기도 힘들다.


인터페이스는 어떨까???

fly() 메소드를 Duck 수퍼클래스에서 빼고 fly() 메소드가 들어가있는 Flyable 인터페이스를 만든다면!

하늘을 나는 오리에 대해서만 이 인터페이스를 구현하여 fly() 메소드를 집어넣으면 되겠다!!!!


모든 오리들이 꽥꽥 우는 것도 아니니 Quackable이라는 인터페이스를 같이 만들어보자!


으악.. 이 방법도 문제가 있다.

서브클래스에서 이 인터페이스들(Flyable, Quackable)을 구현한다면 날거나 울음 소리에 대해 전부 오버라이딩을 해야하므로

코드의 재사용을 전혀 할 수 없다.

100가지의 오리 종류가 있다면 100가지 모두 일일이 다 구현해야하는 것이다.


진짜 어떻게 해결해야하지??ㅠ_ㅠ

이 상황에 가장 어울리는 디자인 원칙이 있다.


애플리케이션에서 달라지는 부분을 찾아내고, 달라지지 않는 부분으로부터 분리하라.


코드에 새로운 요구사항이 있을 때마다 바뀌는 부분이 있다면, 바뀌지 않는 다른 부분으로부터 골라내서 분리해야한다는 말이다.

바뀌는 부분은 따로 뽑아서 캡슐화한다면, 바뀌지 않는 부분에는 영향을 미치지 않은 채로 그 부분만 고치거나 확장할 수 있다.

모든 패턴은 시스템의 일부분을 다른 부분과 독립적으로 변화시킬 수 있는 방법을 제공하기 위한 것이다.


수퍼클래스 Duck에서 fly()와 quack()을 제외하면 다른 부분은 잘 작동한다.

그렇다면 달라지는 부분인 fly()와 quack()을 분리하여 새로운 집합을 만들어보자.


그리고 Duck()의 행동을 동적으로 혹은 유연하게 바꿀 수 있도록, fly와 quack부분에 대해 setter 메소드를 포함하자.


두번째 디자인 원칙!


구현이 아닌 인터페이스에 맞춰서 프로그래밍한다.


여기서 말하는 인터페이스는 자바의 인터페이스라기 보다는 객체가 코드에 의해서 고정되지 않도록, 어떤 상위 형식에 맞춰서 프로그래밍함으로써

다형성을 활용해야한다는 것이다.

그리고 상위 형식에 맞춰서 프로그래밍하라는 원칙은 변수를 선언할 때는 보통 추상 클래스나 인터페이스 같은 상위 형식으로 선언해야 한다는 말이다.

이렇게 하는 이유는 객체를 변수에 대입할 때 상위 형식을 구체적으로 구현한 형식이라면 어떤 객체든 집어넣을 수 있기 때문이다.

또한, 이렇게 하면 변수를 선언하는 클래스에서 실제 객체의 형식을 몰라도 된다.


예를 들어..


Dog d = new Dog();

d.bark();


이렇게 한다면 구체적인 구현에 맞춰서 코딩을 해야한다.

하지만 상위 형식에 맞춰 코딩한다면??


Animal animal = new Dog();

animal.makeSound();


Dog라는 걸 알고 있긴 하지만 다형성을 활용하여 Animal에 대한 레퍼런스를 써도 된다는 말이다.


더 바람직한 방법은 인스턴스를 만드는 과정을 new Dog()처럼 직접만드는 대신 구체적으로 구현된 객체를 실행시에 대입하는 것이다.


a = getAnimal();

a.makeSound();


Animal의 하위 형식 가운데 어떤 형식인지 몰라도 makeSound()에 대해 올바른 반응을 할 수 있다.


어쨋든!!

위에서 분리한 fly와 quack을 인터페이스로 FlyBehavior 와 QuackBehavior로 구현을 하고 

그 인터페이스 안에 FlyWithWings, FlyNoway 그리고 Quack, Squeak, MuteQuack으로 구체적인 행동을 하는 클래스를 만든다.


이런 식으로 디자인하면 다른 형식의 객체에서도 나는 행동과 꽥꽥거리는 행동을 재사용할 수 있다.

그런 행동이 더 이상 Duck클래스 안에 숨겨져 있지 않기 때문이다.


그리고 기존의 행동 클래스를 수정하거나 날아다니는 행동을 사용하는 클래스는

Duck클래스를 전혀 건드리지 않고도 새로운 행동을 추가할 수 있다.


이렇게 한다면 상속을 쓸 때 떠안는 부담을 전부 떨쳐 버리고 코드 재사용의 장점을 그대로 누릴 수 있다.


이 패턴이 바로 스트래티지 패턴이다!


스트래티지 패턴의 정의는! 바로바로!


알고리즘군을 정의하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만든다.

스트래티지 패턴을 활용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있다!

저작자표시

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

데코레이터 패턴(Decorator Pattern)  (0) 2017.08.28
옵저버 패턴(Observer Pattern)  (0) 2017.08.25

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


와우.. 이 문제 진짜로~ 어렵네요!


진짜 가장 중요한 힌트는 달리기 실력을 상대적인 값으로 바꾸는 것입니다.

다른 분들이 푸신 방법들을 봐도 설명이 상세히 안나와있고.. 코드만 봤을 때는 잘 이해가 안가더라구요.


제가 푼 방법은 런타임 속도는 상대적으로 느리지만 좀 직관적으로 해결했습니다.


상대적으로 바꾸는 이유는 달리기 실력 값이 1 ~ 10^9까지 존재하기 때문에 이 값대로 트리를 형성할 수 없기 때문입니다.

우선 N은 3이상 5 * 10^5이므로 실력의 절대값으로 순위를 매겨서 상대적인 값으로 변환합니다.

순위를 매길 때 저는 정렬을 이용했습니다.


그리고 실력을 상대적인 값으로 바꾼 후에 다시 입력받은 순으로 정렬을 합니다.

그 다음에 트리를 생성하는데요!

세그먼트 트리이므로 tree(1 << ((int)ceil(log2(n)) + 1))!!!

이 뜻이 무엇이냐면 ceil이 어떤 값보다 크거나 같은 수를 찾는 함수인데요

예를 들어서 n = 1024라면 log2를 씌우면 10이라는 값이 나옵니다.

ceil(10)은 10이겠지요

1025를 넣는다면 10.xxxx가 나올 것입니다.

이것 또한 10이 나옵니다.!


무튼 ! 이렇게 해서 트리를 생성하면

for문을 n번 돌면서

나보다 큰 순위의 값이 존재하는지 검사를 해서

최선의 순위를 출력해주면 되는데요


최선의 순위 = 1 + (나보다 빨리 출발한 녀석들 중에 나보다 속도가 빠른녀석들)

입니다.

즉, 내 앞에 달리는 놈들 중에 나보다 빠른녀석들의 개수를 트리에 넣어야해요!


n = 8이라면

0~7까지의 실력 값이 존재합니다.

트리에 나보다 실력이 높은 놈의 수를 세서 1을 더하면 순위가 됩니다!


달리기 문제에서의 예제를 예로 들면

2, 8, 10, 7, 1, 9, 4, 15라는 절대 실력 값이 들어옵니다.

이것을 상대 실력으로 바꾸면

1, 4, 6, 3, 0, 5, 2, 7 이 됩니다!


첫번째 달리기 선수는 상대 실력이 1인데

맨앞에 달리고 있으므로 트리는 비어있습니다.

그러므로 1 + 0으로 최선의 순위는 1이됩니다.


두번쨰 선수! 상대 실력은 4입니다.

트리에는 현재 1의 값 밖에 존재하지 않습니다.

순위는 1 + 0 = 1이 됩니다.


3번째도 마찬가지겠지요.

4번째에서는 상대 실력이 3입니다.

현재 트리에는 3가지의 실력 값이 들어가있는데요.

나보다 큰 실력 값이 몇개인지 찾아야겠지요.


찾아보니 4, 6이라는 실력 값이 존재합니다.

그러므로 1 + 2를 해서 3이라는 최선의 순위를 찾을 수 있습니다.


세그먼트 트리에서 어떻게 자신보다 큰 실력 값을 찾는지는 코드를 통해서 보시기 바랍니다.

궁금한 점은 댓글 달아주시면 답변 드리겠습니다.


풀 코드입니다.

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
pii arr[(int)5e5];//실력, 위치
 
int update(vi &tree, int node, int value, int start, int end) {
    if (value < start || end < value) return tree[node]; // 범위 벗어나면 그냥 리턴
    else if (start == end) return tree[node] = 1; // 내가 찾는 value이면 1리턴
 
    int mid = (start + end) / 2;
    return tree[node] = update(tree, node * 2, value, start, mid) + update(tree, node * 2 + 1, value, mid + 1, end);
}
 
int query(vi &tree, int node, int value, int start, int end) {
    if (value < start) return tree[node]; // 내가 찾는 value보다 시작점이 크면 그냥 tree의 개수를 리턴하면 됨.
    else if (end < value || start == end) return 0;
    // end가 나보다 작다는 것은 내 value보다 작으므로 개수를 세면 안됨.
    // 혹은 첫번째 if(value < start) 조건에 안걸렸으면 start == end가 같을 조건은 무조건 start==end가 나보다 작다는 것을 의미
    // 그러므로 0리턴
    
    int ret = 0;
    int mid = (start + end) / 2;
    return query(tree, node * 2, value, start, mid) + query(tree, node * 2 + 1, value, mid + 1, end);
}
 
bool cmp(pii a, pii b) {
    return a.second < b.second;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
 
    sort(arr, arr + n);
 
    for (int i = 0; i < n; i++) arr[i].first = i;
 
    sort(arr, arr + n, cmp);
 
    vi tree(1 << ((int)ceil(log2(n)) + 1)); // 구간에 데이터가 몇 개 있는지를 파악하는 트리
 
    for (int i = 0; i < n; i++) {
        cout << 1 + query(tree, 1, arr[i].first, 0, n - 1) << '\n';
        update(tree, 1, arr[i].first, 0, n - 1);
    }
    return 0;
}
cs


저작자표시

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

[1395] 스위치  (0) 2017.08.30
[12844] XOR  (0) 2017.08.26
[10999] 구간 합 구하기 2  (0) 2017.08.15
[2042] 구간 합 구하기  (0) 2017.08.15

구간 합 구하기1처럼 풀면 시간초과가 나는 문제입니다.

Lazy Propagation + 세그먼트 트리를 섞어서 해결해야하는 문제입니다.
저도 Lazy Propagation ??이라는 알고리즘은 처음 보는데요.

개념은 간단합니다. 지금 할 필요 없는 일은 미루는 개념입니다. 굉장히 게으른 알고리즘이지만 효율이 굉장히 좋은 것 같습니다.


설명 : https://www.acmicpc.net/blog/view/26


여기에 설명이 매우 잘 나와있습니다.


제 코드입니다. 궁금하신건 댓글 달아주시면 무조건 답변 달아드립니다.

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
#include <iostream>
#include <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[MAX_SIZE];
 
ll init(vll &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(vll &tree, vll &lazy, int node, int start, int end) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node] * (end - start + 1);
 
        if (start != end) { //leaf노드가 아닐 때만 전파
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
ll update_range(vll &tree, vll &lazy, int node, int start, int end, int left, int right, ll add) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] += add * (end - start + 1);
 
        if (start != end) {
            lazy[node * 2] += add;
            lazy[node * 2 + 1] += add;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, add) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, add);
}
 
ll sum(vll &tree, vll &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(tree, lazy, node * 2, start, mid, left, right) + sum(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    int height = (int)ceil(log2(n));
    vll tree(1 << (height + 1));
    vll lazy(1 << (height + 1));
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    init(tree, 1, 0, n - 1);
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        ll add;
        cin >> cmd >> a >> b;
        a--, b--;
 
        if (cmd == 1) {
            cin >> add;
            update_range(tree, lazy, 1, 0, n - 1, a, b, add);
        }
        else {
            cout << sum(tree, lazy, 1, 0, n - 1, a, b) << '\n';
        }
    }
 
    return 0;
}
cs


저작자표시

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

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

세그먼트 트리 OR 펜윅 트리로 해결할 수 있는 문제입니다.


세그먼트 트리랑 펜윅 트리 설명 글은 따로 준비해보겠습니다.


세그먼트트리 : https://www.acmicpc.net/blog/view/9

펜윅트리 : https://www.acmicpc.net/blog/view/21


boj 블로그에 있는 내용입니다.

참고하세요!


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
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
 
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define ll long long
#define INF 0x7fffffff
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[(int)1e6 + 1];
ll tree[(int)1e6 + 1];
 
void update(int idx, int diff, int size) {
    while (idx <= size) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}
 
ll sum(int idx) {
    ll ret = 0;
    while (idx) {
        ret += tree[idx];
        idx -= (idx & -idx);
    }
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
 
    //트리를 만드는 과정
    for (int i = 1; i <= n; i++) {
        update(i, arr[i], n);
    }
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        cin >> cmd >> a >> b;
 
        if (cmd == 1) {
            update(a, b - arr[a], n);
            arr[a] = b;
        }
        else {
            cout << sum(b) - sum(a - 1) << '\n';
        }
    }
 
    return 0;
}
cs


저작자표시

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

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

1의 보수란 어떤 수를 커다란 2의 제곱수-1에서 빼서 얻은 이진수이다. 또는 비트를 반전시켜 얻을수 있다. 1의 보수는 대부분의 산술연산에서 원래 숫자의 음수처럼 취급된다. 주어진 이진수와 자리수가 같고 모든 자리가 1인 수에서 주어진 수를 빼서 얻은 수가 1의 보수이다. 혹은 주어진 이진수의 모든 자리의 숫자를 반전(0을 1로, 1을 0으로)시키면 1의 보수를 얻을 수 있다.


https://ko.wikipedia.org/wiki/1%EC%9D%98_%EB%B3%B4%EC%88%98



그러면 1의 보수를 왜쓰냐!!!!!!!하면!!

음수(-)를 표현해주기 위해서 입니다!

컴퓨터는 숫자를 비트로 나타내자나요!?? 4bit라고 생각했을 때 0001이면 1, 0010이면 2

이런식으로 0000~1111 까지 4비트라면 0~15를 나타낼 수 있습니다.

이런 방식이 흔히 우리가 코딩할 때 쓰는 unsigned 방식입니다. 음수를 나타내지 않는 방식이죠.


int는 32비트이니깐 0 ~ (2의 32승 - 1)까지 나타낼 수 있겠죠????

unsigned에 2의 32승 - 1을 대입하시면 숫자가 망가지지 않는 걸 볼 수 있습니다.


그런데

signed(int앞에 키워드를 안붙여도됨 디폴트 값임)에 2의 32승 -1을 넣으면 깨질까욥 안꺠질까욥?

깨집니다!!!!!!!


이유는 signed를 사용하면 음수 값을 사용할 수 있게 되는데! 32비트개의 비트중 맨 앞에 비트를 음수인지 양수인지 구분하는 비트로 사용하기 때문입니다.

그렇기 때문에 0 ~ (2^32 - 1) 이었던 범위가 ! 반으로 싹 ! 쪼게집니다. 그러면 -(2^31 - 1) ~ (2^31 - 1)까지 표현이 가능합니다!


근데 여기서 1의 보수의 문제점을 발견할 수 있습니다!

무엇이냐!!!!!!

4비트로 예를 들어드릴게요!

4비트를 쭉! 써보겠습니다.

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111


이렇게 16가지의 숫자가있죠! 0에서 15까지!!!!!

근데 우리는 맨앞의 부호를 -로 쓰기로했으니 -7에서 7까지의 숫자가 표현이가능합니다!!!!!

여기서 발생하는 문제는 무엇일까요!?

-7 ~ 7까지의 숫자는 16개가 아니고 15개죠??? 왜일까요????

0이 두번 체크되기 때문인데요


1의 보수는 모든 비트를 반전시키는 것이라고 말씀드렸습니다.


그렇다면 0000을 반전시키면 1111 -> -0 값을 갖는데 -0이라는 숫자는 0과 같죠. 두 번 세줄 필요가 없는 것입니다.

그렇다면 이 문제를 어떻게 해결할까요??


바로!!!!!!!!


2의 보수입니다.!

2의 보수 = 1의 보수 + 1 인데요!!!!!!!!

정의 한번 볼까욥


2의 보수란 어떤 수를 커다란 2의 제곱수에서 빼서 얻은 이진수이다. 2의 보수는 대부분의 산술연산에서 원래 숫자의 음수처럼 취급된다. 주어진 이진수보다 한 자리 높고 가장 높은 자리가 1이며 나머지가 0인 수에서 주어진 수를 빼서 얻은 수가 2의 보수이다. 혹은 주어진 이진수의 모든 자리의 숫자를 반전(0을 1로, 1을 0으로)시킨 뒤 여기에 1을 더하면 2의 보수를 얻을 수 있다.


https://ko.wikipedia.org/wiki/2%EC%9D%98_%EB%B3%B4%EC%88%98


이렇게하면 4비트로 -8부터 7까지 표현이 가능해집니다!


그 이유는 !!!!!

0 ~ 7 까지는 총 8개인데 0 ~ 7 까지를 반전시키면 ! -0 ~ -7에서 -1 ~ -8로 바껴버리지요용!!!!!!!! 그러므로 -8 ~ 7까지 총 16개의 수를 전부 사용할 수 있습니당!!!!!!!!!!!!!

저작자표시

'CS기본지식 > 컴퓨터 기본 지식' 카테고리의 다른 글

rest란??  (0) 2017.11.19

+ Recent posts

티스토리툴바