빅맥좋아요

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 백준 1238번 파티 문제를 풀었다. 최단 경로 중에 가장 긴 경로를 구하는 문제다. 입력 N이 최대 1000개라서 플로이드 와샬 알고리즘은 사용할 수 없다. 간선의 가중치에 음수가 없어서 다익스트라 알고리즘을 사용했다. X마을로 갔다가 다시 자신의 마을로 최단 경로를 통해서 돌아오고 이 값을 기록해야한다. 먼저 X마을로부터 다른 마을까지의 최단 경로를 다익스트라 알..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 백준 1613번 역사 문제를 풀었다. 플로이드 와샬 알고리즘을 응용해서 푸는 문제다. 예제를 입력받고 플로이드 와샬 알고리즘을 수행한 후의 dist배열을 살펴보자. dist 1 2 3 4 5 1 0 1 1 2 INF 2 INF 0 1 1 INF 3 INF INF 0 1 INF 4 INF INF INF 0 INF 5 INF INF INF INF 0 dist[i][j]의 값이 INF가 아니라는..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 백준 1916번 최소비용 구하기를 풀었다. 최대 N이 1000이므로 플로이드 와샬로는 풀 수 없다. 그래서 인접리스트를 이용한 다익스트라 알고리즘으로 풀었다. 같은 시작 노드 u와 같은 도착 노드 v에 대해 다른 비용의 입력이 들어 올 수 있다. 예를 들어 2 3 2와 2 3 10이 입력으로 들어 올 수 있다. 그러면 비용이 더 큰 버스에 대해선 연산을 건너 뛰어..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 백준 10159번 저울을 풀었다. 예제 1번의 입력을 넣었을 때 dist 배열이다. dist 1 2 3 4 5 6 1 0 1 2 3 INF INF 2 INF 0 1 2 INF INF 3 INF INF 0 1 INF INF 4 INF INF INF 0 INF INF 5 INF INF INF 1 0 INF 6 INF INF INF 2 1 0 dist[i][j] INF가 아니면..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 백준 1956번 운동을 풀었다. dist[i][i]를 INF로 놓고 플로이드 와샬 알고리즘을 수행하면 i번 노드에서 i번 노드로 가는 최소 비용이 dist[i][i]에 저장된다. 아래는 전체 코드입니다. #include #include #include #include #include #pragma warning(disable:4996) using namespace..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 백준 2458번 키 순서를 풀었다. 먼저 플로이드 와샬 알고리즘으로 전체 노드의 비용을 구한다. 예제 1을 인풋으로 넣었을 때 dist배열이다. 1 2 3 4 5 6 1 0 2 INF 2 1 3 2 INF 0 INF INF INF INF 3 INF 2 0 1 INF 2 4 INF 1 INF 0 INF 1 5 INF 1 INF 1 0 2 6 INF INF INF INF INF 0 그 다음 알아볼 노드..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 백준 11404번 플로이드를 풀었다. 플로이드 와샬 알고리즘을 사용해서 푸는 문제다. 입력받을 때 시작 노드와 도착 노드가 같지만 비용이 다른 버스를 유의해야 한다. 출력할 때 dist배열에 INF로 정한 값이 있다면 갈 수 있는 경로가 없는 것이므로 0으로 바꿔줘야 한다. 아래는 전체 코드입니다. #include #include #include #include #include using name..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 11403번 경로 찾기를 풀었다. 플로이드 와샬 알고리즘을 처음 사용해봤다. 플로이드 와샬 알고리즘은 모든 노드 사이의 최단 경로를 구할 수 있는 알고리즘이다. 2차원 인접 행렬이 주어졌을 때, 삼중 반복문을 사용해서 경로를 계산하기 때문에 시간복잡도는 O(n^3)이다. 인접 행렬의 값을 이용해서 dist배열을 초기화 시킨 후에 반복문을 수행하면 된다. dist[i][j] 는 i 노드에서 출발해서 j 노드에 도착하는 최단 거리이다. ..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 백준 3020번 개똥벌레를 풀었다. 석순과 종유석을 따로 입력받아서 정렬시킨다. 그 다음 이분탐색을 통해 높이에 따라 부딪히는 횟수를 구하고 min값과 비교한다. 최솟값이 갱신되면 카운트값을 1로 바꾼 후 반복문을 진행하고 최솟값과 똑같은 횟수라면 카운트값을 증가시킨다. 그러면 석순과 종유석을 부딪히는 횟수의 최솟값과 그런 구간의 개수를 구할 수 있다. 아래는 전체 코드입니다. #include #in..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준 11660번 구간 합 구하기 5를 풀었다. 2차원 배열에서 구간 합을 구하는 문제다. 행 별로 누적 합을 구한 뒤에 각 행마다 구간 합 연산을 해주면 된다. 1 2 3 4 1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7 처음 입력 받은 배열이다. 0번째 index는 생략했다. 행 별로 누적 합 연산을 해보면 아래 표처럼 바뀐다..