트리

1. 개요 안녕하세요! 오늘 문제의 유형은 트라이입니다. 트라이는 문자열의 문자를 정점으로 하는 트리 자료구조인데요. 이번 문제는 트라이 응용이 필요한 문제였습니다. 저는 트라이를 중첩 구조로 구현하여 문자가 아닌 문자열 값을 가지게 구현한 다음 recursion하게 호출하여 삽입과 출력을 구현했어요! 2. 문제 풀이 문제에 제시된 그림을 통해 개미굴이 트리임을 알 수 있습니다. 여기서 각 트리 정점은 숫자가 아닌 문자열 정보를 가지고 있어야 해요. 그렇다면 문자열로 정점을 분류할 수 있을까요? 정답은 분류할 수 없다입니다. 그림을 확인해 보면 서로 다른 계층에 같은 문자열을 가지고 있음을 알 수 있어요. 그래서 문자열로 정점을 분류할 수 없습니다.  정점을 분리하기 위해서는 다른 논리적인 방법이 필요해..

1. 문제 풀이 문제 유형은 재귀를 사용한 dfs를 사용하여 풀이했습니다. 처음 문제를 읽고 얼리어답터를 어떻게 결정하는 것이 좋을지 감이 잡히지 않았습니다. 트리를 직접 그려서 분석해 본 결과 초기 얼리어답터가 되어야 하는 정점은 리프 노드를 자손으로 가지고 있는 정점이라는 사실을 어렵지 않게 도출할 수 있었습니다. 예제 입력 2를 위상으로 확인해 본 결과 자손을 리프 노드로 가지는 정점뿐만 아니라 추가적으로 얼리어답터를 결정해야 합니다. 따라서 현재 정점이 리프 노드를 자손으로 가지는지 여부 판단과 리프 노드를 자손으로 가지고 있진 않으나 얼리어답터로 지정해야 하는 경우를 판단하는 로직으로 크게 분류하여 구현하였습니다. 우선 리프 노드는 부모 노드와 연결된 간선 1개 만을 가집니다. dfs를 바탕으로..

1. 문제 풀이 문제 유형은 트리 + 다이나믹프로그래밍입니다. 트리의 독립 집합 중 크기가 큰 것을 찾아 출력하면 됩니다. 트리를 탐색하는 깊이 우선 탐색 로직을 구현합니다. 저는 void dfs(int cur)로 작성하였고, 정점 cur에 대해서 해당 정점을 '우수 마을'로 선택할지 안 할지에 따라 계산하여 구현했습니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; ty..

1. 문제풀이 "중복 방문 없이 임의의 두 도시 간을 이동하는 경로가 유일하도록 설계되었다"라는 문제의 설명은 도시와 도로가 트리 자료구조 형태를 가지고 있다는 의미입니다. 따라서 문제에서 요구하는 것은 트리의 지름을 구하라는 것이고 너비우선탐색을 두 번 진행하면 풀이할 수 있습니다.   임의의 정점에서 너비우선탐색을 진행, 가장 먼 도시의 정점 번호를 반환 1번에서 구한 정점에서 너비우선탐색을 진행, 가장 먼 도시까지의 거리가 정답임 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple..

1. 문제 풀이 connected component의 개수를 깊이 우선 탐색으로 셉니다. ( = group ) 이 그룹들을 모두 연결하기 위해서는 group - 1개의 간선이 필요합니다. 그룹들을 모두 연결했으면 간선의 총개수는 m + group -1 개가 됩니다. 트리의 간선은 n-1개이므로 그 이상의 간선들은 삭제하여야 합니다. 따라서 추가/삭제의 최솟값은 group - 1 + m +group - 1 - (n-1)이 됩니다. 2. 코드2-1. C++#include #include #include #include using namespace std;const char nl = '\n';int n, m, u, v;vector adj[100'005];vector vis(100'005);int main() ..

1. 문제 풀이 이진트리는 AVL임을 보장하는 조건이 나오지 않았습니다. 따라서 skewed 한 경우도 고려하여야 합니다. 우선 inorder와 postorder 순서를 통해 얻을 수 있는 정보가 있는지 확인해보아야 합니다. 문제에서 주어진 예제 코드는 노드가 3개뿐이라 분석하기엔 너무 작습니다. 정점 개수가 좀 더 많은 트리를 하나 세워서 확인해 보겠습니다. 정점의 개수 : 7inorder : 4 1 3 6 5 2 7postorder : 4 1 3 5 7 6 postorder를 통해서 처음 알 수 있는 사실은 제일 마지막 값인 6이 트리의 루트임을 알 수 있습니다. inorder는 root node인 6을 기준으로 왼쪽은 left 부분 트리이고, 오른쪽은 right 부분 트리입니다. inorder에서 ..

1. 문제 풀이 트리 자료구조에서 임의의 정점을 하나 삭제한 다음 깊이 우선 탐색을 하면서 리프 노드의 개수 카운팅하여 출력하는 문제였습니다. 정점 삭제함으로써 발생할 수 있는 상황을 분석해봐야 합니다. 1. 삭제한 노드를 자식으로 가지고 있는 부모 노드가 리프노드가 되는 경우가 있습니다.  이 경우 부모 노드를 리프 노드로 판단해 세워주어여합니다.2. 트리는 이진트리 구조가 아니어도 되며 루트 노드가 0이 아닌 경우도 존재합니다.  인접리스트로 트리를 구현하여 이진 트리 구조로 한정되는 것을 피할 수 있었으나 루트 노드가 0이 아닌 경우를 생각하지 못해 WA를 받았습니다.   2. 코드// Authored by : chjh2129#include using namespace std;int n;vector..