전체 글152 최단 경로 (다익스트라(Dijkstra)) 목차 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘은 모두 그래프에서 최단 경로를 찾는 알고리즘입니다. 각 알고리즘은 특정한 조건에서 사용됩니다. 다익스트라 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 없는 경우) 벨만-포드 : 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 찾을 때(음의 가중치가 존재하는 경우. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 플로이드-와샬 : 모든 노드쌍에 대한 최단경로를 모두 찾을 때(음의 가중치가 없어도 있어도 모두 사용가능. 단, 음의 사이클이 있으면 최단 경로 문제의 해를 찾는 것은 불가능) 다익스트라(Dijkstra) 다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의.. 2023. 10. 16. BFS(Breadth-First Search, 너비 우선 탐색), DFS(Depth-First Search, 깊이 우선 탐색) 목차 BFS(Breadth-First Search, 너비 우선 탐색) BFS는 그래프나 트리에서 가장 인접한 노드부터 방문하며, 더 이상 인접한 노드가 없을 때 다음 레벨의 노드들을 방문하는 방식으로 탐색하는 알고리즘입니다. BFS는 주로 큐를 사용하여 구현합니다. BFS의 시간복잡도는 O(V+E)가 됩니다. (V:노드수, E:간선수) 각 노드와 그와 연결된 간선을 한 번씩 확인하므로 위와 같은 시간복잡도를 가지게 됩니다. 코드 from collections import deque def bfs(graph,start,visited): q=deque([start]) # 현재 노드를 방문 처리 visited[start]=True # 큐가 빌 때까지 반복 while q: # 큐에서 하나의 원소를 뽑아 출력 v.. 2023. 10. 16. 그래프(Graph) vs 트리(Tree) 목차 Graph는 Tree를 포함하는 개념입니다. 즉, 모든 트리는 그래프이지만, 모든 그래프는 트리가 아닙니다. 그래프(Graph) 정의 그래프는 노드(Node) 또는 정점(Vertex)들을 연결하는 간선(Edge)의 집합입니다. 종류 방향 여부에 따른 분류 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프 무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프 가중치 여부에 따른 분류 가중치 그래프(Weighted Graph) : 간선에 가중치 또는 비용이 할당된 그래프 비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프 순환 여부에 따른 분류 순환 그래프(Cyclic Graph) : 그래프에 최소한 하나의 순환(또는 사이클)이 .. 2023. 10. 16. 동적 계획법(DP, Dynamic Programming) 목차 동적 계획법(DP, Dynamic Programming) 동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 풀고, 그 결과를 저장하여 큰 문제를 풀어나가는 것입니다. 문제에서 규칙 또는 점화식을 발견한다면, 동적 계획법(DP)를 사용하여 문제를 해결할 수 있습니다. 중복되는 계산 과정을 저장하여 시간을 절약할 수 있습니다. DP는 너무나도 많은 유형이 있고, 직접 다양한 문제들을 경험하며 실력을 키워나가야 합니다. 어떤 것을 메모이제이션(memoization)해서 이용할 것인가가 가장 중요합니다. (큰 문제를 작은 문제로 나눠서 풀때 중복되는 부분을 찾아야 합니다.) 예시 예시 1 (피보나치 수) 가장 대표적인 예시인 백준 2748 피보나치 수 2 문.. 2023. 10. 15. 이전 1 ··· 31 32 33 34 35 36 37 38 다음
