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

1. 문제설명

서로 인접하지 않은 노드의 집합 중 합이 가장 큰 집합을 찾아야하는 문제이다.

트리를 순회하면서 각 노드마다 선택된 상태와 선택되지 않은 상태를 나누어서 DP로 문제를 해결해야한다.

이 문제에서는 독립집합의 노드를 모두 구해야하는데 이 부분이 어렵다

독립집합의 노드를 구하는 방법은

1. 현재 노드를 택한 경우가 택하지 않은 경우보다 결괏값이 커야한다.

2. 다시 트리를 순회하면서 이전 노드와 인접하지 않은 노드를 구해야한다.

1, 2번을 모두 만족시키는 노드를 골라야 정답이 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
#define MX 10001

int n, weight[MX], dp[MX][2];
vector<int> adj[MX];
bool vis[MX];
vector<int> Path;

void DFS(int node) {
    vis[node] = 1;
    dp[node][1] = weight[node];

    for (auto nx: adj[node]) {
        if (vis[nx]) continue;

        DFS(nx);
        dp[node][1] += dp[nx][0];
        dp[node][0] += max(dp[nx][0], dp[nx][1]);

    }
}

void tracing(int cur, int pre){
    if(dp[cur][1] > dp[cur][0] && !vis[pre]){
        vis[cur] = 1;
        Path.push_back(cur);
    }

    for(auto nx: adj[cur]){
        if(nx==pre) continue;
        tracing(nx, cur);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }

    int a, b, cnt = 0;

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS(1);
    memset(vis, 0 , sizeof(vis));
    tracing(1,0);
    sort(Path.begin(), Path.end());


    cout << max(dp[1][0], dp[1][1]) << '\n';
    for(auto num: Path){
        cout << num << ' ';
    }

    return 0;
}

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

1. 문제설명

인접한 노드 두개가 우수마을이 되면 안된다.

그리고 자신이 우수마을이 아니라면 인접한 노드 중 적어도 하나가 우수마을이 되어야한다.

문제를 해결하기 위해

노드를 재귀적으로 탐색해야한다.

현재 노드가 우수마을인 경우와 우수마을이 아닌 경우를 나눈다.

그리고 현재 노드가 우수마을인 경우에는 다음 노드는 무조건 우수마을이면 안된다.

현재 노드가 우수마을이 아닌 경우에는 다음 노드는 우수마을이거나 우수마을이 아닐 수 있다.

이 때

현재 우수마을이 아닌데 다음 마을도 우수마을이 아닌 경우 문제가 생길 수 있다고 생각했다.

예를 들어 세개의 노드가 다 우수마을이 아닌 경우라면 문제의 조건에 맞지 않다.

하지만 다음 코드와 같이 재귀적으로 탐색하면서 최댓값을 계속 넘겨주다보면

모든 마을이 우수마을이 아닌 경우는 남지 않아서 괜찮다.

최댓값만 남기기 때문에 모든 마을이 우수마을이 아닌 경우는 살아남을 수 없다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
#define MX 10001

int N, people[MX], dp[MX][2];
bool vis[MX];
vector<int> adj[MX];

void DFS(int node){
    dp[node][0] = 0;
    dp[node][1] = people[node];
    vis[node] = 1;

    for(int i=0; i<adj[node].size(); i++){
        int nx = adj[node][i];
        if(vis[nx]) continue;

        DFS(nx);
        dp[node][0] += max(dp[nx][0], dp[nx][1]);
        dp[node][1] += dp[nx][0];
    }
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> people[i];
    }

    for(int i=1; i<N; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS(1);
    cout << max(dp[1][0], dp[1][1]) << '\n';
    return 0;
}

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

1. 문제설명

트리의 전위순회 결과와 중위순회 결과를 바탕으로 트리의 구조를 구해낼 수 있고,

이를 후위순회한 결과를 출력하는 문제이다.

전위 순회한 결과 먼저오는 노드가 루트노드임을 알 수 있고,

그 루트노드를 바탕으로 중위순회 결과를 보면

해당 루트노드의 왼쪽 서브트리와 오른쪽 서브트리를 알 수 있다.

이를 재귀적으로 구현하면 트리 구조를 구현할 수 있고,

이를 후위순회하면  정답이 된다.

2. 문제풀이코드

#include <bits/stdc++.h>
using namespace std;

int n,pidx, preOrderRes[1001], inOrderRes[1001], order[1001];

struct Node{
    int data;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int _data, Node* _left, Node* _right): data(_data), left(_left), right(_right){}
};


void postOrder(Node* root){
    if(root== nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << ' ';
}

void deconstruct(Node* root){
    if(root == nullptr) return;
    deconstruct(root->left);
    deconstruct(root->right);
    root = nullptr;
    delete root;
}


Node* makeTree(int start, int end){
    if(start > end) return nullptr;
    
    Node* newNode = new Node(preOrderRes[pidx++], nullptr, nullptr);
    if(start==end) return newNode;
    int mid = order[newNode->data];
    newNode->left = makeTree(start, mid-1);
    newNode->right = makeTree(mid+1, end);
    return newNode;
}

void makeTree(Node** root){
    pidx = 1;
    *root = makeTree(1, n);
}



int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;
    for(int T=0; T<t; T++){
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> preOrderRes[i];
        }
        for(int i=1; i<=n; i++){
            cin >> inOrderRes[i];
            order[inOrderRes[i]] = i;
        }
        Node *root = nullptr;

        makeTree(&root);
        postOrder(root);
        cout << '\n';
        deconstruct(root);
    }

    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node* left;
    Node* right;

    Node(int _data, Node* _left, Node* _right): data(_data), left(_left), right(_right){};
};


void insert(Node** root,int value){
    Node* p = *root, *q = nullptr;

    while(p != nullptr){
        q = p;
        if(value < p->data){
            p = p->left;
        }
        else p = p->right;
    }

    Node* newNode = new Node(value, nullptr, nullptr);
    if(q == nullptr){
        *root = newNode;
    }
    else if(value < q->data){
        q->left = newNode;
    }
    else{
        q->right = newNode;
    }
}


void postOrder(Node* root){
    if(root== nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data << '\n';
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int num;
    Node* root = nullptr;
    while(cin >> num){
        insert(&root, num);
    }
    postOrder(root);

    return 0;
}