PS 일지

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 요약 가중치 있는 유향 그래프가 주어지고 시작 정점과 도착 정점이 주어졌을 때, 시작 정점에서 도착 정점까지의 경로의 가중치 합의 최솟값을 구하고, 경로에 속한 정점들을 방문 순서대로 출력하는 문제이다. 접근 기본 다익스트라 알고리즘에서 경로 추적을 해야 한다. 다익스트라를 수행하면서 정점들이 지나온 경로들을 새로운 2차원 벡터 R에 저장하였다. 벡터 R[i]..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 요약 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 더보기 이분 그래프(Bipartite Graph)? 그래프의 정점의 집합을 둘로 분할했을 때, 각 집합에 속한 정점끼리 서로 인접하지 않게 할 수 있는 그래프이다. 접근 이분 그래프를 모르는 상태에서 문제를 접하다보니 구현에 실수가 조금 있었다. 양방향 그래프를 입력 받고, visit배열을 통해 방문 여부를 확인하며 평범한 DFS를 구..

https://www.acmicpc.net/problem/3769 3769번: 최댓값 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 한 줄이고, $m, p, a, b$로 이루어져 있다. ($m \le 2000, p \le 12, p$는 짝수) 항상 주어진 조건을 만족하는 \(x_1, x_2, \dots, x_m\)이 존 www.acmicpc.net 문제 요약 $m$개의 수 $x_1, x_2, \cdots, x_m$을 정수 $a$, $b$에 대하여 다음과 같이 정의한다. $(a > 0)$ 1. $\quad -\frac{1}{\sqrt{a}} \le x_i \le \sqrt{a}$ 2. $\quad x_1+x_2+\dotsb+x_m=b\times\sqrt{a}$ 자연수 $m$과 정수..

https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 문제 요약 주어지는 연립 방정식의 해를 구하는 문제이다. 접근 행렬 크기의 제한이 6 X 6으로 매우 넉넉하다. 가우스 소거법을 직접 구현하면 된다. 가우스 소거법을 모르더라도, 연립 방정식을 푸는 과정을 직접 코드로 구현하자. 어느 쪽이던 다소 번거로운 것 같다. #include using namespace std; int main() { int N; doubl..

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

https://www.acmicpc.net/problem/2405 2405번: 세 수, 두 M n개의 정수 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..