가전제품 이것저것 이야기

1) 최소 신장트리의 이해

신장트리란?

• Spanning Tree, 또는 신장 트리 라고 불리움
• 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
• 신장 트리의 조건
  • 본래의 그래프의 모든 노드를 포함해야 함
  • 모든 노드가 서로 연결
  • 트리의 속성을 만족시킴 (사이클이 존재하지 않음)

최소 신장트리란?

• Minimum Spanning Tree, MST 라고 불리움
• 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함

최소 신장트리 알고리즘

• 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
• 대표적인 최소 신장 트리 알고리즘
  • Kruskal’s algorithm (크루스칼 알고리즘)
  • Prim's algorithm (프림 알고리즘)

2) 크루스칼 알고리즘

• 모든 정점을 독립적인 집합으로 만든다.
• 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
• 두 정점의 최상위 정점을 확인하고, 서로 다른 집합일 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
• 탐욕 알고리즘을 기초로 하고 있음

3) 프림 알고리즘

• 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식
• 크루스칼 알고리즘과 프림 알고리즘 비교
  • 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
  • Kruskal's algorithm은 전체 간선중에서, 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
  • Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구함

1. spring boot

: 스프링 프레임워크와 3rd party library들에 대한 복잡하고 반복적인(boiler-plate) 설정 코드를 최소화하고 비즈니스 로직 구현에 집중하게 함

- 내장된 Servlet container(Tomcat)를 이용하여 독립적으로 실행 가능한 Spring 애플리케이션 개발 가능 (JAR)

- 'starter' dependency를 이용한 build 의존성 설정 간소화

- 스프링 프레임워크와 3rd party library들에 대한 자동 설정(auto-config)

2. 스타터 의존성(starter)

spring-boot-starter 가 포함하는 의존성

1) spring-boot

2) spring-boot-autoconfigure

3) spring-boot-starter-logging

4) javax-annotation-api

5) spring-core

6) snakeyaml

spring-boot-starter-web이 포함하는 의존성

1) spring-boot-starter

2) spring-boot-starter-json

3) spring-boot-starter-tomcat

4) spring-web

5) spring-webmvc

+ spring-boot-starter-jdbc

3. 자동설정(auto-configuration)

: 어플리케이션 실행 시, classpath에 Spring module 또는 3rd party library가 존재할 경우,

관련된 bean들의 설정을 자동으로 실행한다.

예) 특정 database가 classpath에 있으면 그 database를 사용하는 Datasource bean들을 자동으로 실행한다.

예) spring-jdbc 모듈이 classpath에 있고, datasource bean이 설정되어 있으면 jdbcTemplate bean을 자동으로 설정해준다.

예) Spring-webmvc 모듈이 classpath에 있으면 DispatcherServlet, HandlerMapping 등 Spring MVC의 기본 bean들을 자동 설정

예) Thymeleaf library가 classpath에 있으면  template resolver, view resolver, template engine 등을 자동으로 설정(view로 이용 가능)

예) Spring Security 모듈이 classpath에 있으면 Spring Security 기반의 웹 보안을 위해 필요한 bean들을 자동 설정

예) Embedded Tomcat이 classpath에 있으면 Tomcat servlet container를 시작함 (8080 port 사용)

아래와 같은 명시적인 설정을 하지 않아도 Spring boot가 필요한 bean들을 자동으로 생성 및 설정해준다.

4. Spring boot Actuator

: 실행중인 애플리케이션의 내부 상태를 조회하고 모니터링하는 기능

다양한 application metrics

1) 실행중인 process, thread의 상태

2) HTTP 요청

3) 메모리 사용량

4) data source 사용량(connection 개수)

5) GC 횟수 및 개수

- Web endpoint(Rest URL)이나 원격 shell을 통해 이용 가능하다.

5. @SpringBootApplication

어노테이션은 다음과 같은 세 가지 어노테이션을 포함한다.

1) @SpringBootConfiguration : @Configuration 기능 포함

2) @EnableAutoConfiguration : classpath 기반으로 자동 bean scan 실행

4) @ComponentScan : 현재의 package를 base로 자동 bean scan 실행

- sub package들도 모두 실행

6. shell/cmd에서 build 실행 방법

1) mvnw가 포함된 폴더로 이동

2) mvnw package

-> build 후 JAR 파일 생성

3) java -jar target/demo-0.0.1-SNAPSHOT.jar

-> 생성된 JAR 파일 실행

4) mvnw spring-boot:run

-> build 후 바로 실행

7. 추가적인 MVC 설정, 인터셉터 설정

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 배열 사용