윤깡패 블로그

문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리(Tree) 자료구조 트리(Tree) 자료구조 트리(Tree) 자료구조 노드와 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리 soobin0821.tistory.com 코드 #include #include using namespace std; voi..

트리(Tree) 자료구조 노드와 노드가 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 정보의 단위 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리의 최상단 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리의 최하단 노드 (자식 노드가 없는 노드) 서브 트리 : 전체 트리에 속한 작은 트리 트리의 특징 순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다. 데이터베이스 시스템이나..

문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다. (진실을 아는 사람 데이터, 파티 데이터) 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결한다. 각 파티의 대표 노드와 진실을 아는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단한다. 유니온 파인드(Union-Find) 알고리즘..

유니온 파인드(Union-Find) 알고리즘 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산 + 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 유니온 파인드 알고리즘 핵심 이론 union 연산 각 노드가 속한 집합을 1개로 합치는 연산 void unionfunc(int a, int b) { // a와 b의 대표 노드 찾기 a = find(a); b = find(b); if(a != b) { parent[b] = a;// 두 원소의 대표 노드끼리 연결 } } find 연산 자신이 속한 집합의 대표 노드를 찾는 연산 int find(int a) { if(a == parent[a]) { return a;// a가 대표 노드면 반환 } else { // a의 대표 노드값을 find..