백준: Class 4 - 1932, 1991, 5639

</br> 클래스 4 계속
</br>

1932: 정수 삼각형

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

방법 1.

void func(int ix, int c){
    if( ix >= sz-n ){
        ans = max(ans, c);
        return;
    }
    func(ix+ind[ix], c + heap[ix+ind[ix]]);
    func(ix+ind[ix]+1, c + heap[ix+ind[ix]+1]);
}

// in main()
    sz = n*(n+1)/2;
    for(int i = 0, j = 1; i < sz; j++){
        int k = j*(j+1)/2;
        while( i < k ){
            ind[i] = j;
            i++;
        }
    }
    for(int i = 0; i < sz; i++){
        cin >> heap[i];
    }
    func(0, heap[0]);
    cout << ans << endl;

아하… 힙 모양이네 막 min heap 이런 거 할 때 배열 형태로 저장했었지
나도 그렇게 저장해서 인덱스 규칙 따라서 dfs로 찾아 보자

했는데 시간 초과 났다
</br>

헉… 왜 그럴까 막 그러다보니 다른 방법이 생각났는데

방법 2.

    for(int i = 0; i < n; i++){
        for(int j = 0; j < i+1; j++){
            cin >> heap[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        dp[n-1][i] = heap[n-1][i];
    }
    for(int i = n-1; i >= 0; i--){
        for(int j = 0; j < i+1; j++){
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]);
            dp[i][j] += heap[i][j];
        }
    }
    cout << dp[0][0] << endl;

거꾸로 올라가면 선택할 필요가 없다!! dp문제였다

ex) n = 3
      0 0
   1 0   1 1
2 0   2 1   2 2

삼각형의 인덱스가 이런 모양이라면 (1, 0)에서의 최댓값은 (2, 0)과 (2, 1) 중 최댓값을 골라 힙의 값을 더한 것일 것이다.
</br>

1991: 트리 순회

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

#include <bits/stdc++.h>
using namespace std;
tuple<char, char, char> tree[27];

void preorder(int now){
    cout << get<0>(tree[now]);
    if( get<1>(tree[now]) != '.' ) preorder(get<1>(tree[now])-'A');
    if( get<2>(tree[now]) != '.' ) preorder(get<2>(tree[now])-'A');
}
void inorder(int now){
    if( get<1>(tree[now]) != '.' ) inorder(get<1>(tree[now])-'A');
    cout << get<0>(tree[now]);
    if( get<2>(tree[now]) != '.' ) inorder(get<2>(tree[now])-'A');
}
void postorder(int now){
    if( get<1>(tree[now]) != '.' ) postorder(get<1>(tree[now])-'A');
    if( get<2>(tree[now]) != '.' ) postorder(get<2>(tree[now])-'A');
    cout << get<0>(tree[now]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        char p, c1, c2;
        cin >> p >> c1 >> c2;
        tree[p-'A'] = make_tuple(p, c1, c2);
    }
    preorder(0);
    cout << '\n';
    inorder(0);
    cout << '\n';
    postorder(0);
    cout << '\n';
}

트리… 작년 자료구조 때 struct로 만들고 막 그랬던
지금은 좀 귀찮아서 그냥 튜플로 처리
전위는 루트-왼-오, 중위는 왼-루트-오, 후위는 왼-오-루트이므로, 출력 위치만 루트 자리로 바꿔 주면 된다

지금 보니까 이 문제는 상관없지만 다른 문제들은 인덱스가 자기 마음대로일 수 있으므로, map< char, pair<char, char> >이런 식으로 선언하는 게 더 나을 것 같다
</br>

5639: 이진 검색 트리

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

방법 1.

#include <bits/stdc++.h>

using namespace std;

map<int, pair<int, int> > tree;

void postorder(int now){
    if( tree[now].first != 0 ) postorder(tree[now].first);
    if( tree[now].second != 0 ) postorder(tree[now].second);
    cout << now << '\n';
}

void addNode(int r, int k){
    if( k < r ){
        if( tree[r].first ) addNode(tree[r].first, k);
        else{
            tree[r].first = k;
            return;
        }
    }
    else{
        if( tree[r].second ) addNode(tree[r].second, k);
        else{
            tree[r].second = k;
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> v;
    int a, root = 0;
    while( cin >> a ){
        tree[a] = make_pair(0, 0);
        if( root == 0 ) root = a;
        else addNode(root, a);
    }
    postorder(root);
}

입력 받을 때마다 노드를 만들고, 루트에서부터 찾아 이진 탐색에 따라 삽입하기를 했다.
따라서 트리가 복구되고, 이후 위에도 쓴 postorder() 함수를 사용한다.

근데 시간초과 난다!!
헉… 어째설까
그래서 질문글을 올렸었는데, 친절하신 분이 바로 답을 달아주셨다
https://www.acmicpc.net/board/view/73500#post

Q) 트리에 노드 입력은 평균 O(logN)이고, 최악의 경우 O(N)이라고 알고 있습니다. 따라서 위 코드는 복잡도가 최악에 O(N^2)이 아닌가요?
A) map은 원소를 삽입, 삭제, 탐색하는 과정에서 O(logN)이 걸립니다. 이때문에 실제 시간복잡도는 질문자님이 예상하신 것에 logN이 붙어 O(N^2 logN)이 됩니다.

내가 바보였구나
귀찮다고 맵으로 만들어 놓고ㅜㅜ
</br>

방법 2.

#include <bits/stdc++.h>

using namespace std;

vector<int> pre, in;
int d;

void post(int b, int e){
    int root = -1;
    for(int i = b; i < e; i++){
        if( in[i] == pre[d] ){
            root = i;
            break;
        }
    }
    d++;
    if( root != b ) post(b, root);
    if( root != e-1 ) post(root+1, e);
    cout << in[root] << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    while( cin >> a ){
        pre.push_back(a);
        in.push_back(a);
    }
    sort(in.begin(), in.end());
    post(0, pre.size());
}

그래서, 자료구조 시간 때 전위, 중위로 후위 구하기, 중위, 후위로 전위 구하기 등? 했던 게 생각나서 그렇게 풀어 보기로 했다.
이진 탐색이니까 중위순회는 정렬된 모습이다.

ex) 백준 예제
pre: 50 30 24 5 28 45 98 52 60
in : 5 24 28 30 45 50 52 60 98

전위순회는 루트 우선이므로, 중위순회에서 각각 루트의 위치를 알면 다 풀린다.

pre: 50   30 24 5 28 45 98 52 60
in : 5 24 28 30 45   <50>   52 60 98

pre: 50 30    24 5 28 45 98 52 60
in : 5 24 28   <30>   45

pre: 50 30 24    5 28 45 98 52 60
in : 5   <24>   28

pre: 50 30 24 5    28 45 98 52 60
in : <5>

pre: 50 30 24 5 28    45 98 52 60
in : <28>

pre: 50 30 24 5 28 45    98 52 60
in : <45>

pre: 50 30 24 5 28 45 98    52 60
in : 52 60   <98>

pre: 50 30 24 5 28 45 98 52   60
in : <52>   60

pre: 50 30 24 5 28 45 98 52   60
in : <60>

대충 함수의 실행 순서는 이렇고, 루트 출력을 가장 마지막에 해 주면 후위순회가 가능하다(왼쪽>오른쪽>루트).
</br>

---

오랜만에 트리를 이렇게 잔뜩…
추억에 잠겼다
</br>