어흥

문제 링크: https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 1. 주의할 점 - 모든 간선의 총합 - MST를 연결할때 드는 최소 비용을 출력한다 - 매 TC마다 Par[] 배열을 초기화 한다 2. 구현 - 크루스칼 알고리즘을 통해 MST를 구현한다 - 입력받는 모든 간선에 대한 정보를 우선순위 큐에 삽입하고, 간선의 가중치가 오름차순이 되도록 정렬한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(in..

문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다(필자는 크루스칼 알고리즘을 통해 풀 예정이다) 2. 구현 - 크루스칼 알고리즘을 통해 해당 문제를 해결한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(int a, int b) 함수를 통해 A와 B의 부모가 일치하지 않는다면, 부모의 수가 작은쪽으로 합친다 - 입력받은 간선의 정보를 모두 우선순위큐에 넣고 간선의 크기가 작은것부터 뽑아서 사용한다 - Cycle이 생..

문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 1. 주의할 점 - 위상정렬을 사용할 줄 알아야 한다 2. 구현 - 선행되는 A의 Node에 후행되는 Node B를 추가한다. 그리고 Conn[B]++를 통해 B의 앞에 선행되는 Node가 증가되었음을 표시한다 - For문을 통해 Node 1~N까지 돌며 Conn[]의 값이 0이면 큐에 넣는다 - 큐에서 원소를 뽑으면서 해당 원소를 출력하고, 해당 ..

문제 링크: https://www.acmicpc.net/problem/10473 10473번: 인간 대포 문제 당신은 세계적인 인간대포 서커스 공연자이다. 즉, 당신은 거대한 가짜 대포 안으로 기어올라가 먼 거리를 발사되며 사람들에게 기쁨을 주는 사람인 것이다. 오늘, 당신은 혼자가 아니다. � www.acmicpc.net 1. 주의할 점 - 시작점에서는 대포가 없으므로 무조건 걸어가야 한다 - 다익스트라 알고리즘을 사용한다 2. 구현 - Cal() 함수를 통해 두 점 사이의 빗변의 길이를 반환한다(Hypot 내장함수를 처음알게 되었다) - Arr[][]배열을 통해 대포와 시작 및 도착점의 좌표를 저장한다 - 우선순위 큐를 이용한 다익스트라 알고리즘를 통해 대포를 이용하는 것이 빠른지, 걸어가는 것이 빠..

문제 링크: https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘을 이용하면서 어떤 방식으로 경로표를 저장할 것인지 고려한다 2. 구현 - 모든 간선들의 정보를 V[] 벡터에 저장한다 - 1~Node까지 모든 Node를 시작점으로 하여 다익스트라 알고리즘을 수행하면서 경로표를 구할 수 있도록 한다 - 시작점에서 출발하는 겨우 tmp.start를 다음 Node로 설정하고, 이외의 경우에는 tmp.start를..

문제 링크: https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 1. 주의할 점 - M의 개수가 주어져 있지 않다 - 정답의 개수는 항상 N-1개다. 즉, Dist[a]+ a->G = Dist[b]+b->G의 값이 같다면, MST를 이루는 간선들로 구하자 2. 구현 - 다익스트라를 통해 Node 1번에서 다른 Node들까지의 최단거리를 구하여 Dist[] 배열에 저장한다 - 최단거리를 이루는 간선을 구할때, 1번 Nod..

문제 링크: https://www.acmicpc.net/problem/10282 10282번: 해킹 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염�� www.acmicpc.net 1. 주의할 점 - 단방향 그래프다 - 다익스트라 알고리즘을 사용하면 되며, 매 TC마다 V[] 벡터와,Dist[] 배열을 초기화 해줘야 한다 2. 구현 - 입력받는 그래프의 정보를 V[]에 모두 저장한다 - 시작점을 기준으로 우선순위큐를 사용하여 다익스트라 알고리즘을 통해 각 Node까지의 최단거리를 구한다 - 1~Node의 수 만큼 확인하면서 Dist[]값이 Max가 아니면 Cn..

문제 링크: https://www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 1. 주의할 점 - 서로 같은 곳을 가리킬 수 있다 - 투 포인터를 이용한다 2. 구현 - 입력받은 수를 배열에 저장한 후, 정렬한다 - 투 포인터를 활용하여 L이 가리키는 값과 R이 가리키는 값의 차이를 비교하여 답을 도출한다 #include #include using namespace std; long long arr[100000]; int mai..