분류 전체보기
-
백준 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부터 시작해서 인접한 곳에서 방문하지 않았던 지점 중 거리가 최소인 지점을 연결한다. 이 결과는 총 연결 거리의 최소를 만들어 내는 알고리즘이다. 하지만 문제에서 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하..
-
6/25일상 2020. 6. 25. 12:30
얼마 전 친구와 밥을 먹으면서 좋아하는 드라마에 대해서 이야기 하였다. 최근에 '나의 아저씨'를 다시 정주행하고 있다니깐 그 친구는 제목이 좀 더러워서 볼 생각을 안 했다고 한다. 별 생각은 안했었지만 이선균과 아이유와의 나이차이를 생각해보니 좀 그럴 것 같다고 생각했다. 하지만 드라마의 내용은 둘의 사랑얘기가 아니다. 이렇게 제목만 보고 드라마의 내용을 생각하는 것처럼 내 시야도 그렇다. 기대는 줄어들고 기준은 확고해진다. 작은 걸 보고 큰 거를 알 수있다고 생각한다. 경험은 무섭다 경험하고 나면 무던해진다. 새로움이 없어지고, 설레임이 없어지며, 슬픔은 줄어든다. 감정의 폭이 얕아진다. 사실 작년까지만 해도 나는 운동선수에 대한 로망이 있었다. 운동하면 즐겁고, 설레고 했었던 일들이 계속 하다보니 그..
-
-
백준 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로 풀린 코드도 있다. 이게 어떻게 가능했는지..
-