전공/알고리즘
-
백준 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부터 시작해서 인접한 곳에서 방문하지 않았던 지점 중 거리가 최소인 지점을 연결한다. 이 결과는 총 연결 거리의 최소를 만들어 내는 알고리즘이다. 하지만 문제에서 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하..
-
백준 1644(소수의 연속합)전공/알고리즘 2020. 6. 25. 00:53
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 겨울에 스터디하면서 서강대 raararaara님에게 배운 문제. 그치만 강의가 좋다고만 생각했지, 백준 문제 풀 생각은 전혀 안 했었다. 그러다가 오늘 친구가 풀어보라길래 그때 생각이 나서 강의록을 참조하였다. 이 문제는 부분합 문제이다. 부분합 문제는 여러가지 알고리즘이 있는데 이렇게 정렬된, 연속한 합을 구할 때는 투포..
-
백준 2206(벽 부수고 이동하기)전공/알고리즘 2020. 6. 25. 00:43
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N, M 이 마무리이고, 벽은 한번만 뚫을 수 있으며, 최단 거리로 간다. 모든 가능한 경우를 확인해서, 그 중 가장 짧은 거리를 출력한다. 위 조건들을 보고 이 문제는 무조건 dfs다 라고 생각했다. 하지만 시간초과의 문제에 봉착했고, bfs로 돌렸다. dfs의 시간초과 여부를 계산하는게 아직 많이 어렵다. 아 근데 dfs로 풀린 코드도 있다. 이게 어떻게 가능했는지..
-
백준 9019(DSLR)전공/알고리즘 2020. 6. 22. 16:06
https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net BFS에 대해서 좀 더 생각하게끔 해주었던 문제. 앞서 풀었던 치즈같이 queue 두 개를 이용해서 총 몇번의 횟수가 필요한지 구하려고 했었다. 하지만 문제는 문제에서 요구하는 바가 횟수가 아닌 경로였고, 경로를 구하려면 재귀의 방식이 필요하지 않을까 생각을 하였다. 재귀로 경로를 출력하기에 더 편리하게 느껴졌다. 경험이 있어서 그런지 그래서 재귀와 bfs를 동시에 사용하면 어떨까..
-
백준 2636(치즈)전공/알고리즘 2020. 6. 19. 15:07
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제에서 요구하는 게 무엇인지 제대로 파악하고, 논리를 구성해야 하는 문제. 치즈가 공기와 닿으면, 녹는다. 다 녹을 때 까지 얼마나 걸리는가, 녹기 직전 치즈의 양은? 가장 핵심은 먼저 초기에 공기와 닿는 치즈의 좌표를 구하는 일이었다. 가장자리의 공기부터 시작해서 이어진 모든 공기를 구분하고, 가장 처음 만난 치즈는 무조건 치즈의 가장자리가 되므로 그 좌표들을 치즈의 테두리로 정한다. 치즈의 테두리를 queue1..