본문 바로가기

전체 글73

프로그래머스 위클리 챌린지9주차 전력망을 둘로 나누기 1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 2. 풀이 정점의 개수가 n개인 트리에서 간선 하나를 제거했을 때 2개의 트리로 분리되는데, 이때 분리된 2개의 트리의 정점 수의 차이의 최솟값을 구하는 문제이다. 단순히 모든 간선을 한번씩 제거해 가면서, 각각의 경우에 BFS로 2개의 분리된 트리의 정점 수를 카운트하는 방식으로 해결했다. 위 방식은 O(n^2)인데, n의 최대가 100이기 때문에 가능했다. .. 2021. 10. 6.
백준 1967 트리의 지름 1. 문제 링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이 위 사진처럼 자식 노드부터 순차적으로 탐색해 나가면서 부모 노드로 올라갈 때에는 최댓값 2개를 골라 더해준 후 정답 값보다 크면 정답 값을 업데이트해 준다. 그러고 나서 리턴 값으로는 자식에서 올라온 값 중 가장 큰 값을 리턴해 준다. #include #include #include using namespace std; class Element { p.. 2021. 10. 5.
백준 2407 조합 1. 문제 링크 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 2. 풀이 파스칼의 삼각형에서 제시하는 점화식을 활용해 DP방식으로 풀 수 있다. 문제는 long long 타입조차 감당 안될 정도로 숫자가 커진다는 것. 따라서 숫자 표현을 string으로 해야 한다. #include #include #include using namespace std; int n, m; string arr[101][101]; string StringPlus(const string& s1, const string& s2) { string result = ""; int tmp; a.. 2021. 10. 3.
백준 11779 최소비용 구하기 2 1. 문제 링크 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이 전형적인 최단거리 문제이다. 다만 최소비용을 갖는 경로를 출력하는 부분이 추가되었다. 이 부분은 각 정점마다 최소 비용이 결정되는 시점에, 해당 정점으로 오기 바로 직전 정점을 별도의 배열에 표시해 둠으로 서 해결했다. //n(1≤n≤1,000)개의 도시 => 정점 //m(1≤m≤100,000)개의 버스 => 간선 #include #inc.. 2021. 10. 3.

티스토리툴바