가전제품 이것저것 이야기

1. 벨만 포드 알고리즘

victorydntmd.tistory.com/104

def bellman_ford(graph, start):
    distance, predecessor = dict(), dict()  # 거리 값, 각 정점의 이전 정점을 저장할 딕셔너리
    # 거리 값을 모두 무한대로 초기화 / 이전 정점은 None으로 초기화
    for node in graph:  
        distance[node], predecessor[node] = float('inf'), None
    distance[start] = 0  # 시작 정점 거리는 0

    # 간선 개수(V-1)만큼 반복
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbour in graph[node]:  # 각 정점마다 모든 인접 정점들을 탐색
                # (기존 인접 정점까지의 거리 > 기존 현재 정점까지 거리 + 현재 정점부터 인접 정점까지 거리)인 경우 갱신
                if distance[neighbour] > distance[node] + graph[node][neighbour]:
                    distance[neighbour] = distance[node] + graph[node][neighbour]
                    predecessor[neighbour] = node

    # 음수 사이클 존재 여부 검사 : V-1번 반복 이후에도 갱신할 거리 값이 존재한다면 음수 사이클 존재
    for node in graph:
        for neighbour in graph[node]:
            if distance[neighbour] > distance[node] + graph[node][neighbour]:
                return -1, "그래프에 음수 사이클이 존재합니다."

    return distance, predecessor
    
    
# 음수 사이클이 존재하지 않는 그래프
graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}

# 그래프 정보와 시작 정점을 넘김
distance, predecessor = bellman_ford(graph, start='A')

print(distance)
print(predecessor)


# 음수 사이클이 존재하는 그래프
graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {'A': -5},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}


distance, predecessor = bellman_ford(graph, start='A')

print(distance)
print(predecessor)

2. 플로이드 와샬 알고리즘

blog.naver.com/ndb796/221234427842

from sys import stdin
from math import inf

n = int(stdin.readline())
m = int(stdin.readline())

# 이동 최소비용을 저장할 2차원 배열
cost = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, stdin.readline().split())
    cost[a-1][b-1] = min(cost[a-1][b-1], c)

# 플로이드 와샬 알고리즘 적용
k in range(n):
    cost[k][k] = 0
    for i in range(n):
        for j in range(n):
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

# 결과 출력
for row in cost:
    for i in range(n):
        # 갈 수 없는 경로인 경우, 0 출력
        if row[i] == inf:
            row[i] = 0
        print(row[i], end=" ")
    print()

1. 비용을 정렬한다.

2. 비용이 작은 노드부터 방문한다.

3. 시작점으로부터의 비용을 갱신한다.

C언어 코드

#include <stdio.h>
#include <limits.h>

#define TRUE    1
#define FALSE   0
#define MAX_VERTICES    100     /* 노드의 수 */
#define INF     9999        /* 무한 값(연결이 없는 경우) */

int distance[MAX_VERTICES]; /* 시작노드로부터의 최단경로 거리 */
int previous[MAX_VERTICES]; /* 경유 노드  :  이 배열의 값을 어떻게 설정할 것인가?가 이 숙제의 문제*/
int found[MAX_VERTICES];    /* 방문한 노드 표시 */

typedef struct GraphType {
    int n;                  // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
    int r,c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++)
    for (c = 0; c < MAX_VERTICES; c++)
    g->adj_mat[r][c] = INF;
    
    for (r = 0; r < MAX_VERTICES; r++) // pak 추가
    g->adj_mat[r][r] = 0;
}

int choose(int distance[], int n, int found[])
{
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for (i=0; i < n; i++)
    if (distance[i] < min && ! found[i]) {
        min = distance[i];
        minpos=i;
    }
    return minpos;
}


void read_graph_to_adj_mat(GraphType *g)
{
    int n, u, v;
    scanf("%d", &n);
    g->n = n;
    scanf("%d", &u);
    while (u != -1)
    {
        scanf("%d", &v);
        scanf("%d", &g->adj_mat[u][v]);
        g->adj_mat[v][u] = g->adj_mat[u][v];
        
        scanf("%d", &u);
    }
}
void print_path(int start, int end)
{
    int u = end ;
    if(start == end) {
        printf("%d", start);
        return;
    }
    else {
        print_path(start, previous[u]);
        printf("->%d", u);
    }
}
void shortest_path(GraphType *g, int start, int e, int except) /* 시작노드 */
{
    int i, u, w;
    for(i=0; i<g->n; i++)   /* 초기화 */
    {
        distance[i] = g->adj_mat[start][i];
        found[i] = FALSE;
        previous[i] =start;
    }
    
    found[start] = TRUE;    /* 시작노드 방문 표시 */
    distance[start] = 0;
    
    for(i = 0; i < (g->n)-1; i++) {
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        if(u == except) continue;
        if(u == e) {
            print_path(start, u);
            printf("(%d)\n", distance[u]);
        }
        for(w=0; w<g->n; w++) { // distance[] 재조정
            if(!found[w])
                if( distance[u] + g->adj_mat[u][w] < distance[w] ) {
                    distance[w] = distance[u] + g->adj_mat[u][w];
                    previous[w] = u;
                }
        }
    }
}

int main()
{
    GraphType g;        // 입력 그래프
    int sIndex, dIndex, eIndex;
    graph_init(&g);;
    
    read_graph_to_adj_mat(&g);
    
    //printf("시작점:");
    scanf("%d", &sIndex);
    //printf("도착점:");
    scanf("%d", &dIndex);
    
    //printf("제외점:");
    scanf("%d", &eIndex);
    //shortest_path(&g, sIndex, dIndex);
    shortest_path(&g, sIndex, dIndex, eIndex);
}

파이썬의 우선순위 큐를 사용해보면 좋을 것 같다.

www.daleseo.com/python-priority-queue/

www.daleseo.com/python-heapq/

메모이제이션 강좌를 보셨나요? 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다.

알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.

dfs(깊이우선탐색)

한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 

- 재귀로 구현한다.

- 한번 방문한 곳은 다시 가지 않기 위해 check 배열 사용

BFS(너비우선탐색)

인접 노드부터 탐색

- 큐를 사용한다.

- 한번 방문한 곳은 다시 가지 않기 위해 check 배열 사용

[ 정렬의 종류 ]

재귀를 이용하지 않는 정렬

1) Selection Sort(선택정렬)

2) Bubble Sort(버블정렬)

3) Insertion Sort(삽입정렬)

재귀를 이용하는 정렬

4) Merge Sort

5) Quick Sort

1. Selection Sort

가장 큰 값을 찾아 맨 오른쪽으로 보낸다.

ex) 학생의 성적을 정렬하는 프로그램

학생은 학번, 영어, 수학, 국어 성적을 가지고 있음

국어 성적을 기준으로 내림차순 정렬 (selection sort)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Student {
    int stu_id;
    int eng;
    int math;
    int korean;
};

struct Student* selectSort(struct Student *arr_std, int n){
    
    int i, j, max, maxId;
    struct Student tmp;
    
    for(j=0; j<n-1; j++){
        max = arr_std[0].eng;
        maxId = 0;
        for(i=0; i<n-j; i++){
            if(arr_std[i].eng > max){
                max = arr_std[i].eng;
                maxId = i;
            }
        }
        tmp = arr_std[n-1-j];
        arr_std[n-1-j] = arr_std[maxId];
        arr_std[maxId] = tmp;
    }
    
    return arr_std;
}

int main(void) {
    
    int n, i;
    scanf("%d", &n);

    struct Student *arr_std = (struct Student *)malloc(sizeof(struct Student) * n);

    int stu_id_first = 20210001;
    srand((unsigned)time(NULL));
    
    for(i=0; i<n; i++){
        arr_std[i].stu_id = stu_id_first + i;
        arr_std[i].eng = rand() % 101;
        arr_std[i].math = rand() % 101;
        arr_std[i].korean = rand() % 101;
    }
    
    arr_std = selectSort(arr_std, n);
    
    for(i=0; i<n; i++){
        printf("%d %d %d %d\n", arr_std[i].stu_id, arr_std[i].eng, arr_std[i].math, arr_std[i].korean);
    }
    
    return 0;
}

2. Bubble Sort

두 개 중에 큰 값을 오른쪽에 배치한다.

3. Insertion Sort (삽입정렬)

왼쪽부터 한 숫자씩 선택하면서 자리를 찾고 바꾼다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int* insertSort(int *arr, int n){
    int i,j,tmp;
    
    for(i=1; i<n; i++){
        for(j=0; j<i; j++){
            if(arr[j] > arr[i]){
                tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
                continue;
            }
        }
    }
    return arr;
}

int main(void) {
    
    int i,n;
    scanf("%d", &n);
    
    int *arr = (int *)malloc(sizeof(int) * n);
    srand((unsigned)time(NULL));
    
    
    for(i=0; i<n; i++){
        arr[i] = rand() % 100;
        printf("%d ",arr[i]);
    }
    printf("\n");
 
    arr = insertSort(arr, n);
    
    for(i=0; i<n; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}

4. Quick Sort

평균 수행시간 : nlogn

최악 수행시간 : n^2

1) j는 0부터 n-1까지 돈다.

2) 값이 젤 오른쪽 값보다(pivot) 작으면 i와 j 위치의 값을 서로 바꿔준다. i++

3) j loop가 끝나면 i와 pivot 자리의 값을 바꾼다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int partition(int *arr, int s, int e){
    
    int i, j, tmp;
    
    i = s;
    for(j=s; j<e; j++){
        if(arr[j] < arr[e]){
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
            i++;
        }
    }
    
    tmp = arr[e];
    arr[e] = arr[i];
    arr[i] = tmp;
    
    return i;
}


void quickSort(int *arr, int p, int r){
    int q;
    
    if(p < r){
        q = partition(arr, p, r);
        quickSort(arr, q+1, r);
        quickSort(arr, p, q-1);
    }
}

int main(void) {
    
    int n;
    scanf("%d", &n);
    
    int *arr = (int *)malloc(sizeof(int) * n);
    
    int i;
    srand((unsigned)time(NULL));
    
    for(i=0; i<n; i++){
        arr[i] = rand()%100;
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    quickSort(arr, 0, n-1);
    
    
    
    for(i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

5. Merge Sort

1) 반으로 반으로 끝까지 나눈다.

2) 나눠진 두 그룹을 합치면서 정렬한다.

3) 나눴던 것들을 계속 합치면서 정렬한다.

합할 때는 i = s, j = q + 1, t = s 로 시작해서 

arr[i] 와 arr[j] 중에 더 작은 것을 새로운 배열에 넣는다. 이 때 새로운 배열의 인덱스는 t이다.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void merge(int *arr, int s, int q, int e, int n){
    int *new_arr = (int *)malloc(sizeof(int) * n);
    
    int i = s, j = q+1, k = s;
    
    while(i <= q && j <= e){
        if(arr[i] > arr[j]){
            new_arr[k++] = arr[j++];
        } else {
            new_arr[k++] = arr[i++];
        }
    }
    
    while(i <= q){
        new_arr[k++] = arr[i++];
    }
    while(j <= e){
        new_arr[k++] = arr[j++];
    }
    
    for(i=s; i<=e; i++){
        arr[i] = new_arr[i];
    }
}

void mergeSort(int *arr, int s, int e, int n){
    int q;
    if (s < e){
        q = (s + e) / 2;
        mergeSort(arr, s, q, n);
        mergeSort(arr, q+1, e, n);
        merge(arr, s, q, e, n);
    }
}

int main(void) {
    int n;
    scanf("%d", &n);
    
    int *arr = (int *)malloc(sizeof(int) * n);
    int i;
    srand((unsigned)time(NULL));
    
    for(i=0; i<n; i++){
        arr[i] = rand()%100;
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    mergeSort(arr, 0, n-1, n);
    
    
    for(i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    
    return 0;
}

* 퀵 소트는 먼저 정렬을 하고 나서 나눠가는 방식인데 비해, 머지 소트는 먼저 나누고 정렬을 해 나간다.

1. 개념

- 정적 할당 : 변수 선언을 통해 필요한 메모리 할당

- 동적 할당 : 실행 중에 운영체제로부터 할당 받음 (by Heap)

2. 사용법

malloc() / free()

* stdlib.h 을 include 해야 함

1) 기본 타입 메모리

int *pInt = (int *)malloc(sizeof(int));
char *pChar = (char *)malloc(sizeof(char));

2) 배열 타입 메모리

int *p = (int *)malloc(sizeof(int) * 5);

3. 예시 문제

1) 임의의 정수 n개를 입력받아 n개의 난수를 만들어(0~999) 이를 오름차순을 정렬하는 프로그램

(동적할당 + 선택정렬)

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    
    int n, i;
    
    scanf("%d", &n);
    
    int *arr = (int *)malloc(sizeof(int) * n);
    
    srand((unsigned)time(NULL));
    
    for(i=0; i<n; i++){
        arr[i] = rand() % 1000;
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    
    // selection sort
    int j, k, max, maxIdx, tmp;
    
    for(k=0; k<n-1; k++){
        max = arr[0];
        maxIdx = 0;
        for(j=0; j<n-k; j++){
            if(max < arr[j]){
                max = arr[j];
                maxIdx = j;
            }
        }
        
        // 젤 뒤로 보내기
        tmp = arr[n-1-k];
        arr[n-1-k] = arr[maxIdx];
        arr[maxIdx] = tmp;
    }
    
    for(i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    
    return 0;
}

(동적할당 + 버블정렬)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    
    int n, i;
    scanf("%d", &n);
    
    int *arr = (int *)malloc(sizeof(int) * n);
    srand((unsigned)time(NULL));
    
    for(i=0; i<n; i++){
        arr[i] = rand() % 1000;
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    // bubble sort
    int j, k, tmp;
    
    for(k=0; k<n-1; k++){
        for(j=0; j<n-1-k; j++){
            if(arr[j] > arr[j+1]){
                tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    
    for(i=0; i<n; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    return 0;
}