트리 썸네일형 리스트형 유니온파인드(Union Find) 1234567891011121314151617181920212223242526272829#include#include#includeusing namespace std;int n, m;vector p;int findP(int n) { if (p[n] 더보기 BOJ(백준) 2504 - 괄호의 값 아이디어 짝을 맞추는 것이기 때문에 스택(Stack)이 아닐까 생각을 했는데, 조금 까다로웠다. 다른 괄호가 껴있다보니? 스택의 냄새가 너무 강해서, 발상의 전환을 하기까지 시간이 조금 오래 걸렸다. 그러다보니 트리의 관점에서 트리는 선형자료구조로 표현을 할 수가 있었다는 것이 생각이 났고, 트리의 후위순회로 한번 풀어볼 수 있을 것 같았다. 해당 문자열 "(()[[]])([])"의 인덱스(index)는 1번부터 시작한다고 가정했을 때, 루트노드를 0번으로 잡는다고 하자. 일단, 올바른 문자열이 아닐 조건은 크게 3가지로 나눌 수 있다. 1. ((() (열려있는 상태로 끝나는 형태)2. ())) (열려있지 않는데 닫는 형태)3. (] or [) (괄호의 짝이 맞지 않는 형태) 이것에 대한 정리는 트리에서.. 더보기 BOJ(백준) 6416 - 트리인가? https://github.com/jongwuner/Algorithm/blob/master/BOJ/6416.cpp아이디어 자세히 봐야 알지만 문제에서 '트리'까지는 명시를 해줬지만, 루트가 있는 트리(rooted tree)라는 정보는 숨겨주었다. 어느정도 트리를 경험해본 사람 입장에서는 빨리 캐치했을 것으로 보이지만, indegree가 없는 노드가 루트라는 것을 캐치해내야 한다. 점검해볼 사항- 트리의 정의 : 트리는 공집합도 트리이다. - 루트가 있으면 방향성이 정해진다. (- 방향성이 정해져있는 트리라면, 루트가 있는 것)- indegree가 두개일 수 없다 시간복잡도 O(t*N) : N은 트리의 노드 개수(에지개수 = 노드개수 - 1), t는 테스트케이스 갯수. https://github.com/j.. 더보기 BOJ(백준) 1949 - 우수마을 https://www.acmicpc.net/problem/1949 자료구조(트리, 트리의 독립집합)N개의 노드로 구성된 트리가 있으며, 트리에는 가중치가 있다. 트리의 '독립집합'을 구성할 때, 가장 가중치가 큰 독립집합의 원소 가중치의 합을 구하는 프로그램을 작성하시오. 시간복잡도 : O(N)트리 임을 명시해줬고, 문제에서 트리에 대한 개념적 속성까지 다 명시해줬다. 점검해볼 사항 - 트리의 독립집합- 트리와 DP는 다 후위탐색인가? https://github.com/jongwuner/Algorithm/blob/master/BOJ/1949.cpp 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#.. 더보기 BOJ(백준) 3482 - Labyrinth https://www.acmicpc.net/problem/16437 자료구조(트리), 트리의 지름R x C(3 더보기 BOJ(백준) 1068 - 트리 https://www.acmicpc.net/problem/1068 자료구조(트리), 리프노드, 차수, 트리 방향성루트 있는 트리가 주어지고, 각 노드들의 부모노드가 주어진다. 어떤 한 노드를 제거 했을 때, 남는 리프노드(단말노드)의 개수를 구하는 프로그램을 작성하라. 시간복잡도 : O(N) N은 트리 노드의 개수 점검해봐야 할 부분-루트가 있는 트리의 방향성-리프 노드의 성질 https://github.com/jongwuner/Algorithm/blob/master/BOJ/1068.cpp 1234567891011121314151617181920212223#includeint p[50], a, c[50];int main(){ int n, d; scanf("%d", &n); for (int i = 0; i.. 더보기 BOJ(백준) 11725 - 트리의 부모찾기 https://www.acmicpc.net/problem/11725 자료구조(트리), 트리 순회루트가 1인 트리가 주어지면(트리의 속성 : 정점N개, 간선N-1개), 2번 ~ N번 노드의 부모노드를 출력하는 프로그램을 작성하라 시간복잡도 : O(N)N은 트리의 정점 개수 점검해봐야할 부분- 부모를 기억한 채로 순회- 루트가 주어지면 방향성도 이미 정해진 것 https://github.com/jongwuner/Algorithm/blob/master/BOJ/11725.cpp 12345678910111213141516171819202122232425262728#include#include#define MAX 100005using namespace std;vector adj[MAX];bool visit[MAX].. 더보기 BOJ(백준) 4803 - 트리 https://www.acmicpc.net/problem/4803 자료구조(트리), 연결요소, 그래프의 정점과 간선이 주어지면, 포레스트(트리의 집합)속에서 트리의 갯수를 찾는 프로그램을 작성하라. 시간복잡도 : O(N) N은 포레스트 내에 정점 개수. 연결요소 검사를 하고나서 다시 중복으로 확인하지 않는다. 점검해봐야 할 부분-자료구조를 왜 깊게 공부해야 하는지 교훈을 주는 문제. (노드의 개수 = 간선의 개수 - 1)+순수 자료구조의 속성에 대해 증명해보고 체화되어있지 않으면 문제를 너무 어렵게 풀게 된다.- 트리는 방향성 없는 상태에서 사이클이 없는 연결요소라는 개념- 그래프와 트리에서의 사이클 판단은 다르다.- 사이클찾는 아이디어(visit, finish 자료구조)? 총 연결요소 개수 - 사이클 .. 더보기 이전 1 2 다음
