해설35 [C/C++] 백준 11725: 트리의 부모 찾기(vector 이용) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 맨 처음에 문제에서 트리의 루트를 1로 둔다는 조건을 확인 못해서 맨 처음에 해맸다.. 구현!! 사실 간단하게 풀이가 가능하다. 이차원 백터 vectorv1[100001]를 선언하여 각 노드와 연결되어 있는 노드를 뒤에 추가해주면 된다. 이때 무엇이 부모이고 자식 노드인지 모르기 때문에 v1[tmp1].push_back(tmp2); v1[tmp2].push_back(tmp1); 두번 다 해줘야한다. 그 다음에는 queue를 이용하여 push와 pop을 해주면 .. 2023. 9. 17. [C/C++] 백준 1167: 트리의 지름 (다익스트라 풀이) https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 방법?? 문제 자체가 트리의 지름을 구하라고 하는데 이때 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다. 그렇기 때문에 모든 노드에서 DFS 혹은 다익스트라 알고리즘을 통해 가장 긴 거리를 구하려는 것이 첫번째 생각일 것이다. 하지만 이렇게 할 경우 각 정점마다 (V) 트리를 모두 순회하며 (V) 최댓값을 구해야하기 때문에 O(V^2)의 시간이 걸려 시.. 2023. 9. 15. [C++] Map을 이용한 tree 구현 (BOJ 1991: 트리순회) https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제를 직접 tree를 구현하여 풀지 않고 map을 이용하여 구현하였다. Map이란? map은 각 노드가 key와 value가 쌍을 이루고 있는 트리로 pair 객체로 저장되기 때문에 first-key로 second-value를 저장한다. 중복을 허락하지 않으며 기본 형태는 map m; 으로 key를 통해 value를 찾기 용이하게 되어있다. 그래서 map은 pair로 이루어진 se.. 2023. 9. 14. [C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다. 알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다. 1. 준비작업 1-1. vector adj_list[100001] 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector adj_list[100001]을 선언해주었다. 이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까.. 2023. 9. 13. 이전 1 2 3 4 5 6 7 8 9 다음
