소스코드33 [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++] 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. [C/C++] 백준 11404: 플로이드 (플로이드-워셜 알고리즘) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘? 알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다. 특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 .. 2023. 9. 11. 이전 1 2 3 4 5 6 ··· 9 다음
