어흥

문제 링크: www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 1. 주의할 점 - 우선순위큐를 사용한 다익스트라를 이용하지 않은 경우 TLE가 날 확률이 크다 - 조건들을 잘 살핀다 2. 구현 - 모든 간선에 대한 정보를 입력 받아서 V[] 벡터에 넣는다 - Dist[][]배열을 전부 최대로 초기화한 이후, 맥세권과 스세권을 다익스트라 알고리즘을 통해 구한다 - 집에서 맥세권과 스세권까지의 최대거리를 넘지 ..

문제 링크: www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1. 주의할 점 - 이분탐색 + 다익스트라를 이용하여 문제를 해결한다 2. 구현 - 2가지의 방법으로 풀었으며, 다익스트라는 우선순위큐를 활용하여 푸는 방법이 훨씬 빠르다 - Result의 값은 -1로 초기화한다(N번 컴퓨터까지 도달하지 못할 경우를 대비) - Dijkstra() 함수만 바뀐다 - 메인 함수에서 케이블선에 대한 정보를 받을 때, 케이블선의 최..

문제 링크: https://www.acmicpc.net/problem/11085 11085번: 군사 이동 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재�� www.acmicpc.net 1. 주의할 점 - 가중치가 큰 간선들부터 연결을 한다 - 크루스칼 알고리즘을 사용한다. 단, 종료조건이 다르다 2. 구현 - 입력 받는 간선에 대한 정보를 우선순위큐에 저장하며, 가중치의 내림차순으로 정렬한다 - 우선순위큐에서 간선에 대한 정보를 1개씩 빼면서 만약 2개의 도시가 이어져 있지 않다면 연결하고, Result에 해..

문제 링크: https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우� www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다 - 이미 연결되어 있는 경우, 어떻게 처리할 것인지 고민한다 2. 구현 - 크루스칼 알고리즘을 통해 MST를 해결한다 - 모든 우주신들의 좌표를 X[], Y[] 배열에 저장한다 - 이미 연결된 통로의 정보를 입력받아 Make_union(a,b) 함수를 통해 A와 B의 부모를 일치시킨다 - 서로 다른 신과 그 사이의 거리를 Ca..

문제 링크: 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/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/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경이의 시작 위치에서 주유소 까지의 거리, 그리고 b(1 ≤ b ≤ 100)는 그 주유소에서 채울 수 있는 연료의 양을 의미한다. 그리고 N+2번째 줄에는 두 정수 L과 P가 주어지는데 L(1 ≤ L ≤ 1,000,000)은 성경이 www.acmicpc.net 1. 주의할 점 - 입력 받는 주유소의 정보가 거리순이 아니다 2. 구현 - 주유소의 정보를 우선순위 큐 PQ2에 입력받..

문제 링크: https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 www.acmicpc.net 1. 주의할 점 - 총 합(Result)이 Int범위를 벗어날 수도 있으므로 Long Long으로 설정한다 2. 구현 -..