버블 정렬이란?버블 정렬은 두 개의 인접한 원소를 비교해 순서에 맞지 않으면 서로 교환하는 정렬 방식입니다. 이렇게 인접한 원소를 교환하는 모습이 마치 물 속의 거품과 비슷해 버블 정렬이라고 부르는 것입니다. 순서에 맞지 않은 원소들을 교환하다 보면 오른쪽 리스트는 자동으로 정렬되기 시작합니다. 이 과정에서 왼쪽 리스트에 있는 원소들을 반복적으로 교환하면 정렬이 완료됩니다.  버블 정렬 구현버블 정렬의 핵심은 비교 후 순서에 어긋나면 교환하는 것입니다. 각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다.왼쪽 리스트: 인접한 원소의 순서가 맞지 않으면 바꿔줍니다.오른쪽 리스트: 리스트 끝에서부터 정렬이 되어 있는 상태이므로 이 안에서 절대 자리..

삽입 정렬이란? 정렬이 되어 있는 왼쪽 리스트와 정렬이 되어 있지 않은 오른쪽 리스트로 나누었다고 가정해봅시다. 배열의 첫 원소부터 차례대로 앞에 이미 정렬되어 있는 왼쪽 리스트와 비교하며 어느 자리에 들어갈 지 위치를 판단한 후, 적절한 위치에 삽입하는 정렬 방식입니다. 삽입 정렬 구현 삽입 정렬의 핵심 또한 왼쪽 리스트와 오른쪽 리스트를 분리하는 것입니다. 각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다. 왼쪽 리스트: 오름차순 (혹은 내림차순) 으로 정렬이 되어있는 상태여야 함. 오른쪽 리스트: 정렬 관계는 상관 없지만, 왼쪽 리스트에 어느 부분에 삽입되어야 할 지 정확히 계산해야 합니다. 코드로 구현하면 아래와 같습니다. void i..

선택 정렬이란? 정렬이 되어 있는 왼쪽 리스트와 정렬이 되어 있지 않은 오른쪽 리스트로 나누었다고 가정해봅시다. 오른쪽 리스트에서 가장 작은 숫자를 선택해서 왼쪽 리스트에 차례대로 넣어줍니다. 그렇게 되면 왼쪽 리스트는 자동적으로 오름차순으로 정렬되게 됩니다. 이 방식을 선택 정렬이라고 합니다. 선택 정렬 구현 선택 정렬의 핵심은 왼쪽 리스트와 오른쪽 리스트를 분리하는 것입니다. 각자 아래 목적에 맞게 분리되어야 하므로 반복문을 통해 숫자가 담겨있는 배열이나 리스트에 제대로 접근해야 합니다. 왼쪽 리스트: 오름차순 (혹은 내림차순) 으로 정렬이 되어있는 상태여야 함. 오른쪽 리스트: 정렬 관계는 상관 없지만, 최솟값을 찾아 왼쪽 리스트 끝에 넣어주어야 합니다. 코드로 구현하면 아래와 같습니다. void ..

위상 정렬이란? 순서가 정해져있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘입니다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열할 수 있습니다. 위상 정렬의 특징 위상 정렬의 특징은 다음과 같습니다. 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방함. 따라서 다수의 위상 순서가 있을 수 있음 위상 정렬 과정에서 선택되는 정점의 순서를 위상 순서(topological order)라고 함 만약 진입 차수가 0인 정점이 없다면, 실행 불가능한 프로젝트가 되고 위상 정렬 알고리즘이 중단됨 그래프에 사이클이 존재하지 않아야 함 위상 정렬의 작동 방식 그래프에 있는 노드들의 진입 차수를 배열에 저장합니다. 그 후, 진입 차수가 0인 노드를 큐/..

Floyd의 최단 경로 알고리즘 최단 경로를 찾는 과정은 다음과 같습니다. 각각의 정점이 다른 정점으로 가는 최소 가중치를 저장 무작위의 두 정점 사이의 가중치와 그 두 정점 사이에 특정 정점을 거쳐서 가는 가중치를 비교해서 가장 가중치가 적은 간선으로 갱신 모든 노드를 방문할 때까지 2번을 반복 예시로 한 그래프를 Floyd의 알고리즘을 이용해 최단 경로를 구해보겠습니다. Floyd 알고리즘 또한 시작 정점에서 다른 정점으로 가는 최단거리를 기록하는 배열이 필요합니다. 각 정점에서 다른 정점으로 이동할 때 걸리는 가중치를 표로 표현한 것입니다. 표 위의 그래프와 비교해봅시다. 예를 들어, 0번 정점과 2번 정점의 간선 가중치를 확인해보면 23인 것을 알 수 있습니다. 또한 무방향 그래프를 표에 옮겼으므..

최단 경로 네트워크 상에서 정점 v와 정점 w를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제입니다. 최단 경로를 찾는 방법 중 Dijkstra, Floyd-Warshall가 고안한 알고리즘이 대표적으로 사용되고 있습니다. Dijkstra의 최단 경로 알고리즘 최단 경로를 찾는 과정은 다음과 같습니다. 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중, 특정 노드로 가는 가장 비용이 적은 간선 선택 새로 발견한 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 가중치로 갱신 모든 노드를 방문할 때까지 3번과 4번 반복 예시로 한 그래프를 Dijkstra의 알고리즘을 이용해 최단 경로를 구해보겠습니다. Dijkstra 알고리즘은 시작 정..

프림(Prim)의 MST 알고리즘 Prim 알고리즘은 특정 정점에서 시작해 신장 트리 집합을 단계적으로 확장해 나가는 방법입니다. 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택해 트리를 간선이 $n-1$개가 될 때까지 확장합니다. 최소 신장 트리 구하는 과정 예시로 한 그래프에서 Prim 알고리즘을 이용해 MST를 구해보도록 하겠습니다. 시작 정점은 0이라고 가정하겠습니다. 결론적으로 이 그래프의 최소 신장 트리는 마지막 사진에 색칠한 것과 같이 이루어짐을 알 수 있습니다. 코드로 구현하면 아래와 같습니다. typedef struct Graph { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; } Graph; int selected[MAX_..