본문 바로가기
반응형

Study86

[Algorithm] 플로이드-워셜(floyd-warshall) 알고리즘 (python) 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 최단 거리를 구할 때 사용하는 알고리즘이다. 벨만-포드 알고리즘과 같이 음수 가중치를 가지는 노드가 있어도 사용가능하다. 하지만 벨만-포드 알고리즘보다 더 큰 시간 복잡도를 가진다. 플로이드-워셜 알고리즘의 핵심 원리는 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합이라는 것이다. 파이썬으로 플로이드-워셜 알고리즘 구현하기 1. 최단 거리를 저장할 2차원 리스트 선언 출발 노드와 도착 노드가 같은 경우는 0으로 초기화하고 기본은 시스템 최댓값으로 초기화한다. dist=[[sys.maxsize]*(n+1) for _ in range(n+1)] for i in range(1, n+1): dist[i][i]=0 2. 주어진 그래프 값 저장 1에서 선언한 .. 2023. 2. 9.
[백준] #1976. 여행 가자 (python) 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라.. 2022. 12. 16.
[Algorithm] 유니온 파인드(Union-Find) 알고리즘 (python) 유니온 파인드 알고리즘 유니온 파인드 알고리즘은 이름 그대로 유니온 연산과 파인드 연산으로 구성되어 있는 알고리즘이다. 그래프에서 두 노드가 같은 그래프에 속해 있는지를 확인할 수 있다. 1. union 연산 두 노드가 속한 집합을 하나의 집합으로 합치는 연산이다. 2. find 연산 특정 노드가 속한 집합의 대표 노드를 반환하는 연산이다. 파이썬으로 유니온 파인드 알고리즘 구현하기 1. 1차원 리스트 사용 인덱스를 노드라고 생각하고 대표 노드 값을 리스트의 값으로 본다. 2. 2개의 노드의 집합을 하나로 합치는 union 연산 진행 두 노드를 합칠 때 두 노드의 리스트 값이 대표 노드가 아닌 경우가 있을 수 있다. 그럴 때 각 노드의 대표노드를 찾아서 대표 노드끼리 연결을 해야 한다. 3의 대표 노드가.. 2022. 12. 15.
[Python] 최단 경로 - 다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘 다익스트라 알고리즘은 그래프의 한 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 그래프의 노드를 잇는 간선에는 거리 정보가 주어진다. 다익스트라 알고리즘은 이 거리가 양수여야 한다. 다익스트라 알고리즘 구현 1. 주어진 그래프 구현 2. 최단 거리 리스트를 생성 3. 최단 거리 리스트에서 가장 작은 값을 가지는 노드 선택 4. 최단 거리 리스트 업데이트 - 선택한 노드의 최단거리 + 도착 노드까지의 거리와 도착 노드의 최단거리를 비교해서 작은 값으로 도착 노드의 최단 거리를 업데이트 한다. 이 과정을 반복해서 최단거리 리스트를 업데이트한다. 효율적인 다익스트라 알고리즘을 구현하기 위해 우선순위 큐를 사용해서 구현한다. 파이썬의 heapq 모듈을 통해 우선순위 큐를 사용할.. 2022. 3. 28.
반응형

티스토리툴바