https://www.welcomekakao.com/learn/courses/30/lessons/42892



순회는 간단한 부분이기 때문에, 사실 관건은 좌표를 이용해서 트리를 어떻게 만들 것이냐이다.


기본적으로 위에서부터, root를 시작으로 아래로 채워갈 것이기 때문에, 입력받는 좌표를 y값 내림차순으로 정렬한다. y좌표가 동일한 경우 x좌표 오름차순으로 정렬해서, 왼쪽 자식부터 확인할 수 있도록 한다.


정렬을 할 때, 아무런 처리를 해주지 않고 정렬하게 되면, 본인이 원래 몇 번째 인덱스였는지 잃어버리기 때문에, 이후에 순회를 할 수가 없다.


따라서 입력을 받을 당시에, 본인의 인덱스를(노드 번호) 갖고 있도록 처리를 해주어야 한다.



본인은 구조체를 이용했고, 사실 벡터에 그냥 인덱스를 추가해줘도 상관이 없을 것 같다.



트리를 만들 때는, 링크드리스트의 형태를 취해서 만드는 것도 가능하고, 배열의 인덱스를 루트로 해서 하는 방법도 가능하다.


본인은 후자로 구현했다.



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
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct Node {
    int idx, l = 0, r = 0, x, y;
}b[10001];
struct move {
    int l, r;
}m[10001];
bool cmp(Node a, Node b) {
    if (a.y > b.y) return true;
    else if (a.y < b.y) return false;
    else {
        return a.x < b.x;
    }
}
int num;
void makeTree(int root) {
 
    for (int i = 2; i <= num; i++) {
        int cur = root;
        while (1) {
            if (b[i].x < b[cur].x) {
                if (b[cur].l == 0) {
                    b[cur].l = i;
                    break;
                }
                else
                    cur = b[cur].l;
            }
            else {
                if (b[cur].r == 0) {
                    b[cur].r = i;
                    break;
                }
                else
                    cur = b[cur].r;
            }
        }
    }
}
vector<int> pre;
void preOrder(int cur) {
    if (cur == 0) return;
    pre.push_back(cur);
    preOrder(m[cur].l);
    preOrder(m[cur].r);
}
vector<int> pos;
void postOrder(int cur) {
    if (cur == 0) return;
    postOrder(m[cur].l);
    postOrder(m[cur].r);
    pos.push_back(cur);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    num = nodeinfo.size();
 
    for (int i = 1; i <= nodeinfo.size(); i++) {
        b[i].x = nodeinfo[i-1][0];
        b[i].y = nodeinfo[i-1][1];
        //cout << nodeinfo[i - 1][0] << ' ' << nodeinfo[i - 1][1] << '\n';
        b[i].idx = i;
    }
 
    sort(b+1, b + num+1, cmp); //1. y좌표 큰순, 2. x좌표 작은순
    
    makeTree(1); // root의 노드 번호
    
    for (int i = 1; i <= num; i++) {
        m[b[i].idx].l = b[b[i].l].idx;
        m[b[i].idx].r = b[b[i].r].idx;
    }
 
    preOrder(b[1].idx);
    postOrder(b[1].idx);
 
    answer.push_back(pre);
    answer.push_back(pos);
    return answer;
}
 
int main(void) {
    vector<vector<int>> nodeinfo;
    nodeinfo = { {5,3},{11,5}, {13,3}, {3,5}, {6,1}, {1,3}, {8,6}, {7,2}, {2,2} };
    solution(nodeinfo);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

2017 카카오 블라인드 테스트 1차: 비밀지도 (C++)  (0) 2019.08.23
카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
카카오 2018 블라인드 테스트: 실패율 C++  (0) 2019.08.19
카카오 2018 블라인드 테스트: 오픈채팅방 C++  (0) 2019.08.19
프로그래머스: 모의고사 (C++)  (0) 2019.07.09

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


인덱스 트리를 활용하여 해결했다.


앞선 인덱스 트리를 활용하는 문제들과 같이, 이 문제도 말만 다르지, 결국 원소 업데이트가 빈번하게 일어나는 동시에 구간합을 구하는 문제이다.


특정 맛의 사탕을 빼거나 더하는 것은, 인덱스 트리의 기본적인 업데이트 쿼리와 동일하기 때문에 따로 설명하지는 않을 것이고, 특정 순위의 사탕을 가져오는 부분에 대해서만 살펴보겠다.



a == 1인 경우에 k번째 순위를 가지는 사탕을 가져와야 하는 상황이다.


root에서부터 노드 하나하나가 사탕의 개수를 구간합으로 가지고 있는 형태로 트리를 만들어준다. leaf 노드의 수는 가능한 맛의 범위로 잡아주면 된다. 이 문제에서는 100 만이었던 것으로 기억한다.


이렇게 leaf 노드는 그 맛의 사탕이 몇 개 있다는 것을 의미한다.



이제 k번째 순위의 사탕을 찾는다고 하면, 트리의 왼쪽에서부터(가장 맛있는 사탕부터) k번째인 것이다. 이때 k보다 한 노드의 값(거기까지 구간합)이 크다면 그 노드의 자손 부분에 우리가 찾는 k번째 사탕이 존재한다는 의미이므로 계속 아래로 내려가준다.


반대로 k보다 작다면, 우리가 찾는 k번째 사탕이 그 노드의 오른쪽 트리에 있다는 것이기 때문에 오른쪽으로 이동해주고, 왼쪽에 있는 사탕의 개수(확인했던 구간합의 값)만큼 k를 감소시켜준다.


또한 리트 노드에 도달했다면 위의 작업을 해줄 필요가 없기 때문에, 리프 노드인지 아닌지 확인해 주는 작업을 함께 진행해주면 된다.


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
#include<iostream>
#define MAX 1000000
using namespace std;
 
int idxT[4 * MAX+2], start = 1;
 
void Update(int idx, int delta) {
    while (idx > 0) {
        idxT[idx] += delta;
        idx /= 2;
    }
}
 
int getCandy(int k) {
    int i = 1;
    while (1) {
        if (idxT[i] >= k) { //이 지점의 서브트리에 우리가 찾는 사탕이 속해 있다면
            if (i >= start && i < start + MAX) { //그 지점이 leaf라면 종료
                Update(i, -1);
                return i - start + 1;
            }
            i *= 2; //leaf가 아니라면 이어서 탐색
            continue;
        }
        else { //이 지점이 아닌 반대쪽에 우리가 찾는 사탕이 있다면
            k = k - idxT[i]; 
            i++;
            continue;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while (start < MAX) //MAX보다 크거나 같으면서 가장 큰 2의 제곱수
        start *= 2;
    
    int n; 
    cin >> n; //쿼리의 수
    for (int i = 0, a, b, c ; i < n; i++) {
        cin >> a >> b;
        if (a == 1) 
            cout << getCandy(b) << '\n'; //사탕 꺼내기
        
        else {
            cin >> c; //사탕의 변화량
            Update(b + start - 1, c);
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13

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


이진 검색 트리를 구현해주면 된다.


왼쪽 자식은 부모보다 작은 값이고, 오른쪽 자식은 부모보다 큰 값이다.


이진 검색 트리의 서브트리는, 마찬가지로 이진 검색 트리이다.



이 문제에서는 node 구조체를 root값 자체를 인덱스로 하도록 잡았다.


이전에 트리 순회 문제에서도 봤듯이, 순회가 문제에 섞일 때에는 인덱스를 루트의 값과 연결시켜서 잡아주는 것이 좋은 것 같다.



이 문제에서 주의할 사항은, 루트의 값 자체를 인덱스로 사용하기 때문에, 전체 노드의 개수가 아닌, root값의 허용 범위를


인덱스로 잡아줘야하다는 것이다.


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
#include<iostream>
using namespace std;
 
struct NODE{
    int l, r;
}n[1000002]; //인덱스가 root
//노드의 개수는 1000개인데, 인덱스를 루트로 쓰고 있기 때문에 루트의 허용 범위만큼 인덱스 필요
 
void postOrder(int rt) {
    if (rt == 0) return;
    postOrder(n[rt].l);
    postOrder(n[rt].r);
    cout << rt << '\n';
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int root;
    cin >> root; //전위순회니까 처음 나오는 게 무조건 tree의 root
    int num;
    while (cin >> num) {
        int cur = root;
        while (1) {
            if (num < cur) {
                if (n[cur].l != 0) cur = n[cur].l;
                else {
                    n[cur].l = num;
                    break;
                }
            }
            else {
                if (n[cur].r != 0) cur = n[cur].r;
                else {
                    n[cur].r = num;
                    break;
                }
            }
 
        }
    }
    postOrder(root);
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13

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


트리는


1. 간선의 개수 + 1 == 노드의 개수


2. 들어오는 간선이 없는 노드는 하나



1번 사실을 이용해서 node를 담는 set을 만들고, 간선의 개수를 카운트해서 개수 비교를 통해 풀었다.


추가적으로, 간선이 하나도 없어도 트리가 될 수 있다.


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
#include<iostream>
#include<unordered_set>
using namespace std;
unordered_set<int> nodes;
int main(void) {
 
    bool endFlag = false;
    int lineCnt = 0, caseCnt = 1;
    while (1) {
        int a, b;
        cin >> a >> b;
        if (a == -1 && b == -1) {
            endFlag = true;
            break;
        }
        if (a == 0 && b == 0) {
            if (lineCnt == 0 || nodes.size() == lineCnt + 1 ) {
                printf("Case %d is a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
            else{
                printf("Case %d is not a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
 
        }
        nodes.insert(a);
        nodes.insert(b);
        lineCnt++;
    }
 
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12

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


재귀로 트리 순회를 구현해주면 된다.


무조건 대문자로 들어온다고 했기 때문에 'A'를 빼주면서 A부터 0에 대응되도록 인덱스를 잡아준다.



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
#include<iostream>
using namespace std;
struct NODE {
    char left;
    char right;
}tree[27];
void preOrder(char root) {
    if (root == '.') return;
    cout << root;
    preOrder(tree[root-'A'].left);
    preOrder(tree[root-'A'].right);
}
void inOrder(char root) {
    if (root == '.') return;
    inOrder(tree[root - 'A'].left);
    cout << root;
    inOrder(tree[root - 'A'].right);
}
void postOrder(char root) {
    if (root == '.')return;
    postOrder(tree[root - 'A'].left);
    postOrder(tree[root - 'A'].right);
    cout << root;
}
int main(void) {
    int n;
    cin >> n;
    while (n--) {
        char parent, l, r;
        cin >> parent >> l >> r;
        tree[parent - 'A'].left = l;
        tree[parent - 'A'].right = r;
    }
    preOrder('A');
    cout << '\n';
    inOrder('A');
    cout << '\n';
    postOrder('A');
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12
백준 10255 교차점 C++  (0) 2019.08.11

+ Recent posts

티스토리툴바