+1-1 Techinque- 아래와 같은 문제가 있다.1차 수직선 상에서 가로 n개의 선분이 주어졌고 어떤 임의의 세로 수직선을 그었을 때,만나는 서로 다른 선분의 개수는? 답: 3개 - 그림을 통해 봤을 때 당연히 3개라는 것은 알 수 있지만, 이를 컴퓨터로 구현하기 위해서는 어떻게 해야 할까? - 바로 1차 선분의 시작점과 끝점에 각각 +1과 -1을 붙이는 것이다. - 시작점과 끝점의 가중치 값을 부여하고 빨간선 앞쪽에 있는 가중치 값들 모두 더해주면 답이 나오게 된다. - 이 점을 활용하면 주어지는 모든 선분 N개를 각각 2개의 시작점, 끝점으로 구분하여 총 2N개의 점으로 나눠 이를 x좌표 순으로 오름차순 정렬한 뒤, x = k보다 커지기 직전까지의 숫자를 전부 더하는 식으로 진행해볼 수 있다. ..

1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 문제 설명 2. 입출력 조건 및 예제 입력 조건 (1) 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) (2) 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. (3) 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 출력 조건 (1) ..

1. 개념 설명 (1) 다익스트라는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. ( 이것을 줄여서 최단 경로 알고리즘이라고 부른다. ) (2) 다익스트라는 그래프 방향의 유무는 상관없으나, 간선들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. (3) 만약 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용한다. ( 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면, 무한히 음의 사이클을 도는 경우 합이 음수 무한대로 발산하기 때문에 최단 경로를 구성할 수 없다. ) 2. 과정 - 실제로 수행되는 과정이며, 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록하고 있다. 3. 입출력 조건 ..

1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. 문제 설명 2. 입출력 조건 및 예제 입력 조건 (1) 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. (2) 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. (3) 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가..