Algorithm/BOJ4 [BOJ] 백준 11404 플로이드 (python 파이썬) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이에 앞서 백준 11404 플로이드 문제는 플로이드-워셜 알고리즘을 이용한 문제이므로 플로이드-워셜 알고리즘을 이해하고 있으면 좋습니다! 플로이드-워셜 알고리즘 관련해서 제가 최근에 정리해둔 글도 있으니 참고해주시면 이해가 더 쉬우실 거에요! https://zerozero909.tistory.com/41 [Algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘 플로이드 워.. 2023. 4. 18. [BOJ] 백준 11657 타임머신 (파이썬 python) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음수 간선이 있을 수 있으므로 벨만포드 알고리즘을 사용해야한다. 출력 부분에서 "시간을 무한히 오래 전으로 되돌릴 수 있다면" = 음수사이클이 있다면 Step1 문제 분석하기 시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 것이다. 이렇게 시.. 2023. 4. 15. [BOJ] 백준 1753 최단 경로 구하기 (python 파이썬) 백준 1753 최단 경로 구하기 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 Step 1 문제 분석하기 문제 모든 간선의 가중치가 10 이하의 자연수. 자연수는 양수이므로 모든 간선이 양수 -> 백준 1753은 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 수행 과정 거리 리스트에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다. 즉, 우선순위 큐에서 데이터를 뽑아온다. .. 2023. 4. 13. [BOJ] 백준 11399 ATM (파이썬 python) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘, 삽입 정렬 인프런 강의를 보고 참고하였습니다~ Step 1 문제 분석 ATM에서 모든 사람이 가장 빠른 시간에 인출하는 방법을 그리디 방식으로 해결한다. ATM 앞에 있는 사람 중 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 것이 곧 그리디 방식이다. 이를 위해서는 인출 시간을 기준으로 값을 정렬해야한다. (오름차순) 정렬을 마친 후에는 각 사람이 돈을 인출하는데 필요한 시간을 .. 2023. 3. 23. 이전 1 다음
