C++106 [백준][bfs] 1967 트리의 지름 c++ 구현 목차 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 문제 구현 방향 나는 리프 노드부터 bfs탐색을 시작하여 가중치를 더해준 후 그 중 가장 큰 가중치를 출력하는 방식으로 구현하였다. 가중치를 계속해서 누적해주는 것은 dp에서 착안하였다. 문제 풀이 시 주의할 점 그냥 인접행렬로 만들게 되면 메모리를 굉장히 많이 먹기 때문에 메모리 초과 오류에 빠진다. 따라서 구조체를 만들고 인접리스트를 사용하여 간선과 노드를 저장하.. 2024. 2. 24. [백준][다익스트라] 1916 최소비용 구하기 c++ 구현 목차 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 구현 방향 다익스트라 알고리즘을 이용해 구현했다. 다른 bfs나 dfs를 사용하게 되면 시간초과가 뜰 것이다.. 구현 시 주의할 점 처음 가중치를 설정할 때 최대 가중치를 10만을 약간 넘게 잡으면 틀린다. 그이유는 목표 노드까지 가는 비용의 최대치가 10만이 아니기 때문이다. 따라서 훨씬 10만 보다 큰 수로 해주어야 한다. 노드에 비해 간선의 수가 .. 2024. 2. 23. [백준][크루스칼] 1197 최소 스패닝 트리 c++ 구현 목차 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 보기 전에 참고하면 좋을 것 같습니다 https://be-senior-developer.tistory.com/29 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs,.. 2024. 2. 22. [백준][union find] 1717 집합의 표현 c++ 구현 목차 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 보기 전에 참고하면 좋을 것 같습니다 https://be-senior-developer.tistory.com/29 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를.. 2024. 2. 22. 이전 1 ··· 20 21 22 23 24 25 26 27 다음 728x90
