반응형

2024/09/24 4

[백준] 1260 DFS 와 BFS Python

1. 문제그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V M 개의 줄에는 간선이 연결하는 두 정점의 번호가 주어지고, 입력으로 주어지는 간선은 양방향이다1 2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 깊이 우선 탐색3. 접근 방식DFS (Stack 이용) 와 BFS (deque 이용) 를 공부한 김에 관련 문제를 풀어봤다DFS, BFS 개념 정리 [TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Se..

알고리즘 2024.09.24

[TIL] 플로이드 와샬 Floyd Warshall

플로이드 와샬 Floyd Warshall 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘거쳐가는 정점을 기준으로 최단 거리를 구한다  플로이드 와샬 특징 1. 시작 정점과 도착 정점의 구분 없이 모든 경로에 대한 최단 경로를 구하는 데 사용된다2. 동적 계획법을 사용하여, 경로가 점차적으로 개선되면서 최단 경로를 찾는다3. 음수 가중치를 갖는 그래프에서도 동작하지만, 음수 사이클이 있으면 알고리즘이 제대로 동작하지 않는다  (음수 사이클 - 음수 가중치를 갖는 경로로 인해 무한히 작은 경로가 생기는 경우)4. 시간 복잡도 가 O(N^3) 으로, 정점의 수가 적을 때는 효율적이지만 정점 수가 많을 수록 비효율적일 수 있다 5. 인접 행렬로 표현하여 사용되며, 행렬의 각 값은 두 정점 사이의..

TIL/Python 2024.09.24

[백준][아직못풀었음] 18352 특정 거리 도시 찾기 Python

1. 문제1번부터 N번까지의 도시와 M개의 단방향 도로가 존재할 때 (모든 도로의 거리는 1이다)특정한 도시 X로부터 출발하여 최단 거리가 K인 모든 도시의 번호를 구하는 프로그램을 작성하시오2  2. 알고리즘 분류* 그래프 이론* 그래프 탐색* 너비 우선 탐색* 최단 경로* 데이크스트라 3. 접근 방식Week02 퀴즈 주제인 다익스트라를 이용하여 문제를 푸려고 한다 4. 전체 코드첫번째 시도 다익스트라 함수를 별개로 구현하고, N, M, K, X 를 입력 받아 딕셔너리 형태로 graph 를 만들었다 그리고 딕셔너리에서 items() 로 node 와 edge 를 꺼내 edge 와 K 를 비교해서 result list 에 append 하고, 나중에 .join() 으로 정리해서 print 했다import h..

알고리즘 2024.09.24
반응형