100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/1967

원래 푸는 방법대로 풀지 않은 거 같다.

원래는 1번 노드에서 가장 먼 곳을 찾은 후, 그 노드에서 가장 먼 곳과의 거리를 구하면 된다.

그러면 노드에서는 지름을 구할 수 있다.

하지만 그냥 아무생각없이 모든 노드를 방문하는 방법으로 풀었는데, 그냥 풀렸다.

그래서 이번 문제는 그냥 간단하게 푸는 방법으로 풀도록 하겠다.

이번에는 그래프를 dict로 받았는데, 모든 노드에 대한 2차원 배열로 만들면 메모리 초과가 발생한다.

그냥 반복마다, 최대의 길이를 구하고 그 중에서 최대의 길이를 출력한다.

import sys
from collections import deque

n = int(sys.stdin.readline().strip())

node = {i: [] for i in range(n)}

for i in range(n - 1):
    start, end, weight = map(int, sys.stdin.readline().split())

    node[start - 1].append([end - 1, weight])
    node[end - 1].append([start - 1, weight])

result = 0

for i in range(n):
    cur_result = 0
    visited = [False for _ in range(n)]
    need_visit = deque()
    need_visit.append([0, i])
    visited[i] = True

    while need_visit:

        cur_weight, cur_node = need_visit.popleft()

        cur_result = max(cur_result, cur_weight)

        for next_node, next_weight in node[cur_node]:
            if visited[next_node] is False:
                visited[next_node] = True
                need_visit.append([cur_weight + next_weight, next_node])

    result = max(result, cur_result)

print(result)

https://www.acmicpc.net/problem/16234

평범한 그래프 문제였지만, 이동이 있었는지 체크하며 수를 하나씩 늘리는 과정이 좀 귀찮았다.

한 차례마다 각 칸에 대하여

위, 아래, 좌, 우 이렇게 4방향을 확인하고 만약 차이가 범위 내라면 그래프 탐색을 실행한다.

탐색을 진행하가며 인구수를 더해주고 탐색이 끝나면 총 인구를 칸으로 나누어 인구를 분배한다.

만약 해당 차례에 인구의 이동이 없었다면, 반복문을 종료하고 지금까지 소모한 턴을 출력한다.

import sys
from collections import deque

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

N, L, R = map(int, sys.stdin.readline().split())

nation = list()

for _ in range(N):
    nation.append(list(map(int, sys.stdin.readline().split())))

flag = True

result = 0

while flag:

    flag = False

    visited = [[False for _ in range(N)] for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if visited[r][c] is False:

                visited[r][c] = True

                need_visit = deque()
                change = [[r, c]]

                need_visit.append([r, c])

                people = nation[r][c]

                while need_visit:

                    cur_r, cur_c = need_visit.popleft()

                    for d in range(4):
                        next_r, next_c = cur_r + dx[d], cur_c + dy[d]
                        if 0 <= next_r < N and 0 <= next_c < N and visited[next_r][next_c] is False and L <= abs(nation[cur_r][cur_c] - nation[next_r][next_c]) <= R:
                            change.append([next_r, next_c])
                            visited[next_r][next_c] = True
                            need_visit.append([next_r, next_c])
                            people += nation[next_r][next_c]
                            flag = True

                per_people = people // len(change)

                for next_r, next_c in change:
                    nation[next_r][next_c] = per_people

    if flag:
        result += 1

print(result)

https://www.acmicpc.net/problem/5014

백준의 숨바꼭질 문제와 굉장히 비슷하다.

그냥 단순히 배열을 만들어서 BFS로 풀면 끝난다.

import sys
from collections import deque

F, S, G, U, D = map(int, sys.stdin.readline().split())

stair = [float('inf') for _ in range(F + 1)]
stair[S] = 0

need_visit = deque()

need_visit.append(S)

while need_visit:

    cur_stair = need_visit.popleft()

    if cur_stair == G:
        break

    next_up, next_down = cur_stair + U, cur_stair - D

    next_cnt = stair[cur_stair] + 1

    if 0 < next_up <= F and stair[next_up] > next_cnt:
        stair[next_up] = next_cnt
        need_visit.append(next_up)

    if 0 < next_down <= F and stair[next_down] > next_cnt:
        stair[next_down] = next_cnt
        need_visit.append(next_down)


print(stair[G] if stair[G] != float('inf') else "use the stairs")

https://www.acmicpc.net/problem/1167

트리의 지름을 구하는 방법은 우선, 한 노드에서 가장 멀리 있는 노드를 구한다.

그리고 그 노드에서 가장 멀리 있는 길이를 구한다.

그러면 그게 노드의 지름이 된다.

그러면 2번 길이를 구해야 하는 데, 귀찮아서 함수로 만들어버렸다.

우선 각 그래프에 대한 정보를 입력 받은 후 BFS를 진행한다.

처음의 BFS에서는 가장 멀리 있는 노드를 구하고, 그 다음의 BFS에서는 길이를 구한 후 출력한다.

from collections import deque
import sys

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]

for _ in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(target):
    weight = [-1] * (V + 1)
    weight[target] = 0
    need_visit = deque()
    need_visit.append(target)
    result = [0, 0]

    while need_visit:
        cur = need_visit.popleft()
        for v, w in graph[cur]:
            if weight[v] == -1:
                weight[v] = weight[cur] + w
                need_visit.append(v)
                if result[0] < weight[v]:
                    result = [weight[v], v]

    return result


print(bfs(bfs(1)[1])[0])

https://www.acmicpc.net/problem/7562

원래 상하좌우 4방향만 움직이던 그래프에서 나이트가 이동하는 8방향으로 이동 할 수 있도록 방향을 설정해주면 된다.

여기에는 못 가는 경우가 있을 줄 알았는데... 고려하지 않고 그냥 제출해도 맞다고 되는 것을 보니, 못 가는 경우가 존재하지 않는 것 같다.

그냥 Python3로 제출하면 시간초과가 발생하고 Pypy3로 제출했었다.

그냥 방향만 추가가 되었고, 푸는 방법은 기존과 다르지 않으니 더 설명은 하지 않도록 하겠다.

from collections import deque
import sys

dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [-2, -1, 1, 2, 2, 1, -1, -2]

for _ in range(int(sys.stdin.readline())):
    i = int(sys.stdin.readline().strip())

    start_y, start_x = map(int, sys.stdin.readline().split())

    dest_y, dest_x = map(int, sys.stdin.readline().split())

    visited = [[float('inf') for _ in range(i)] for _ in range(i)]
    visited[start_y][start_x] = 0

    need_visit = deque()

    need_visit.append([0, start_y, start_x])

    result = -1

    while need_visit:

        cur_cnt, cur_y, cur_x = need_visit.popleft()

        if cur_y == dest_y and cur_x == dest_x:
            result = cur_cnt

        for index in range(8):
            next_y, next_x = cur_y + dy[index], cur_x + dx[index]
            if 0 <= next_y < i and 0 <= next_x < i and visited[next_y][next_x] > cur_cnt + 1:
                need_visit.append([cur_cnt + 1, next_y, next_x])
                visited[next_y][next_x] = cur_cnt + 1

    print(result)

https://www.acmicpc.net/problem/2644

해당 문제의 분류는 분명 그래프에 너비 우선 탐색이겠지만, 딱 보자마자 플로이드 와샬이 생각이 나서 해당 방법으로 해결했다.

n * n 크기의 배열을 만들고 3중 반복문으로 각 촌수를 계산할 수 있도록 하였다.

import sys

n = int(sys.stdin.readline().strip())

target_a, target_b = map(int, sys.stdin.readline().split())

family = [[float('inf') for _ in range(n)] for _ in range(n)]

for _ in range(int(sys.stdin.readline().strip())):
    a, b = map(int, sys.stdin.readline().split())
    family[a-1][b-1] = 1
    family[b-1][a-1] = 1

for i in range(n):
    for t in range(n):
        for k in range(n):
            if t != k:
                family[t][k] = min(family[t][k], family[t][i] + family[i][k])


print(family[target_a - 1][target_b - 1] if family[target_a - 1][target_b - 1] != float('inf') else -1)

• 읽기 전용 볼륨

바인드 마운트는 로컬의 특정 위치로 연결이 된다.

그럴 때 런타임 중에 해당 파일들을 변경할 수 없도록 해야 하는 경우가 있을 것이다.

그런 경우에 사용하는 바인드 마운트를 읽기 전용 볼륨으로 전환하는 방법을 알아보자.

docker run -v "{로컬의 위치:도커의 위치:ro}" {image ID || image Name}

그럴 때는 -v 옵션을 사용하면서 :ro read-only 옵션을 넣어준다.

• Docker 볼륨 관리하기

우선 현재 도커에서 관리하고 있는 볼륨들을 먼저 확인해보자.

docker volume ls

현재는 익명 볼륨 2개와 이름 볼륨 1개를 사용하고 있는 것을 볼 수 있다.

당연히 바인드 마운트는 도커에 의해 관리되는 것이 아니기 때문에 여기에서 확인할 수 없다.

구체적으로 볼륨을 만들 수도 있다.

docker volume create {볼륨 이름}

많이 사용할 거 같지는 않다.

docker volume inspect {볼륨 이름}

inspect를 사용해서 해당 볼륨의 자세한 정보를 확인해볼 수 있다.

docker volume rm {볼륨 이름}

rm을 사용해서 볼륨을 제거할 수 있다.

물론 해당 볼륨을 사용하고 있는 컨테이너가 없을 때만 사용이 가능하다.

• dockerignore 사용하기

COPY를 할 때 보통 모든 파일들을 복사해가지만, 복사하면 안되는 파일도 있을 것이다.

그럴 때는 .dockerignore을 사용해서 복사를 막는다.

.dockerignore에 명시한 파일, 폴더 등은 복사가 되지 않으며 사용방법은 .gitignore와 비슷하다.

• Docker로 환경변수 작업하기

Dockerfile에 다음과 같이 작성하면 된다.

run 할 때 -e key=value로도 명시할 수 있다.

이렇게 환경변수를 사용하면 애플리케이션에서 해당 환경변수를 사용해 하드코딩할 필요 없이 유연하게 작성할 수 있다는 장점이 있다.

환경변수가 지정된 파일을 --env-file로 지정할 수 있다.

이렇게 key=value값이 지정되어 있는 파일을 

이렇게 docker run 할 때 지정해주면 된다.

• Docker에서의 데이터 종류

Docker에서의 데이터는 크게 3가지로 나눌 수 있다.

우리가 이미지를 만들고 컨테이너를 실행하는 데 필요한 데이터와 런타임 중에 임시로 생성되는 데이터, 그리고 런타임 중에 생성이 되며 영구적으로 저장해야 하는 데이터가 있다.

스프링부트를 사용하면 사용자로부터 파일 업로드를 받을 때가 있는 데, 이때 영구적인 데이터로 저장을 하는 것 같다.

이미지는 읽기 전용이기 때문에, 이 부분에 데이터를 추가할 수는 없다.

이 때는 volume을 사용해야 한다고 한다.

• 기존의 방법으로 컨테이너에 데이터 저장

기존의 방식으로 런타임 도중에 파일을 저장해보도록 하자.

run 할 때 --rm 의 옵션을 추가했다.

이 앱을 이용해서 해당 파일을 저장한다.

이렇게 저장된 파일에 접속이 가능한 것을 볼 수 있다.

과연 해당 파일은 컨테이너를 재실행하더라도 접속이 가능할까?

재실행하고 접속을 해보았지만

접속이 불가능한 것을 확인할 수 있다.

컨테이너가 삭제되고 재실행되었기 때문에 해당 파일도 삭제되어서 그런 것임을 알 수 있다.

--rm을 제거하여 컨테이너를 삭제하지 않고 재실행만 해보자.

stop 후 start로 재실행하니 해당 데이터는 삭제되지 않아 다시 접속이 가능한 것을 볼 수 있다.

하지만 여기서 한 가지 문제를 찾을 수 있다.

해당 데이터가 컨테이너 내부에 저장이 되기 때문에 컨테이너가 제거되면 데이터도 제거가 된다.

동일한 이미지를 사용하더라도 말이다.

WAS에서는 업로드 한 데이터들을 삭제하면 안되는 경우가 생길 수도 있기 해당 데이터를 가지고 있어야 한다.

그렇기 때문에 Docker의 volume을 사용하여 데이터를 유지할 수 있도록 해야 한다.

• volume이란?

volume은 호스트 머신의 폴더이다. 컨테이너나 이미지에 있는 것이 아니다.

volume은 도커가 인식하는 호스트 머신에 있는 폴더로서 도커 컨테이너 내부의 폴더에 매핑된다.

그리고 두 폴더의 변경 사항은 다른 폴더에 반영이 된다.

호스트 머신에 파일을 추가하면, 컨테이너 내부에서 액세스 할 수 있다.

컨테이너가 매핑된 경로에 파일을 추가하면, 호스트 머신에서도 사용할 수 있다.

이렇게 volume을 통해 데이터를 유지할 수 있다.

해당 volume은 컨테이너가 종료되더라도 유지되기 때문이다.

Docker의 volume에는 2가지 종류가 있다.

익명 volume과 명명된 volume이다.

익명 volume은 진짜 호스트 머신의 어딘가로 연결이 되며, 보통은 그 경로를 모를 것이다.

신경 쓸 필요가 없어 편하지만, 해당 익명 volume은 컨테이너가 종료된 경우에 삭제가 된다.

그렇기 때문에 이런 경우에는 Named volume을 사용해야 한다.

Named volume을 사용하는 방법은 run 할 때 -v 옵션을 사용하는 것이다.

docker run -v {volume 이름:컨테이너 내부 path} {image ID || image Name}

이렇게 실행을 하면 --rm 옵션으로 컨테이너를 삭제하더라도 데이터가 보존되는 것을 볼 수 있다.

• 바인드 마운트

개발하는 과정에서 스프링부트의 코드가 조금이라도 변경이 된다면, 이미지를 새로 만들고 해당 이미지로 컨테이너를 만들어야 했다.

해당 과정은 시간이 굉장히 오래 걸리고, 이미지가 쌓인다는 문제가 있었다.

바인드 마운트는 volume과는 다르게 해당 위치를 개발자가 알 수 있으며, 호스트 머신 상에 매핑될 컨테이너의 경로를 설정한다.

COPY로 소스코드를 복사하는 것이 아니라, 해당 마운트의 파일을 최신버전으로 유지하면서 배포할 수 있다는 장점이 있다.

바인드 마운트도 -v를 사용한다.

volume과는 거꾸로 {복사하고 싶은 디렉터리 : 컨테이너 디렉터로}로 실행할 수 있다.

docker run -v {바인드 마운트 할 경로:컨테이너 내부 path} {image ID || image Name}

하지만 이 과정에서 덮어쓰기 때문에 필요한 종속성들이 날아갈 수 있다.

그렇기 때문에 종속성이 있는 폴더는 익명 volume으로 유지하면서 run을 하면 종속성을 유지한 채로 최신 버전으로 실행이 가능하다.

• 컨테이너에서 데이터 관리하는 방법들 간의 비교