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

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

단순한 그래프 문제이다.

입력받은 edge를 배열에 저장하고 해당 배열을 DFS, BFS에 맞게 탐색하면서 풀었다.

DFS, BFS에서의 다른 점은 BFS는 바로바로 다음 방문 배열에 넣은 반면, DFS는 해당 노드에서 인접한 노드를 모두 구해 배열로 만든 후 다음 방문 배열 앞으로 넣어주었다.

import sys

N, M, V = map(int, sys.stdin.readline().split())

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

for i in range(M):
    V1, V2 = map(int, sys.stdin.readline().split())
    graph[V1-1][V2-1] = True
    graph[V2-1][V1-1] = True

DFS, BFS = [False for i in range(N)], [False for i in range(N)]
to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if DFS[cur_node]:
        continue
    save_to_visit = []
    for i in range(N):
        if graph[cur_node][i] and not DFS[i]:
            save_to_visit.append(i)

    to_visit = save_to_visit + to_visit

    print(cur_node + 1, end=' ')
    DFS[cur_node] = True

print()

to_visit = [V-1]

while to_visit:
    cur_node = to_visit.pop(0)
    if BFS[cur_node]:
        continue

    for i in range(N):
        if graph[cur_node][i] and not BFS[i]:
            to_visit.append(i)

    print(cur_node + 1, end=' ')
    BFS[cur_node] = True

• 이미지와 컨테이너는 무엇인가?

저번에 다루어 봤듯이 컨테이너는 애플리케이션, 애플리케이션을 실행하는 전체 환경 등등 무엇이든 포함하는 작은 패키지이다.

컨테이너에는 소프트웨어 실행 유닛이 존재하며, 우리는 그 유닛을 실행하는 것이다.

이미지는 템플릿, 컨테이너의 블루프린트이다.

이미지는 실제로 코드와 코드를 실행하는데 필요한 도구를 포함한다.

하나의 이미지는 하나의 컨테이너만 실행하는 것이 아니라

이미지를 기반으로 여러 컨테이너를 만들 수 있다.

이미지는 모든 설정과 코드가 포함된 공유 가능한 패키지이며, 컨테이너는 그런 이미지의 구체적인 실행 인스턴스이다.

• 외부에서 이미지를 가져와 사용하기

이미지는 우리가 직접 만드는 것이 아닌, 가져와서 사용하는 방법도 존재한다.

일반적이어서 미리 구축이 되어 있는 공식 이미지들이 많이 있으며, 해당 이미지를 가져오는 것도 좋은 방법이다.

보통은 DockerHub에서 많이 찾아볼 수 있다.

https://hub.docker.com/

docker run node 명령어를 실행해 보았는 데, 아래처럼 나오는 것을 볼 수 있다.

우선 local에서 node image를 찾고, 없기 때문에 원격으로 이미지를 가져오는 것을 볼 수 있다.

• 이미지를 이용하여 빌드하기

커스텀 이미지를 만들기 위해서는 Dockerfile을 만들고 작성해야 한다.

우선 다음과 같이 작성한다.

FROM node

WORKDIR /app

COPY . /app

RUN npm install

EXPOSE 80

CMD ["node", "server.js"]

FROM은 다른 베이스 이미지 위에 현재 이미지를 생성한다는 의미이다.

물론 처음부터 만들 수는 있지만, 언제나 코드에 필요한 도구 같은 레이어가 필요하기에 보통은 추가한다.

WORKDIR은 도커 내부에서 해당 컨테이너를 작업할 경로를 명시한다.

/app 폴더 밑에서 작업한다는 의미이다.

COPY는 Dockerfile과 같은 디렉토리디렉터리 내에서 작업 디렉터리로 복사해 가져갈 파일들을 적어놓는 것이며, . 을 사용하면 현재 디렉터리에서 Dockerfile을 제외한 모든 파일을 복사한다는 의미이며, 도커 내부의 /app 폴더로 복사해 간다는 것이다.

WORKDIR에 의해 도커 내부의 경로는 상대주소를 가질 수 있지만, 보통 명확하게 하기 위해 절대경로로 하는 것을 추천한다.

RUN은 이미지에서 실행할 명령을 작성하는 것이다. 여기서에선 npm install을 사용해 필요한 종속성들을 설치해 주었다.

EXPOSE는 노출하고 싶은 포트의 주소를 명시한다.

없어도 되지만 그래도 명시하도록 하자.

CMD는 이미지가 빌드 될 때 실행되는 명령이 아닌, 컨테이너를 실행할 때 사용하는 명령어를 적어두면 된다.

이제 해당 이미지를 바탕으로 빌드해보자.

docker build .

해당 명령어를 사용하면 현재 디렉토리에 있는 Dockerfile을 사용해 이미지를 빌드한다.

Dockerfile에 있는 명령어들이 실행 된 것을 볼 수 있다.

해당 이미지를 바탕으로 컨테이너를 실행해본다.

docker run -p 80:80 {이미지 ID}

이렇게 접속이 되는 것을 볼 수 있다.

도커의 실행 상태를 보고 싶다면

docker ps 명령어를 사용하여 현재 실행 중인 컨테이너들을 볼 수 있다.

• 이미지의 변경사항

이미지는 단순히 읽기를 위해서 작성한 코드이다.

무슨 말인지를 직접 보여주도록 하겠다.

이렇게 html 중간의 내용을 변경하였다.

이렇게 변경을 하고 도커의 컨테이너를 재실행해도

이렇게 이전 그대로 나오게 된다.

이는 이전에 COPY 한 내용을 바탕으로 실행이 되기 때문에 해당 COPY에서는 변경사항이 적용되지 않아 생기는 문제이다.

그렇기 위해 이미지로 빌드를 다시 해서 COPY를 다시 해야 해당 변경사항이 적용 될 것이다.

이미지를 다시 빌드하고 컨테이너를 실행해보니

이렇게 제대로 적용이 된 것을 볼 수 있다.

• 이미지의 레이어

Docker에서 이미지를 만들 때

이렇게 CACHED라고 나오는 경우를 볼 수 있을 것이다.

도커는 명령어를 다시 실행했을 때의 결과가 동일하다고 판단되면, Cache를 사용한다.

모든 명령의 결과를 캐시하고, 그 캐시를 사용하는 것이다.

이것을 레이어 기반 구조라고 한다.

Dockerfile의 모든 명령어는 레이어를 나타낸다.

이렇게 이미지 레이어를 기반으로 컨테이너가 실행되게 된다.

해당 레이어에서 아무것도 변경되지 않으면, 캐시를 사용하지만

만약 코드가 변경이 된다면 캐시의 일부만 사용하고 해당 변경내용을 다시 실행하게 된다.

이렇게 만약 코드가 변경이 되었다면, 해당 파일을 다시 COPY하며 캐시를 사용하지 않는 것을 볼 수 있다.

그리고 그 아래의 레이어들도 모두 재실행되는 것을 볼 수 있다.

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

당연히 heap을 사용해야 한다는 것은 알고 있었지만, 어떻게 사용할 지에 대해서 고민을 많이 했었다.

보석과 가방을 같은 heap에 넣는다는 생각을 하는 게 좀 힘들었던 것 같다.

무게를 기준으로 최소 heap에 보석과 가방을 넣어준다.

가방 같은 경우는 같은 무게에서 가장 뒤로 갈 수 있도록 가치에는 무한을 넣어준다.

하나씩 꺼낼 때 쓸 heap도 만들어준다.

보석과 가방을 넣은 heap에서 하나씩 꺼내어서 반복문을 실행해준다.

만약 꺼낸 것이 보석이라면 최대 heap에 가치를 넣어준다.

만약 꺼낸 것이 가방이라면 최대 heap에서 하나의 보석을 넣을 수 있는 것이므로 가장 큰 값을 가져와 결과값에 더해준다.

그렇게해서 구한 결과값을 출력해주면 된다.

import sys
import heapq

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

jewelry = list()

for _ in range(N):
    heapq.heappush(jewelry, list(map(int, sys.stdin.readline().split())))

for _ in range(K):
    heapq.heappush(jewelry, [int(sys.stdin.readline().strip()), float('inf')])

result = 0
cur_jewelry = list()

while jewelry:

    weight, value = heapq.heappop(jewelry)

    if value == float('inf'):
        if cur_jewelry:
            result += heapq.heappop(cur_jewelry)
    else:
        heapq.heappush(cur_jewelry, value * -1)


print(result * -1)

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

당연히 회의실 문제랑 똑같은 줄 알고 heap으로만 바꿔서 풀었었다.

문제를 똑바로 읽지 않은 내 잘못이다..

이번 문제는 해당 강의를 모두 가능하도록 만들어야 한다.

그렇기에 끝나는 시간으로 정렬하는 것이 아닌, 시작하는 순서대로 해서 빨리빨리 받아서 끝내도록 해야한다.

나중에 퀵정렬을 사용하는 것이 아니라 heap을 사용하여 입력을 받았다.

강의실을 배정할 때도 가장 빨리 끝나는 시간 순으로 정렬을 해두고, 앞의 시간이랑 비교해서 만약 강의 진행이 불가능 하다면 새로운 강의실을 편성한다.

만약 가능하다면 해당 강의실의 끝나는 시간을 현재 강의가 끝나는 시간으로 변경한 후 다시 heap으로 넣어준다.

import sys
import heapq

heap = []

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

for i in range(N):
    S, T = map(int, sys.stdin.readline().split())

    heapq.heappush(heap, [S, T])

room = list()
heapq.heappush(room, heap[0][1])
heapq.heappop(heap)

while heap:
    heap_S, heap_T = heapq.heappop(heap)

    if room[0] <= heap_S:
        heapq.heappush(room, heap_T)
        heapq.heappop(room)
    else:
        heapq.heappush(room, heap_T)


print(len(room))

마지막에는 강의실의 개수를 출력하고 마무리 해준다.

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

일의 자리는 * 1
십의 자리는 * 10

백의 자리는 * 100

으로 배열에 각 알파벳 마다 수를 계산해서 가지고 있는다.

그리고 큰 순으로 정렬을 해서 9, 8, 7, .... 이렇게 곱하기 해준 후 더해주면 된다.

import sys

word = [0 for i in range(ord('Z') - ord('A') + 1)]

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

    input_word = str(sys.stdin.readline().strip())

    cur_index = 1

    while input_word:
        word[ord(input_word[-1]) - ord('A')] += cur_index
        cur_index *= 10
        input_word = input_word[:-1]

word.sort(reverse=True)

result = 0

for i in range(10):
    result += (word[i] * (9-i))

print(result)

• 도커란?

도커는 컨테이너 기술입니다.

컨테이너를 생성하고 관리하기 위한 도구입니다.

이렇게 말하면 쉽게 이해가 되지 않으며, 왜 써야 하는 지도 잘 모르겠다.

우선 소프트웨어 개발에서 컨테이너는 표준화된 소프트웨어 유닛입니다.

아래는 구글 클라우드에서 말하는 컨테이란?입니다.

https://cloud.google.com/learn/what-are-containers?hl=ko

컨터이너는 스프링부트를 사용해 봐서 알겠지만, 해당 코드와 종속성, 코드들이 포함되어 있다.

도커는 결국 이러한 컨테이너의 생성 및 관리 프로세스를 도와주는 도구이다.

결국 도커로 이 컨테이너를 만들고 관리하는 것이 목표가 될 것이다.

• 컨테이너가 필요한 이유

왜 이렇게 개발에서 독립적인 표준화된 애플리케이션 패키지를 원하는 것일까?

이렇게 직접 작업한 로컬의 환경과 배포에서의 환경이 다른 경우가 생긴다.

Java 11에서는 사용하지 못하는 코드들이 있다면 문제가 될 것이다.

이러한 문제가 있기에 같은 개발 환경을 갖는 것은 상당히 중요한 문제이다.

이것을 도커의 컨테이너로 해결하는 것이다.

특정 버전을 도커 컨테이너에 Lock 할 수 있으므로, 코드가 항상 정확한 버전으로 실행되도록 할 수 있다.

애플리케이션이 자체적으로 필요한 버전을 제공하는 컨테이너에서 실행되게 된다.

또한 팀에서 작업을 하게 된다면

팀원 간에 작업 환경이 다르게 될 수도 있다.

그런 경우에도 문제가 생기지 않도록 같은 환경에서 실행될 수 있도록 한다.

또한, 혼자 작업을 하는 경우에도 문제가 될 수 있다.

이렇게 가지고 있는 프로젝트마다 버전이 다른 경우이다.

이런 상황에서도 컨테이너에 모든 환경이 속해있기 때문에 컨테이너만 바꾸면 문제없이 동작할 수 있게 된다.

• 가상 머신 VS 도커

옛날에 가상머신으로 네트워크 공부했던 거 처럼, 그냥 가상머신에 각각의 환경을 만들어서 배포를 해도 독립된 환경을 만들어 줄 수 있기는 하다.

하지만 보통은 도커를 사용하게 되는 데, 이유에 대해 알아보자.

리눅스의 가상머신을 이용한다고 해보자.

이렇게 각 App마다 VM을 사용하게 되고, 이 Virtual OS는 메모리, CPU등의 사용량이 높다.

때문에 VM을 많이 사용할 수록 큰 오버헤드가 발생하게 된다.

도커를 사용할 때를 보자.

이 컨테이너에는 중요한 도구, 런타임이 추가되어 있지만 오버헤드가 큰 운영체제 등은 들어가 있지 않다.

컨테이너 내부에 작은 레이어가 포함되어 있을 수는 있지만, VM을 설치하는 것과는 비교도 안되게 가벼울 것이다.

또한 도커를 사용하면 이미지를 만들어 다른 사람과 공유하며, 모든 사람이 자신의 시스템에서 사용한 것과 같은 환경을 제공해 줄 수 있다.

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

그리디답게 생각하는 데 오래 걸리지 않는다.

해당 카드 뭉치들에서 가장 작은 거 2개를 뽑아오는 것이 가장 최적일 것이다.

그러면 가장 작은 뭉치를 어떻게 가져오느냐를 생각해야 하는 데, 당연히 정렬이 먼저 떠오를 것이다.

여기서 퀵 정렬을 사용하면 nlogn의 시간복잡도가 나올 것인데, 지속적으로 가장 작은 것을 가져오려면 우선순위 큐를 사용하는 것이 logn으로 시간복잡도가 더 낮을 것이다.

그렇기 때문에 우선순위 큐를 사용하도록 한다.

import sys
import heapq

heap = []

for _ in range(int(sys.stdin.readline().strip())):
    heapq.heappush(heap, int(sys.stdin.readline().strip()))

result = 0

while len(heap) > 1:
    A = heapq.heappop(heap)
    B = heapq.heappop(heap)

    result += (A + B)
    heapq.heappush(heap, A + B)

print(result)

heap이라는 우선순위큐를 만들고 그곳에다가 카드의 수를 입력 받는다.

그리고는 while 반복문으로 카드 뭉치가 하나 남을 때까지 카드들을 뭉쳐주고 그렇게 뭉친 카드 뭉치는 다시 우선순위큐로 넣을 수 있도록 한다.

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

문제를 이해하는 시간만 한시간 정도 걸렸던 것 같다.

당연히 점수인 줄 알았는 데, 너무 이해가 되지 않아 질문게시판 찾아보니까 순위라고 하더라....

무조건 한 명 이상은 뽑을 것이니 처음 result를 1로 해준다.

그러고는 그냥 단순히 앞 순위로 정렬해주고, 반복문으로 순위를 점점 올려가며 가능한 친구들만 받고 result를 +1해준다.

import sys

for i in range(int(sys.stdin.readline().strip())):
    candidate = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(int(sys.stdin.readline().strip()))])
    top = 0
    result = 1

    for t in range(1, len(candidate)):
        if candidate[t][1] < candidate[top][1]:
            top = t
            result += 1

    print(result)