알고리즘, 자료구조15 퀵 정렬(Quick Sort) [Python / 파이썬] 1. 퀵 정렬 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식을 기준으로 퀵 정렬을 정리해 보도록 하겠다. 호어 분할 방식에서는 리스트의 첫 번째 데이터를 피벗으로 정한다. 이와 같이 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를.. 2022. 1. 17. 위상 정렬(Topology Sort) [Python / 파이썬] 1. 위상 정렬 위상 정렬(Topology Sort)은 정렬 알고리즘의 일종으로 위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 주어진 방향 그래프에서 위상 정렬을 수행하는 구체적인 알고리즘을 살펴보자. 진입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 위와 같은 알고리즘을 이용하여 간단하게 위상 정렬을 수행할 수 있다. 알고리즘에서 확인할 수 있듯이 큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복한다. 이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 위와 같이.. 2022. 1. 17. 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) [Python / 파이썬] 1. 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 다익스트라(Dijkstra's) 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 차이점은 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있고, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라와 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 또한 다익스트라 알고리즘은 그리디 알고리즘인데 플로이드 워셜 알고리즘은 다이나믹 프로그래.. 2022. 1. 16. 크루스칼 알고리즘(Kruskal Algorithm) [Python / 파이썬] 1. 크루스칼 알고리즘 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 '연결'할 때, 최소한의 비용으로 연결 하려면 어떤 알고리즘을 이용해야 할까? 예를들어 위와같은 그래프가 있다고 가정해보자. 3개의 도시가 있고, 각 도시 간 도로를 건설하는 비용은 23, 13, 25이다. 여기서.. 2022. 1. 15. 이전 1 2 3 4 다음
