코딩/백준 (Python) 검색 결과
183 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 11404번: 플로이드 (Python)

접근 문제 풀이에 앞서 플로이드 와샬 알고리즘이 무엇인지 공부해보았다. 이전에 풀었던 다익스트라 알고리즘이 하나의 점에서 출발했을 때 모든 정점까지의 최단 경로를 구했다면, 플로이드 와샬 알고리즘은 모든 점에서 모든 점까지의 최단 경로를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는것이다. 문제의 예제 입력에 주어진 버스 노선을 그래프로 표시하면 아래와 같다. (중복되는 버스 경로는 최소값만 저장) 그리고 이를 n * n 크기의 표로 표시하면 아래와 같다. 0 2 3 1 10 INF 0 INF 2 INF 8 INF 0 1 1 INF INF INF 0 3 7 4 INF INF 0 이 표는 현재까지 계산된 최소 이동비용이다. 이 표를 계속 갱신하여 최종적으..

2021. 4. 21. 22:02
코딩/백준 (Python)

백준 11657번: 타임머신 (Python)

접근 최단 경로 참고 문제: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python) 백준 1753번: 최단경로 (Python) 접근 이전의 이분 그래프 문제와 풀이 과정이 비슷했다. 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1707번: 이분 그래프 (Python) 백준 1707번: 이분 그래프 (Python) 접근 이분 그래프가 무엇인지부터 찾 ca.ramel.be 기본적으로는 기존에 풀었던 최단 경로 문제에 음수 가중치를 더해주는 것 같이 보인다. 하지만 음수 가중치 때문에, 다익스트라 알고리즘을 이용할 수는 없고, 시작 노드에서 다른 모든 노드까지의 길이를 추적하는 벨만 포드 알고리즘을 이용해야 한다. (풀고 나서야 이것이 벨만..

2021. 4. 21. 00:46
코딩/백준 (Python)

백준 9370번: 미확인 도착지 (Python)

접근 바로 이전에 풀었던 다익스트라 알고리즘 문제에 추가적인 알고리즘을 더하여 해결할 수 있다. 다익스트라 알고리즘 기본 문제: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python) 백준 1753번: 최단경로 (Python) 접근 이전의 이분 그래프 문제와 풀이 과정이 비슷했다. 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1707번: 이분 그래프 (Python) 백준 1707번: 이분 그래프 (Python) 접근 이분 그래프가 무엇인지부터 찾 ca.ramel.be 문제를 해결하는 방법에는 두가지 정도의 방법이 있고 이는 다음과 같다. start - g - h - end 루트나 start - h - g - end 루트를 계산하여 st..

2021. 4. 18. 09:20
코딩/백준 (Python)

백준 1504번: 특정한 최단 경로 (Python)

접근 바로 전 문제인 최단 경로 문제와 유사하지만 특정 경로를 거쳐야 한다는 점과 방향성이 없다는 점을 고려하여 풀어주면 된다. 최단 경로 문제 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python) 백준 1753번: 최단경로 (Python) 접근 이전의 이분 그래프 문제와 풀이 과정이 비슷했다. 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1707번: 이분 그래프 (Python) 백준 1707번: 이분 그래프 (Python) 접근 이분 그래프가 무엇인지부터 찾 ca.ramel.be 기본적으로 최단경로를 구하는 다익스트라 알고리즘을 이용하여 풀었다. ( 다익스트라 알고리즘 ) 방향성이 없는 점은 처음에 그래프를 추가할 때, 서로..

2021. 4. 15. 00:31
코딩/백준 (Python)

백준 1753번: 최단경로 (Python)

접근 이전의 이분 그래프 문제와 풀이 과정이 비슷했다. 참고: 2021.04.14 - [코딩/백준 (Python)] - 백준 1707번: 이분 그래프 (Python) 백준 1707번: 이분 그래프 (Python) 접근 이분 그래프가 무엇인지부터 찾아보고 이해하고 나서 쉽다고 생각했으나 생각보다 시간초과와 오래 싸웠던 것 같다. 이분 그래프란, 쉽게 말하면 모든 점을 빨강과 파랑 두가지 색으로 칠 ca.ramel.be 비슷한 풀이에 거기에 가중치를 추가로 저장하여 각각의 정점들을 탐색하면서 가중치의 최소값으로 최신화 해주면서 탐색을 이어나가면 된다. 이런 식으로 그래프에서 최단 경로를 찾는 알고리즘을 다익스트라 알고리즘이라고 한다. 이 알고리즘은 최단경로를 찾는 알고리즘 중 하나이고, 자세한 설명은 아래 ..

2021. 4. 14. 22:42
코딩/백준 (Python)

백준 1707번: 이분 그래프 (Python)

접근 이분 그래프가 무엇인지부터 찾아보고 이해하고 나서 쉽다고 생각했으나 생각보다 시간초과와 오래 싸웠던 것 같다. 이분 그래프란, 쉽게 말하면 모든 점을 빨강과 파랑 두가지 색으로 칠한다고 했을 때, 선으로 이어져 이웃하는 점들이 항상 서로 다른색으로 칠해질 수 있는 그래프를 말한다. 고로 한 점에서 시작하여 주어진 선들을 따라 진행하면서 이전 단계와 다른 색을 칠해주면서 탐색했을 때, 다음 칸이 이미 칠해진 같은 색을 가지고 있다면 이분 그래프가 아닌 것으로 판단해주면 된다. 코드 import sys def bfs(a): q.append(a) visited[a] = 1 while q: now = q.pop(0) for i in range(len(lines[now])): if visited[lines[..

2021. 4. 14. 21:14
반응형