2023/12/08 2

[알고리즘] 정렬 1

정렬 가지고 있는 자료를 사용하기 편하도록 정렬하려면 어떤 방법이 있을까? 이때 고민해 볼 수 있는 것이 정렬 알고리즘이다. 우선 정렬 Sort이란 순서 없이 배열된 자료를 작은 것부터 또는 큰 것부터 오름차순, 내림차순으로 재배열(재배치)하는 것이다. 여기서 재배열을 하는 기준을 어떻게 정하나인데, 가게를 예를 들면 유통기한 순으로 물건을 다시 진열하거나, 우리가 살면서 해야 할 일을 적을 때도 마찬가지이다. 이처럼 일상생활에서 자주 사용하는데.... 자료를 정렬하는데 사용하는 기준이 되는 특정 값(유통기한, 날짜 등)을 켜라고 한다. 따라서 우리는 그 키를 기준으로 정렬하면 크기가 키가 된다. 정렬 방식의 분류 기준 정렬 방식 설명 실행 방법 비교식 정렬 Comparative Sort 비교할 각 키값..

알고리즘 2023.12.08

[알고리즘] 그래프 8 - 최단 경로(플로이드)

최단 경로 플로이드 Floyd 최단 경로 알고리즘은 모든 정점 사이의 최단 경로 All to Shortest Path를 구하고 최단 경로로 만드는 알고리즘이다. 1. 초기 2차원 배열에 각 정점에서의 거리를 2차원 배열로 초깃값으로 집어넣는다. 2. 여기서부터 adj [v][w]=MIN(adj [v][w], adj [v][k]+adj [k][w])라는 식을 사용한다. 정점 0부터 k까지의 정점만을 이용한 정점 v에서 정점 w까지의 최단 경로를 의미하는데 정점 0부터 정점 k -1까지의 정점을 고려한 최단 거리 adj을 구한 상태에서 다음 정점 k를 정할 때, adj [v][w]와 adj [v][k] + adj [k][w] 중에서 작은 값을 최단 경로로 정한다. #include #define INF 100..

알고리즘 2023.12.08