전공
-
백준 13549(숨바꼭질3)전공/알고리즘 2020. 6. 29. 15:11
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 어떻게 하면 원하는 값까지 도달할 수 있을까. dfs는 한곳을 엄청 깊게 판다. 그래서 원하는 값까지 도달하더라도 그 값이 최솟값이 아닐 가능성이 농후하다. 그래서 bfs bfs에 단순 queue로 구성을 하려니 순간이동할때는 시간 소모가 안된다고 한다. 그래서 만약 단순 queue로 구성을 한다고 하면 경로는 더 길지만 시간이 적게 걸리는 경우를 확인하지 ..
-
백준 1916(최소비용 구하기)전공/알고리즘 2020. 6. 29. 14:33
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 제발 문제좀 제대로 읽자. 조건을 제대로 파악해야 찾을 수 있다. 그냥 다 익스트라로 풀린다. priority_queue를 이용한 다 익스트라의 일반적인 시간복잡도는 O(ElogV)이고 이 문제에서는 V = 1,000 E = 100,000 이므로 10^5로 간단하게 풀린다. 1. 하지만 이전 문제에서의 문제와 같이 한 지점에서 다른 지점까지의 경로는 하나 이상일 ..
-
백준 1753(최단경로)전공/알고리즘 2020. 6. 29. 14:06
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 엄청 단순한 다익스트라 문제. 문제에서 요구하는 바가 무조건 다익스트라이다. 근데 고비가 있었다. 이제까지 인접행렬로 문제를 풀었었기 때문에 이 문제 또한 인접행렬로 문제를 풀려고 했지만, vertex가 20,000 이므로 만약에 인접행렬로 푼다면 20000*20000 4억 메모리제한에 걸리게 된다. 따라서 인접리스트로 문제를 풀어야한다. 인접리스트를 사용하려면 vect..
-
백준 2665(미로만들기)전공/알고리즘 2020. 6. 28. 16:40
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net N^2의 격자에 흰색과 검은색이 존재한다. 검은색은 벽으로 이루어져서 지나갈 수 없다. 하지만 벽을 부술 수 있다. 최소 몇번의 벽을 부셔야 시작점에서 종료지점까지 갈 수 있는가 어디 지점에서 어디 까지 가는 방법 => dfs, bfs 사실 먼저 dfs를 생각했다. dfs의 재귀함수로 몇 번의 벽을 부술지 기록하기가 더 쉽다고 생각했지만, 역시 문제점은 시간 만약에 dfs로 구현하게 된다면 벽이 보이는대..
-
백준 1719(택배)전공/알고리즘 2020. 6. 28. 15:51
https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net N개의 점이 있을 때, 각각의 점에서 나머지 점까지 최단 경로로 이동할 때, 가장 먼저 거쳐가야 하는 점을 찾는 문제이다. N개의 점에서 나머지 N개의 점까지의 최단 거리를 구하는 문제 => 플로이드 와샬 O(N^3) 200^3 = 8*10^6이므로 시간복잡도에서 문제가 되지 않는다. 그럼 이제 최단경로로 이동한다고 했을 때, 가장 먼저 들려야 하는 지점을 찾는게 문제인데 플로이드 와샬의 작..
-
백준 1504(특정한 최단 경로)전공/알고리즘 2020. 6. 26. 17:50
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존� www.acmicpc.net 1번 집에서 주어진 두 집(n1, n2)을 거친 후 N번째 집까지 가는 거리 중 최단 거리를 구하는 문제이다. 위 문제에서 양방향은 같은 간선의 길이를 가지므로, 1번에서 두 집을 거쳐서 N까지 가는 경우의 수는 두가지이다. 1 -> n1 + n1 -> n2 + n2 -> N vs 1 -> n2 + n2 -> n1 + n1 -> N 위에 화살표들은 연..
-
백준 1238(파티)전공/알고리즘 2020. 6. 26. 17:41
https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 모든 N개의 집에서 X까지 왕복하는 거리 중 최대 거리를 구하는 방법 1->X + X->1 2->X + X->2 . .. N->X + X->N 최단거리를 구하는 알고리즘이 필요하다는 걸 알 수 있다. X에서 나머지집까지의 거리를 구하는 알고리즘이 쉽게 있다. 한 지점에서 모든 다른 지점까지의 최단거리를 구하는 다익스트라 그러면 이제 나머지 N개에서 X까지의 거리를 구하는 알고리즘이 필요하다 ..
-
백준 2211(네트워크 복구)전공/알고리즘 2020. 6. 25. 13:55
https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 모든 연결이 끊겨 있는 상태에서 어떤 조건들을 만족하면서 최소의 연결방법을 구하는 문제이다. 어떤 조건을 빼고 보면 최소 스패닝 트리라고 보면 된다. 1부터 시작해서 인접한 곳에서 방문하지 않았던 지점 중 거리가 최소인 지점을 연결한다. 이 결과는 총 연결 거리의 최소를 만들어 내는 알고리즘이다. 하지만 문제에서 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하..