Tree
-
(백준 1967번 트리 지름 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 3 with gptPROGRAMMING/알고리즘 2024. 5. 1. 15:00
풀이가 감이 오질 않아 gpt에게 물어보고 나름 내 스타일대로 풀어보았다. 백준 1967번https://www.acmicpc.net/problem/1967 트리에서 가장 긴 거리를 구하는 문제인데, gpt는 2번의 dfs방법을 사용해서 풀었다.보고나니 당연하게 느껴졌지만, 처음에는 생각하지 못했다..ㅠ 우선 가장 긴 거리는 당연히! leaf에서 출발해서 leaf에서 끝날 것이다..!그렇다면 우선 root에서 시작에서 가장 멀리 있는 leaf를 찾은 다음( = farthestNode)farthestNode에서 다시 dfs를 통해 가장 멀리 있는 leaf를 찾으면 된다. 여기서 신박했던 점은 farthestNode와 maxDistance를 찾는 방법이다.dfs 매 실행마다 farthestNode와 max..
-
(백준 4803번 트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 2 with gptPROGRAMMING/알고리즘 2024. 5. 1. 14:37
오늘은 gpt 선생님에게 한 수 배웠다. 백준 4803번https://www.acmicpc.net/problem/4803 일단 gpt가 풀어준 풀이는 아래와 같다. § dfs(int node, int parent)를 정의해줘서 부모가 아닌데 방문된 노드를 만나면 순환이 있다고 판단§ 처음 시작은 dfs(node, -1)로 시작#include #include #include using namespace std;int n, m;vector> graph;vector visited;// DFS 함수, 순환이 있는지 체크bool dfs(int node, int parent) { visited[node] = true; for (int next : graph[node]) { if (!visi..
-
(백준 1068번 트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 1PROGRAMMING/알고리즘 2024. 4. 24. 20:22
오늘은 자료구조 Tree에 대해 배워보았씀당ㅎㅎhttps://blog.naver.com/PostView.naver?blogId=kks227&logNo=220788265724&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 트리(Tree) (수정: 2018-11-22)안녕하세요. DFS와 BFS를 다루면서 그래프에 대해서 소개해 드렸습니다. 그래프라는 개념은 알고리즘...blog.naver.com 백준 1068번https://www.acmicpc.net/problem/1068 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1..