반응형

1. 세그먼트 트리 (Segment Tree)

 

먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1,2,3,4,5} 일 때, 다음과 같은 그래프로 나타낼 수 있습니다.

 

 

각각의 노드들의 값은 자식 노드들의 값들을 더한 것입니다. 구간의 합을 구할 때 보통 O(N)의 시간이 걸리지만 세그먼트 트리를 이용한다면 O(logN)의 시간만에 값을 구할 수 있습니다.

 

트리를 만들기 위해서는 트리의 높이를 알아야 합니다. 트리의 높이를 알기 위해서는 리프노드의 수를 이용해야 하고, 다음과 같이 구할 수 있습니다.

 

트리의 높이 = ceil(log(N))

 

ceil은 어떤 수든 올림을 해서 구해주는 함수입니다. 따라서 log5 = 2.xxx이지만 ceil함수 안에 넣는다면 3이라는 수가 나오게 됩니다. 위의 그래프를 보면 루트 노드의 높이를 0이라고 했을 때 트리의 높이가 3인 것을 알 수 있습니다. 따라서 세그먼트 트리의 크기는 2^(트리의 높이 + 1)이 됩니다.

 

2. 세그먼트 트리 만들기

 

먼저 주어진 범위를 반으로 나누고, 나누어진 2개의 범위에 대해서 왼쪽과 오른쪽 범위에 대해 각각 재귀호출을 해줍니다. 이를 계속 반복해주다가 리프 노드에 다다르면 재귀를 멈춰주시면 됩니다.

 

이진트리이므로 항상 범위를 반으로 나누면 됩니다. 즉 (현재 노드, 시작 범위, 끝 범위)의 형태로 반복해서 재귀 호출을 해주고 마지막에 시작 범위와 끝 범위가 일치할 때가 리프 노드이므로 값을 넣어주고 그 값을 return 해주면 됩니다.

 

 

3. 세그먼트 트리 구간합 구하기

 

구간합을 구할 때 조건을 나누어 주면 쉽게 구할 수 있습니다. 

 

1. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치는 경우

2. 현재 탐색하는 범위가 찾고자하는 범위와 일부 겹치는 경우

3. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치지 않는 경우

 

이를 코드로 표현하면 다음과 같습니다.

 

 

4. 세그먼트 트리 값 바꾸기

 

특정 index의 값을 바꿀 때도 분기를 나누어서 구해주면 됩니다. 바꾸고자 하는 index가 현재 범위에 포함되어 있는지 없는지만 체크해주면 쉽게 구현할 수 있습니다.

 

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
반응형

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

 

13334번: 철로

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

선분의 최대 개수가 100,000개이므로 2중 for문을 돌리게 된다면 시간 초과가 뜹니다. 따라서 한 번의 탐색으로 답을 구해야 합니다.

 

먼저 선분을 끝점의 좌표를 기준으로 오름차순으로 정렬합니다. 그리고 앞에서부터 탐색을 시작하면서 선분의 길이가 d보다 작거나 같다면 priority_queue에 넣어줍니다. 그리고 끝 점의 좌표를 o라고 했을 때 o-d의 좌표보다 시작점의 좌표가 작다면 priority_queue에서 pop을 해줍니다.

 

이때 priority_queue의 size가 선분의 개수가 되고 위의 과정을 반복하면서 size의 최댓값을 저장해줍니다. 그리고 마지막에 최댓값을 출력해주면 쉽게 풀리는 문제였습니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct line {
    int h;
    int o;
};
 
struct cmp {        //priority_queue는 선분의 시작 좌표가 작을수록 먼저 나오도록 설정
    bool operator()(line right, line left)
    {
        if (left.h == right.h) return left.o < right.o;
        return left.h < right.h;
    }
};
 
bool comp(line left, line right)    //선분들을 끝 좌표를 기준으로 오름차순 정렬
{
    if (left.o == right.o) return left.h < right.h;
    return left.o < right.o;
};
 
int n, d;
vector<line> arr;
priority_queue<line, vector<line>, cmp> pqAns;
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int h, o;
        scanf("%d %d", &h, &o);
        if (h < o) {        //좌푯값이 더 작은 값을 먼저 넣기
            arr.push_back({ h,o });
        }
        else {
            arr.push_back({ o,h });
        }
    }
 
    sort(arr.begin(), arr.end(), comp);
 
    cin >> d;
 
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        int h = arr[i].h;
        int o = arr[i].o;
 
        if (o - h <= d) {    //선분의 길이가 d를 넘지 않으면 push
            pqAns.push({ h,o });
        }
 
        while (!pqAns.empty())
        {
            int h = pqAns.top().h;
            if (h < o - d) {    //만약 제일 앞에 있는 선분이 길이L을 벗어나면 pop
                pqAns.pop();
            }
            else {
                break;
            }
        }
 
        if (ans < pqAns.size()) {    //pq의 사이즈가 선분의 개수
            ans = pqAns.size();
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
반응형

 

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

 

14725번: 개미굴

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

트라이의 개념을 모른다면 공부하고 이 문제를 푸는 것을 추천합니다!

 

문제의 조건에서 사전 순으로 출력하라고 했으므로 map 자료구조를 이용해서 문제를 풀었습니다. 각각의 노드들은 자식 노드를 가지고 있고, 자식 노드들의 키값은 string입니다. 따라서 map <string, Trie*> map을 만들어 주고 이 노드는 자식 노드의 정보를 포인터의 형식으로 가지고 있습니다.

 

먹이를 벡터로 입력 받아서 만약 해당 깊이에 단어가 존재한다면 그 단어의 자식 노드로 넘어가고, 없다면 단어를 동적 할당을 통해 생성해줍니다. 그러고 나서 자식 노드로 넘어가게 됩니다.

 

이러한 방식으로 모든 입력을 처리하면 map의 특성상 자동으로 오름차순으로 정렬이 되기때문에 따로 정렬해줄 필요 없이 Find 함수를 통해서 출력해주면 됩니다.

 

Find 함수 또한 iiterator를 차례로 순회해주면서 dfs와 비슷한 방식으로 출력해주면 됩니다.

 

[ 소스 코드 ]

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<string>
#include<map>
#include<vector>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie*> m;        //오름차순으로 출력하기 위해서 map을 씀
    ~Trie() {                    //소멸자로 동적 할당한 Trie들을 delete
        for (auto it = m.begin(); it != m.end(); it++) {
            delete it->second;
        }
    }
 
    void Insert(vector<string> vect, int idx)
    {
        if (vect.size() == idx) return;    //모두 삽입했다면 return
 
        if (m.find(vect[idx]) == m.end()) {    //vect[idx]가 map에 없다면
            m.insert({ vect[idx], new Trie });
        }
 
        m[vect[idx]]->Insert(vect, idx + 1);    //다음 단어를 삽입
    }
 
    void Find(int depth)
    {
        for (auto it = m.begin(); it != m.end(); it++) {
            for (int i = 0; i < depth; i++) {
                printf("--");
            }
            cout << it->first << '\n';
            
            it->second->Find(depth + 1);
        }
    }
};
 
int main()
{
    Trie *root = new Trie();
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        vector<string> vect(n);
        for (int j = 0; j < n; j++) {
            cin >> vect[j];
        }
 
        root->Insert(vect, 0);
    }
 
    root->Find(0);
    delete root;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2162번 - 선분 그룹 (C++)  (0) 2022.06.26
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
반응형

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

 

2162번: 선분 그룹

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/5

 

[ 백준 ] 17387번 - 선분 교차 2 (C++)

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net [ 문제풀이 ] 선분이 교차할..

rudalsd.tistory.com

 

위 문제를 풀어보고 오는 것을 추천드립니다!

 

이 문제는 선분 교차 2 문제에서 Union - Find를 추가한 문제입니다. 직선의 개수가 3000개밖에 되지 않으므로 2중 for문을 돌려도 큰 문제가 없으므로 2중 for문으로 문제를 풀었습니다. 선분이 교차한다면 Union을 해주고 마지막에 모든 선분을 돌면서 Find를 통해 map에 부모 노드를 저장해줍니다.

 

그리고 map.size()와 map[ 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
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
#include <iostream>
#include <algorithm>
#include<unordered_map>
 
using namespace std;
 
struct pos {
    int x;
    int y;
};
 
pos arr[6000];
int vect[3001];
unordered_map<int, int> m;
 
int N;
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    if (pa != pb) {
        vect[pb] = pa;
    }
}
 
bool cmp(pos left, pos right)
{
    if (left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    int cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N * 2; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    for (int i = 0; i < N ; i++) {
        sort(arr + i * 2, arr + (i + 1) * 2, cmp);
    }
 
    for (int i = 0; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int l1 = closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2]) * closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2 + 1]);
            int l2 = closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2]) * closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2 + 1]);
            if (l1 == 0 && l2 == 0) {            //두 선이 일직선상에 있을 때
                if (cmp(arr[j*2], arr[i*2+1]) && cmp(arr[i*2], arr[j*2+1])) {
                    if (Find(i) != Find(j)) {
                        Union(i, j);
                    }
                }
            }
            else if (l1 <= 0 && l2 <= 0) {
                if (Find(i) != Find(j)) {
                    Union(i, j);
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        m[Find(i)]++;        //집합에 속해있다면 선분을 map에 추가
    }
 
    int ans = 0;
 
    for (auto it = m.begin(); it != m.end(); it++) {
        if (ans < it->second) {    //집합 중 가장 큰 집합을 ans에 대입
            ans = it->second;
        }
    }
 
    cout << m.size() << endl << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 12850번 - 본대 산책2 (C++)  (0) 2022.06.23
반응형

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

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

 

 

[ 문제풀이 ]

 

문제 난이도에 비해 생각을 좀 해야 하는 문제였습니다.

 

먼저 최댓값과 최솟값을 각각 저장할 maxpq와 minpq를 각각 만들고 입력받는 모든 수들을 넣습니다. 값을 넣을 때 map을 만들어 줘서 현재 그 숫자가 남아있는지 없는지를 체크합니다. 값을 뺄 때는 각각의 큐에서 빼지만 map과 비교하여 없는 숫자라면 계속 pop()해주고, 있는 숫자라면 map에서 빼고 난 후 pq에서 빼줍니다.

 

위 과정을 반복하면 현재 남아있는 숫자들이 map에 저장되어 있고, maxpq와 minpq를 모두 map과 비교하여 없는 숫자들을 pop해줍니다. 그러면 남은 숫자들이 pq에 각각 저장되어 있을 것이고 만약 큐 하나라도 비어있다면 EMPTY를 출력해주고 아니라면 각각의 pq에서 top을 출력해주면 됩니다.

 

[ 소스 코드 ]

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>
#include <unordered_map>
 
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        priority_queue<int> maxpq;        //최댓값 저장
        priority_queue<int, vector<int>, greater<int>> minpq;    //최솟값 저장
        unordered_map<int, int> m;        //현재 남아있는 숫자 저장
 
        int k;
        cin >> k;
        for (int i = 0; i < k; i++) {
            char ch;
            cin >> ch;
            if (ch == 'I') {
                int num;
                cin >> num;
                maxpq.push(num);
                minpq.push(num);
                m[num]++;
            }
            else {
                int num;
                cin >> num;
                if (num == -1) {
                    if (!minpq.empty()) {
                        while (m[minpq.top()] == 0) {    //없는 숫자가 남아있다면
                            minpq.pop();                //모두 pop
                            if (minpq.empty()) {
                                break;
                            }
                        }
                        if (!minpq.empty()) {
                            m[minpq.top()]--;
                            minpq.pop();
                        }
                    }
                }
                else {
                    if (!maxpq.empty()) {
                        while (m[maxpq.top()] == 0) {    //없는 숫자가 남아있다면
                            maxpq.pop();                //모두 pop
                            if (maxpq.empty()) {
                                break;
                            }
                        }
                        if (!maxpq.empty()) {
                            m[maxpq.top()]--;
                            maxpq.pop();
                        }
                    }
                }
            }
        }
 
        while (!maxpq.empty()) {        //없는 숫자 pop
            if (m[maxpq.top()] == 0) {
                maxpq.pop();
            }
            else {
                break;
            }
        }
 
        while (!minpq.empty()) {        //없는 숫자 pop
            if (m[minpq.top()] == 0) {
                minpq.pop();
            }
            else {
                break;
            }
        }
 
        if (maxpq.empty()) {
            cout << "EMPTY" << endl;
        }
        else {
            cout << maxpq.top() << " " << minpq.top() << endl;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1167번 - 트리의 지름 (C++)  (0) 2022.06.19
[ 백준 ] 17404번 - RGB거리 2 (C++)  (0) 2022.06.18
[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 9935번 - 문자열 폭발 (C++)  (0) 2022.06.14
반응형

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

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net

 

 

[ 문제풀이 ]

 

스택을 사용해서 문자열을 넣어가며 폭탄 문자열을 만나면 제거하는 방식으로 문제를 풀었습니다.

 

하지만 폭탄 문자열과 일부만 일치하는 문자열이 들어왔을 때는 한 과정이 더 추가되었습니다. temp 스택에 문자열을 넣으면서 비교를 하다가 폭탄 문자열과 다르다면 temp 스택에 들어있는 문자열을 다시 정답 스택에 집어넣어주었습니다.

 

 

[ 소스 코드 ]

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<stack>
 
using namespace std;
 
string str, bomb;
 
int main()
{
    cin >> str >> bomb;
 
    stack<char> ans;
    stack<char> temp;
 
    for (int i = 0; i < str.size(); i++) {
        ans.push(str[i]);                //stack의 크기가 폭탄문자열의 길이보다 길고 문자가 일치한다면
        if (ans.size() >= bomb.size() && ans.top() == bomb[bomb.size() - 1]) {
            for (int j = bomb.size() - 1; j >= 0; j--) {
                if (bomb[j] == ans.top()) {        //임시로 temp스택에 저장
                    temp.push(ans.top());
                    ans.pop();
                }
            }
            if (temp.size() == bomb.size()) {    //폭탄 문자열이 나오면
                while (!temp.empty()) {            //temp스택을 비움
                    temp.pop();
                }
            }
            else {
                while (!temp.empty()) {            //ans 스택에 temp를 다시 넣어줌
                    ans.push(temp.top());
                    temp.pop();
                }
            }
        }
    }
 
    while (!ans.empty()) {        //스택을 그대로 출력하면 반대로 나오므로
        temp.push(ans.top());    //temp 스택에 다시 넣어줌
        ans.pop();
    }
 
    if (temp.size() == 0) {
        cout << "FRULA";
    }
    else {
        while (!temp.empty()) {
            printf("%c", temp.top());
            temp.pop();
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1967번 - 트리의 지름 (C++)  (0) 2022.06.16
[ 백준 ] 13549번 - 숨바꼭질 3 (C++)  (0) 2022.06.15
[ 백준 ] 2638번 - 치즈 (C++)  (0) 2022.06.13
[ 백준 ] 13460번 - 구슬 탈출 2 (C++)  (0) 2022.06.12
[ 백준 ] 11404번 - 플로이드 (C++)  (0) 2022.06.11

+ Recent posts

티스토리툴바