PS 일지

https://www.acmicpc.net/problem/1005 1005번: ACM Craft첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부www.acmicpc.net 문제 요약정점에 가중치가 있는 방향 그래프가 주어졌을 때, 최초 진입 차수가 0인 정점에서부터 지정된 정점까지 가는 경로의가중치 합의 최솟값을 구하는 문제이다. 접근기본적인 위상 정렬 문제이다. 배열 deg를 선언하여 i번 정점을 자손으로 두는 정점의 개수를 저장한다. 다시 말해, 진입 차수를 나타내는 배열이다.deg배열과 큐 자료 구조를 이용하여 위상 정렬을 수행한다.사전에 배열 d를 선언하여..

https://www.acmicpc.net/problem/2405 2405번: 세 수, 두 Mn개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c)www.acmicpc.net 문제 요약주어지는 N개의 정수 중 세 개의 수를 골랐을 때 중위값과 평균값의 차이의 최댓값을 세 배 곱하여 출력하는 문제이다. 접근선택된 세 개의 수를 오름차순으로 $a, b, c$라고 하자. 중위값은 $b$이고, 평균값은 $\dfrac{a+b+c}{3}$ 이다.세 배 곱하여도 최대인 경우의 $a, b, c$는 변하..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 문제 요약$N$개의 정점과 $N$개의 간선으로 이루어진 방향 그래프가 주어졌을 때,그래프에서 사이클을 이루지 않는 정점의 개수를 구하는 문제이다. 접근DFS를 수행하며 사이클을 찾고, 사이클을 이루는 정점의 수를 파악해야 한다.사이클 찾기정점이 최대 10만 개이기 때문에 방문 여부를 저장하는 배열 visit을 선언하고,반복문을 통해 방문하지 않은 점에 대해 1번 정점부터 N번 정점까지 DFS를 수행하며 사..