[파이썬] 그리디 알고리즘의 응용과 예제
그리디 알고리즘은 최적 부분 구조를 이용하여 문제를 해결하는 알고리즘입니다. 이 알고리즘은 각 단계에서 최적의 선택을 함으로써 전체적으로도 최적의 결과를 얻을 수 있습니다.
그리디 알고리즘의 응용은 다양한 문제에 활용될 수 있으며, 이를 통해 실제 예제를 풀어보겠습니다. 이번 예제에서는 순회 세일스맨 문제를 그리디 알고리즘을 사용하여 해결하는 방법을 살펴보겠습니다.
순회 세일스맨 문제
순회 세일스맨 문제는 도시를 모두 방문하면서 가장 짧은 경로를 찾는 문제입니다. 이 문제를 그리디 알고리즘을 사용하여 해결하면 다음과 같습니다.
입력
- 도시의 수:
n - 도시 사이의 거리를 저장한 2차원 배열:
distances
출력
- 가장 짧은 경로를 나타내는 도시 순서의 배열
def find_shortest_path(n, distances):
current_city = 0 # 출발 도시를 0번 도시로 설정
visited_cities = [current_city] # 방문한 도시를 저장하는 배열
while len(visited_cities) < n: # 모든 도시를 방문할 때까지 반복
next_city = -1 # 다음 방문할 도시
min_distance = float('inf') # 최단 거리를 무한대로 초기화
for i in range(n):
if i not in visited_cities: # 방문하지 않은 도시일 경우
if distances[current_city][i] < min_distance: # 더 짧은 거리를 발견한 경우
next_city = i # 다음 방문할 도시를 설정
min_distance = distances[current_city][i] # 최단 거리 갱신
visited_cities.append(next_city) # 다음 도시를 방문한 도시 목록에 추가
current_city = next_city # 현재 도시를 다음 도시로 변경
return visited_cities
# 예제 입력
n = 4 # 도시의 수
distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
# 함수 호출
shortest_path = find_shortest_path(n, distances)
print(shortest_path) # [0, 1, 3, 2]
위의 코드에서는 현재 도시에서 방문하지 않은 도시 중에서 가장 가까운 도시를 선택하여 방문하는 것을 반복합니다. 이렇게 하면 모든 도시를 방문하면서 가장 짧은 경로를 구할 수 있습니다.
위 코드를 실행하면, 주어진 예제 입력에 대한 가장 짧은 경로인 [0, 1, 3, 2]가 출력됩니다.
이와 같이 그리디 알고리즘을 사용하여 순회 세일스맨 문제를 해결하는 방법을 살펴보았습니다. 그리디 알고리즘은 최적 부분 구조를 가지는 문제에 유용하게 적용될 수 있으며, 여러 가지 문제에 적용하여 최적의 결과를 얻을 수 있습니다.